Past exam question: 2078 Poush (Back), Q5
Open in the Padhaiko appQuestion
Define B-tree with its properties. construct a B-tree of order 5 from the following data: 1, 7, 6, 2, 11, 4, 8, 13, 10, 5, 19, 9, 18, 24, 3, 12, 14, 20, 21, 16
Solution
Definition and Properties of a B-Tree of Order : A B-Tree of order is a self-balancing multi-way search tree optimized for disk-based storage:
- Every node has at most children and at most keys (for : max 4 keys, max 5 children).
- Every internal node (except the root) has at least children and keys (for : min 3 children, min 2 keys).
- The root has at least 2 children if it is not a leaf.
- All leaf nodes appear at the exact same depth.
- Keys inside each node are sorted in ascending order and partition child subtrees.
Insertions 1, 7, 6, 2, 11 (First Split):
- Insert
1, 7, 6, 2: single leaf[1, 2, 6, 7](full with 4 keys). - Insert
11:[1, 2, 6, 7, 11]overflows! Promote median6to new root:
[6]
/ \
[1, 2] [7, 11]Insertions 4, 8, 13, 10, 5, 19, 9, 18, 24, 3:
- Insert
4:[1, 2, 4]left leaf. - Insert
8, 13: right leaf becomes[7, 8, 11, 13](full). - Insert
10: right leaf[7, 8, 10, 11, 13]overflows promote10to root[6, 10]; leaves:[1, 2, 4],[7, 8],[11, 13]. - Insert
5:[1, 2, 4, 5](full). - Insert
19:[11, 13, 19]. - Insert
9:[7, 8, 9]. - Insert
18:[11, 13, 18, 19](full). - Insert
24:[11, 13, 18, 19, 24]overflows promote18to root[6, 10, 18]; rightmost leaves:[11, 13],[19, 24]. - Insert
3:[1, 2, 3, 4, 5]overflows promote3to root[3, 6, 10, 18](root now full); leaves:[1, 2],[4, 5],[7, 8, 9],[11, 13],[19, 24].
Insertions 12, 14, 20, 21, 16 (Leaf and Root Split):
- Insert
12, 14: leaf[11, 12, 13, 14](full). - Insert
20, 21: leaf[19, 20, 21, 24](full). - Insert
16: goes to[11, 12, 13, 14, 16]overflows! Promote median13into root[3, 6, 10, 13, 18]. Now the root overflows! Promote median10to a brand-new root:
[10]
/ \
[3, 6] [13, 18]
/ | \ / | \
[1,2] [4,5] [7,8,9] [11,12] [14,16] [19,20,21,24]Answer:
Final B-tree of order 5 (height 3):
- Root:
[10] - Level 1:
[3, 6]and[13, 18] - Leaves:
[1, 2],[4, 5],[7, 8, 9](under[3, 6]);[11, 12],[14, 16],[19, 20, 21, 24](under[13, 18]).