min/max number of records on a B+Tree?

I was looking at the best & worst case scenarios for a B+Tree (http://en.wikipedia.org/wiki/B-tree#Best_case_and_worst_case_heights) but I don't know how to use this formula with the information I have. Let's say I have a tree B with 1,000 records, what is the maximum (and maximum) number of levels B can have? I can have as many/little keys开发者_如何学Python on each page. I can also have as many/little number of pages. Any ideas? (In case you are wondering, this is not a homework question, but it will surely help me understand some stuff for hw.)

---

I don't have the math handy, but...

Basically, the primary factor to tree depth is the "fan out" of each node in the tree.

Normally, in a simply B-Tree, the fan out is 2, 2 nodes as children for each node in the tree.

But with a B+Tree, typically they have a fan out much larger.

One factor that comes in to play is the size of the node on disk.

For example, if you have a 4K page size, and, say, 4000 byte of free space (not including any other pointers or other meta data related to the node), and lets say that a pointer to any other node in the tree is a 4 byte integer. If your B+Tree is in fact storing 4 byte integers, then the combined size (4 bytes of pointer information + 4 bytes of key information) = 8 bytes. 4000 free bytes / 8 bytes == 500 possible children.

That give you a fan out of 500 for this contrived case.

So, with one page of index, i.e. the root node, or a height of 1 for the tree, you can reference 500 records. Add another level, and you're at 500*500, so for 501 4K pages, you can reference 250,000 rows.

Obviously, the large the key size, or the smaller the page size of your node, the lower the fan out that the tree is capable of. If you allow variable length keys in each node, then the fan out can easily vary.

But hopefully you can see the gist of how this all works.

---

It depends on the arity of the tree. You have to define this value. If you say that each node can have 4 children then and you have 1000 records, then the height is

Best case log_4(1000) = 5

Worst case log_{4/2}(1000) = 10

The arity is m and the number of records is n.

---

The best and worst case depends on the no. of children each node can have. For the best case, we consider the case, when each node has the maximum number of children (i.e. m for an m-ary tree) with each node having m-1 keys. So,

1st level(or root) has m-1 entries 2nd level has m*(m-1) entries (since the root has m children with m-1 keys each) 3rd level has m^2*(m-1) entries .... Hth level has m^(h-1)*(m-1)

Thus, if H is the height of the tree, the total number of entries is equal to n=m^H-1 which is equivalent to H=log_m(n+1)

Hence, in your case, if you have n=1000 records with each node having m children (m should be odd), then the best case height will be equal to log_m(1000+1)

Similarly, for the worst case scenario:

Level 1(root) has at least 1 entry (and minimum 2 children) 2nd level has as least 2*(d-1) entries (where d=ceil(m/2) is the minimum number of children each internal node (except root) can have) 3rd level has 2d*(d-1) entries ... Hth level has 2*d^(h-2)*(d-1) entries

Thus, if H is the height of the tree, the total number of entries is equal to n=2*d^H-1 which is equivalent to H=log_d((n+1)/2+1)

Hence, in your case, if you have n=1000 records with each node having m children (m should be odd), then the worst case height will be equal to log_d((1000+1)/2+1)