GATE CSE 1994 | Question: 14b

Question

For a $B^+$ - tree of order $d$ with $n$ leaf nodes, the number of nodes accessed during a search is $O(\_)$.

Answer 1

For $n$ leaves we have $n-1$ keys in the internal node. (see 'part a' of this question)

Total keys in internal nodes $= n-1,$ each node can have keys between d and 2d.

For $n-1$ keys there will be minimum $\left \lceil \frac{n-1}{2d} \right \rceil$ internal nodes, and maximum $\left \lceil \frac{n-1}{d} \right \rceil$ internal nodes.

To calculate Big-Omega I am taking maximum everywhere.

If every node contains $d+1$ pointers (d keys) then height will be maximum, because number of nodes to be accommodated are fixed $\left (\left \lceil \frac{n-1}{d} \right \rceil \right )$.

If height is $h$ then equation becomes

$\large 1+(d+1)+(d+1)^2+(d+1)^3 +\ldots+(d+1)^{h-1} = \frac{n-1}{d}$
$\implies \frac{(d+1)^h-1}{(d+1)-1} = \frac{n-1}{d}$
$\implies (d+1)^h = n$
$\implies h =\log_{(d+1)}n$

This is the maximum height possible or says the maximum number of levels possible.

Now using $h$ traverse we can get to the leaf node :

Answer is $O(h)$ i.e., $O(\log_{(d+1)}n)\\=O(\log_dn)$

Comments

if this is correct then my doubt is:

when we reach one of the leaf nodes and the element we are searching for is the last element in the list so ultimately we have to traverse all the elements which takes O(n) time as total n elements in leaf.

---

While searching, from top only, we compare and go down. We know that in a B+ tree to search a key value $K$:-

1. We start from the root, look for the largest key value $(K_i)$ in the node $<=$ $K$
2. Follow the pointer $P_{i+1}$ to next value until we reach the leaf node.
3. If $K$ is found = $K_i$ in the leaf, follow $P_{ri}$ to search record.

Now at every node since the elements inside it are sorted, we can perform binary search.

---

Abhrajyoti00

got it brother . Thanks  :)

Answer 2

if u think i am wrong at some point plz comment.

 

i think the first part. they have given their own definition of b+ tree.

no considering their definition . if d=1

then minimum no of nodes should be 1 and maximum should be 2 . which we can see is not the case as 4 keys are their in one node.

d=2

minimum =2 max =4

satisfy the condition .

d=3

one underflow case exists which means the value of d is 2. now insert it according order 5 tree.

now the second part.  number of acess will be order of level . as i have to access every level once till the leafs . as the record pointer is always present in leafs.

so to find worst case complexity the tree should be of maximum height so that the number of level can be full.

By putting maximum.
 

Height        nodes
0                 1

1                2d+1

2               (2d+1)^2

k               (2d+1)^k

 

n = (2d+1)^k

as n are leaf nodes which will result in k = log n base (2d+1)

Comments

that finding 'd' part is really helpful..thanks:)

Answer 3

as given min d keys at each node so assuming atleast d+1 child for each ( root too)

as they have given their own definition of degree

so (d+1)^ h = n

thus, h = log n / log (d+1)

 

or (if considering max child at each node )

 

as given 2d keys at each node so assuming 2d+1 child for each( root too).

if 2d+1 child at each then at height h (2d+1)^h = n

thus, h = log n / log (2d+1 )

in both cases - o(log n ) ( as d will be small )

am i correct ?

Answer 4

For n leaves, there must be exactly n-1 keys distributed in the internal nodes.
As per the question, each node can have keys between d and 2d. Therefore for n-1 keys there can be minimum $\lceil$$\dfrac{n-1}{2d}$$\rceil$ internal nodes and maximum $\lceil$$\dfrac{n-1}{d}$$\rceil$ internal nodes.

To determine upper bound on the number of nodes accessed during the search, let us take the maximum case.

In this $B^+$-tree every level will contain nodes in the powers of (d+1), so the equation of height is,
1 + (d+1) + $(d+1)^2$ + $(d+1)^2$ +.....+ $(d+1)^{h-1}$ = $\dfrac{n-1}{d}$
$\implies$ $\dfrac{(d+1)^{h}-1}{(d+1)-1}$ = $\dfrac{n-1}{d}$
$\implies$ $(d+1)^h$ = n
$\implies$ h = $log_{(d+1)}n$

Now using h, leaf node containing key being searched can be reached. Hence the number of nodes accessed during the search is O($log_{(d+1)}n$)

Comments

wat is the difference between u and sachin's answer ??

---

https://gateoverflow.in/?qa=blob&qa_blobid=13488428153385853655