edited by
4,690 views
3 votes
3 votes
What is the maximum number of records that can be indexed in B+ tree of level $4$ ,order $10$ where root is at level $1$ ?

As the order of tree is $10$, nodes in the last level of b+ tree should contain $10$ record pointers (number of record pointers = order of leaf node). So I think that answer should be $ \big(10\big) \big(10\big) \big(10\big)\big(10\big)= 10,000$.

But the answer given is $\big(10\big)\big(10\big)\big(10\big)\big(9\big) = 9000$ considering that leaf nodes contain only $10-1 = 9$ record pointers.

Which one is correct?
edited by

2 Answers

1 votes
1 votes
b+ tree have each record pointer in leaf here at level 4

root have 10 child means level 2 have 10 block

each node at level 2 have 10 child

means level 3 have 100 node

at level 3 each have 10 child

means level 4 have 1000 node

each node can store (order-1)=9 record pointer and key

so , max no of record pointer in tree =9000
0 votes
0 votes

The order, or branching factor, b of a B+ tree measures the capacity of nodes (i.e., the number of children nodes) for internal nodes in the tree. The actual number of children for a node, referred to here as m, is constrained for internal nodes so that ${\displaystyle \lceil b/2\rceil \leq m\leq b}$. The root is an exception: it is allowed to have as few as two children. For example, if the order of a B+ tree is 7, each internal node (except for the root) may have between 4 and 7 children; the root may have between 2 and 7. Leaf nodes have no children, but are constrained so that the number of keys must be at least ${\displaystyle \lceil b/2\rceil }$ and at most ${\displaystyle b}$.

Source – https://en.wikipedia.org/wiki/B%2B_tree#Overview

Every node of the B+-tree except the root node is at least half-filled.

This condition can be formulated more exactly: denote by s(x) the number of children of node x if x is a non-leaf node and the number of keys stored in x if x is a leaf node.

Source – https://www.cs.helsinki.fi/u/mluukkai/tirak2010/B-tree.pdf

So, the answer should be:

$= \text{(Number of leaf nodes) * (Maximum Records/Leaf node)}$

$= 10^3 * 10$

$= 10000$

Related questions

0 votes
0 votes
3 answers
1
Na462 asked Feb 2, 2019
2,043 views
3 votes
3 votes
2 answers
2
Himanshu1 asked Jan 2, 2016
831 views
0 votes
0 votes
1 answer
3
Salazar asked Jan 29, 2018
3,934 views
Maximum height of a B+ tree of order m with n key values is (With Derivation), the answer is known Logceil(m/2) NI tried deriving but had some trouble, could someone assi...
0 votes
0 votes
1 answer
4
Vishnathan asked Aug 24, 2018
8,183 views