edited by
7,928 views
36 votes
36 votes
Consider a B-tree with degree $m$, that is, the number of children, $c$, of any internal node (except the root) is such that $m \leq c \leq 2m-1$. Derive the maximum and minimum number of records in the leaf nodes for such a B-tree with height $h, h \geq 1. ($Assume that the root of a tree is at height $0).$
edited by

2 Answers

Best answer
55 votes
55 votes

Given a $B$ tree :

  • max children at a node $: 2m - 1 \implies$  max keys : $2m -2$
  • min children at a node $:  m \implies$ min keys :   $m -1$

At Root node :   min keys $: 1 \implies $ min children $: 2$

Here, leaf level is at level $\bf{h}$ (because root is at level $\bf{0}$)

Now, we have to find

  1. Minimum keys at leaf level(complete bottommost level, not just a node ) -  
    • For this, we have to consider minimum everywhere.
    • Firstly we will count the minimum possible nodes at the leaf level.
    • At Root Node (level $\bf{0}$) : It can have minimum $2$ child (mean $2$ nodes minimum for next level)
    • At level 1: It has $2$ nodes, each can have a minimum of $m$ child (so, this gives  $2 \ast m$  minimum possible nodes at next level )
    • At level $2:$ min $2 \ast m^2$  Child and so on.
    • At level $(h-1)$ $: 2 \ast (m)^{h-1}$   child (these are min number of leaf nodes possible )
    • At level $h$(leaf level) $:  2 \ast (m)^{h-1}$  nodes each having minimum $(m-1)$ keys. So, this gives the answer as  $\bf{2 \ast (m)^{h-1} \ast (m-1)}$ minimum keys possible at leaf level.                             
  1.  Maximum keys at leaf level(complete bottommost level, not just a node ) -   
    •  For this, we have to count max everywhere.
    • At root (level 0) : max child possible  $2m-1$   (nodes for next level)
    • At level $1$ $:  2m-1$ nodes give  $(2m-1)^2$  child
    • At level $(h-1)$ $: (2m-1)^h$  child (these are maximum possible nodes at leaf level)
    • At level $h$ (leaf level) $: (2m-1)^h$  nodes  each having a maximum of $(2m-2)$ keys. Giving a total of - $\bf{(2m-1)^h * (2m-2) } $  maximum keys at leaf level. 
edited by
0 votes
0 votes
as per me -
 
for max records- max no of leaf nodes and max no of records per node -
so ( 2m-1 )^h * (2m-2)
 
for min nodes- min no fo leaf nodes * min no of records per node
 
for min nodes - all nodes at height h-1 and just 1 node at height h
so ( m^(h-1) -1 +1 ) * ( m -1) = m^(h-1) * (m-1)
 
Any mistake in this?

Related questions

35 votes
35 votes
3 answers
1
29 votes
29 votes
3 answers
3
Kathleen asked Sep 23, 2014
11,434 views
The maximum gate delay for any output to appear in an array multiplier for multiplying two $n$ bit numbers is$O(n^2)$$O(n)$$O(\log n)$$O(1)$