in Databases
1,751 views
4 votes
4 votes
For a $B^+$ - tree of order $d$ with $n$ leaf nodes, the number of nodes accessed during a search is $O(\_)$.
in Databases
by
1.8k views

5 Answers

0 votes
0 votes

We can argue in the following way:

In the worst case, we can consider a complete $d$ - ary B+ tree ($\because$  B+ tree of order $d$ is given) and the key to be searched is present in the last level of the tree.

$\therefore$ Number of nodes accessed = $O ( h + d ) $ (as given in @Sachin Mittal 1 's answer)

For height of B+ tree,

Let the total number of nodes in tree be $N$.

Level 0 - $d^{0}$ nodes

Level 1 - $d^{1}$ nodes

Level 2 - $d^{2}$ nodes

Level 3 - $d^{3}$ nodes    

and so on till

Level h - $d^{h}$ nodes (last level)

$\therefore$        N = $d^{0}$ + $d^{1}$+ $d^{2}$+ $...$ + $d^{h}$ = $\frac{d^{h+1} -1}{d-1}$ = $\frac{nd -1}{d-1}$          ( $\because$ last level has leaf nodes= $n$ )

height of B+ tree= $\log _{d}N= \log$ $\frac{nd -1}{d-1}$ = $ O ( \log _{d}n$)

Number of nodes accessed = $O ( h + d ) $ = $ O (  \log _{d}n + d)$

Related questions