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