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.4k points)
edited by | 2k 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

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

answered by Boss (15.2k points)
selected 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.

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 (765 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

35,507 questions
42,829 answers
42,183 users