Past exam question: 2063 Baishakh (Regular / Back), Q4
Open in the Padhaiko appQuestion
Discuss the application of multiway search tree. Define B-tree. Using the insertion algorithm of B tree. Create 3-order B tree for the given sequence of date. 8,14,2,15,3,1,12,6,5
Solution
Applications of Multi-Way Search Trees & Definition of B-Tree:
- Applications: Database indexing (B-Tree / B+ Tree in MySQL, PostgreSQL), file-system directory trees (ext4, NTFS, Btrfs), and external disk-resident dictionaries where minimizing slow disk block reads is critical.
- B-Tree of Order : A balanced multi-way search tree where each node holds at most sorted keys and children, each internal non-root node holds at least children ( keys), and all leaves lie at the exact same depth.
Order-3 B-Tree (2-3 Tree, Max 2 Keys/Node) Construction for 8, 14, 2, 15, 3, 1, 12, 6, 5:
- Insert
8, 14:[8, 14](full). - Insert
2:[2, 8, 14]overflows promote median8: root[8], leaves[2],[14]. - Insert
15:[14, 15]. - Insert
3:[2, 3]. - Insert
1:[1, 2, 3]overflows promote2to root[2, 8]; leaves[1],[3],[14, 15]. - Insert
12:[12, 14, 15]overflows promote14into root[2, 8, 14]! Root overflows promote8to new root[8]:[8] -> ([2] -> [1], [3])and([14] -> [12], [15]). - Insert
6:[3, 6]. - Insert
5:[3, 5, 6]overflows promote5to[2, 5]; leaves under[2, 5]are[1],[3],[6].
[8]
/ \
[2, 5] [14]
/ | \ / \
[1] [3] [6] [12] [15]Answer:
Multi-way search trees power database/file-system indexing by minimizing disk reads. Final 3-order B-tree: root [8], level-1 [2, 5] and [14], leaves [1], [3], [6], [12], [15].