The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 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 (52.1k points)
edited by | 2.6k 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

+33 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}$ (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 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.4k 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?
When the question already says "Consider a B-tree with degree mm, that is, the number of children, cc, of any internal note (except the root) is such that m≤c≤2m−1m≤c≤2m−1. "

I want to downvote this answer, because the answer assumes same degree for the root node for the maximum case, it doesn't make sense. if you don't agree please explain why it's correct.
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 (771 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
49,814 questions
54,518 answers
75,288 users