Past exam question: 2075 Baisakh (Back), Q6(b)
Open in the Padhaiko appQuestion
Construct a B-tree of order 5 for following data: 82, 12, 22, 23, 56, 96, 37, 99, 59, 74, 28, 65, 60 and 44.
Solution
Order-5 B-Tree Rules & Insertions 82, 12, 22, 23, 56: Order max 4 keys per node, min 2 keys (except root).
- Insert
82, 12, 22, 23: root leaf[12, 22, 23, 82](full). - Insert
56:[12, 22, 23, 56, 82]overflows! Promote median23:
[23]
/ \
[12, 22] [56, 82]Insertions 96, 37, 99, 59, 74:
- Insert
96, 37: right leaf becomes[37, 56, 82, 96](full). - Insert
99:[37, 56, 82, 96, 99]overflows promote median82to root[23, 82]; leaves:[12, 22],[37, 56],[96, 99]. - Insert
59, 74: middle leaf becomes[37, 56, 59, 74](full).
Insertions 28, 65, 60, 44:
- Insert
28: middle leaf[28, 37, 56, 59, 74]overflows promote median56to root[23, 56, 82]; leaves:[12, 22],[28, 37],[59, 74],[96, 99]. - Insert
65, 60: leaf[59, 60, 65, 74](full). - Insert
44: leaf[28, 37, 44](fits cleanly).
[23, 56, 82]
/ | | \
[12, 22] [28,37,44] [59,60,65,74] [96, 99]Answer:
Final order-5 B-tree (height 2):
- Root:
[23, 56, 82] - Leaves:
[12, 22],[28, 37, 44],[59, 60, 65, 74],[96, 99].