Next:5.4.3 B-Trees: InsertionUp:5.4 B-TreesPrevious:5.4.1 Definition of B-Trees

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$\displaystyle \lceil$n/b$\displaystyle \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

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

    $\displaystyle {\frac{L}{l^{h-1}}}$$\displaystyle \geq$ 1
or   h$\displaystyle \leq$ loglL
i.e.,   h$\displaystyle \leq$ log$\scriptstyle \lceil$m/2$\scriptstyle \rceil$$\displaystyle \lceil$n/b$\displaystyle \rceil$  

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

                                                            h$\displaystyle \leq$ 3.9