The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+18 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).

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

+28 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 * 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 **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.

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)???

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?

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 284
- Exam Queries 397
- Tier 1 Placement Questions 17
- Job Queries 51
- Projects 7

33,705 questions

40,252 answers

114,345 comments

38,862 users