3,445 views

5 Answers

Best answer
61 votes
61 votes

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

6 votes
6 votes
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)
edited by
2 votes
2 votes
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 ?
1 votes
1 votes
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$)

Related questions

29 votes
29 votes
1 answer
1
Kathleen asked Oct 5, 2014
7,339 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
3
Kathleen asked Oct 5, 2014
6,884 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
4
Kathleen asked Oct 5, 2014
7,575 views
State True or False with reasonLogical data independence is easier to achieve than physical data independence.