Chapter 9
Q. 9.FAQ.1
Construct a B-tree of order 5 and insert the following values into it:
Values to be inserted – B, N, G, A, H, E, J, Q, M, D, V, L, T, Z
Step-by-Step
Verified Solution
1. Since order = 5, we can store at least 3 values and at most 4 values in a single node. Hence, we will insert B, N, G, A into the B-tree in sorted order.
2. Now H is to be inserted between G and N, so now the order will be A B G H N, which is not possible, as at most 4 values can be accommodated in a single node. So now we will split the node, and the middle element G will become the root node.
3. Now we will insert E J and Q into the B-tree.
4. M is to be inserted in the right subtree. But at most 4 values can be stored in the node, so now we will push the middle element, that is, M, into the root node. Thus, the node is split into two halves.
5. Now we will insert D V L T into the tree.
6. Finally, Z is to be inserted. It will be inserted in the right subtree. Hence, the last node will split into two halves, and the middle element, that is, T, will push up to the root node.





