1.9k views
Consider a B-tree with degree $m$, that is, the number of children, $c$, of any internal note (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 | 1.9k views

For maximum no of records in leaf node-

Root can have a max of m child Thus at h=1 no of leaf nodes would be m

Each of internal node can have a maximum of 2*m-1 child thus for h=2 no of leaf nodes would be m*(2m-1)

For h=3 max no of leaf nodes=m*((2m-1)^2)

So for a general expression max no of leaf nodes =m *((2m-1)^h-1)

Please correct me if i am wrong...

How is it possible for a node of B-Tree to have a children more than m?

A​nswer I am getting is -

minimum records in leaf nodes  =  2 * (m) h - 1 * (m-1)

maximum records in leaf nodes =  (2m-1)h * (2m-2)

Given a B tree :

max children at a node : 2m - 1             =>         max keys : 2m -2

min children at a node :  m                    =>         min keys :   m -1

At Root node :    min keys : 1       min children :  2

Here , leaf level is at level h (becz root is at level 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 minimum possible nodes at leaf level.

At Root Node (level 0) :   It can have minimum 2 child (mean 2 nodes

minimum for next level)

At level 1 :  It has 2 nodes , each can have minimum  m child (so , this

gives  2 * m  minimum possible nodes at next level )

At level 2 :   min 2 * m2      Child   and so on.

At level (h-1) :    2 * (m) h - 1  child (these are min number of leaf nodes possible )

At level h(leaf level) :    2 * (m) h - 1  nodes each having minimum (m-1) keys.

So, this gives the answer as  2 *(m) h - 1 * (m-1) minimum keys

possible at leaf level.

2) 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 - (2m-1)h * (2m-2)  maximum keys at leaf level.

selected

it is given that for all internal nodes(except root node)m ≤ no. of children ≤ 2m−1,

but what should be the max no. of children for a root node? In general we know that

2<= no. of children of a root node<=order of B-tree i.e m.

So, the root node can have max m children,

how did u take max children of root node as (2m-1)???

But it says any node except root node will follow this condition....how are u taking maximum child in leaf to be 2m-1?

As when B tree have B=2 it can have maximum of 2B-1 i.e 3  children

But when B=10 I cant able to visualise  how it can adjust 19 children, I can only see if there is only 10 children . Please anyone give me a picture view.

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?