5.4.2 Complexity of B-tree Operations

Let there be n records. If each leaf has b records on the average, we have,

                                                            average number of leaves = L = $$\lceil$$n/b$$\rceil$$
Longest paths occur if the number of children at every stage = $\lceil$m/2$\rceil$ = l, say

Average number of nodes that are parents of leaves = ${\frac{L}{l}}$

Average number of nodes that are second level parents

                                                                                = $$\left(\vphantom{\frac{L}{l}}\right.$$$${\frac{L}{l}}$$$$\left.\vphantom{\frac{L}{l}}\right)$$$$\left/\vphantom{ l = \frac{L}{l^2}}\right.$$l = $${\frac{L}{l^2}}$$$$\left.\vphantom{ l = \frac{L}{l^2}}\right.$$
If h is the level of the leaves, we have

$${\frac{L}{l^{h-1}}} \geq$$

$$\leq$$ or

$$\leq \lceil \rceil \lceil \rceil$$ i.e.,

If n = 106 records (1 million records), b = 10, and m = 100, we have 

                                                            h$$\leq$$ 3.9