Dark Mode

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