3,447 views

5 Answers

1 votes
1 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

29 votes
29 votes
1 answer
5
Kathleen asked Oct 5, 2014
7,340 views
Consider $B^+$ - tree of order $d$ shown in figure. (A $B^+$ - tree of order $d$ contains between $d$ and $2d$ keys in each node)Draw the resulting $B^+$ - tree after $10...
26 votes
26 votes
5 answers
7
Kathleen asked Oct 5, 2014
6,885 views
Give a relational algebra expression using only the minimum number of operators from $(∪, −)$ which is equivalent to $R$ $∩$ $S.$
26 votes
26 votes
5 answers
8
Kathleen asked Oct 5, 2014
7,575 views
State True or False with reasonLogical data independence is easier to achieve than physical data independence.