The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+19 votes
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).
asked in Databases by Veteran (59.6k points)
edited by | 2.1k 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)


Degree of B tree: Minimum number of children a B tree node should have

Order: Maximum number of children a B tree node can have.

The question is saying that the B tree has degree m. So max children is 2m-1

2 Answers

+31 votes
Best answer

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 $\bf{h}$ (becz 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 minimum possible nodes at 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 minimum  $m$ child (so , this

                                gives  $2 * m$  minimum possible nodes at next level )

       At level 2 :   min $2 * m^2$      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  $\bf{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 - $\bf{(2m-1)^h * (2m-2) } $  maximum keys at leaf level. 

answered by Boss (15.5k points)
edited by

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 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.

How max number of child nodes of a leaf is 2m-1 , in question the child node between m and 2m-1 except for the root so how you take 2m-1(max childs) for root?
Did you get this how it is taking 2m-1 max nodes for root node?
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?
answered by Junior (783 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,903 questions
47,560 answers
62,306 users