Past exam question: 2064 Jestha, Q5
Open in the Padhaiko appQuestion
Define B-tree and construct the B-tree for order 5 (i.e. M = 5) for given sequence of data 1,7,6,2,11,4,8,13,10,5,19,9,18,24,3,12,14,20,21,16 showing each steps.
Solution
Definition of Order-5 B-Tree: A B-Tree of order is a balanced multi-way search tree where every node has at most children and sorted keys, every internal node (except root) has at least children and keys, and all leaf nodes lie at the same depth.
Step-by-Step Construction (1, 7, 6, 2, 11, 4, 8, 13, 10, 5, 19, 9, 18, 24, 3):
1, 7, 6, 2[1, 2, 6, 7](full).+11[1, 2, 6, 7, 11]splits at median6root[6], leaves[1, 2],[7, 11].+4[1, 2, 4].+8, +13[7, 8, 11, 13](full).+10[7, 8, 10, 11, 13]splits at10root[6, 10], leaves[1, 2, 4],[7, 8],[11, 13].+5[1, 2, 4, 5];+19[11, 13, 19];+9[7, 8, 9].+18[11, 13, 18, 19](full).+24[11, 13, 18, 19, 24]splits at18root[6, 10, 18], leaves[11, 13],[19, 24].+3[1, 2, 3, 4, 5]splits at3root[3, 6, 10, 18](root full!), leaves[1, 2],[4, 5],[7, 8, 9],[11, 13],[19, 24].
Insert 12, 14, 20, 21, 16 (Root Split):
+12, +14[11, 12, 13, 14];+20, +21[19, 20, 21, 24].+16[11, 12, 13, 14, 16]splits at13, promoting13into full root[3, 6, 10, 13, 18], which splits at median10into new root[10]:
[10]
/ \
[3, 6] [13, 18]
/ | \ / | \
[1,2] [4,5] [7,8,9] [11,12] [14,16] [19,20,21,24]Answer:
Final order-5 B-tree: root [10], internal nodes [3, 6] and [13, 18], leaves [1, 2], [4, 5], [7, 8, 9], [11, 12], [14, 16], [19, 20, 21, 24].