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 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.)
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.