Past exam question: 2065 Shrawan (Regular / Back), Q6
Open in the Padhaiko appQuestion
Define B-tree. ... and also discuss the efficiency of multi-waytree.
Solution
Definition of B-Tree of Order : A B-Tree of order is a self-balancing multi-way search tree in which:
- Every node has at most children and sorted keys.
- Every internal node (except the root) has at least children and keys.
- The root has at least 2 children if it is not a leaf.
- All leaves lie at the exact same level.
Efficiency of Multi-Way Search Trees (B-Trees):
- Logarithmic Height with Base : With keys and branching factor , height is instead of . For and , a binary tree needs levels whereas a B-tree needs only – levels.
- Minimized Disk I/O: Each node fits one disk block/page, so searching, inserting, or updating requires only a tiny constant number of slow secondary-storage reads/writes.
Answer:
A B-tree of order is a balanced -way search tree with all leaves at uniform depth. Multi-way branching compresses height to , dramatically minimizing disk I/O operations compared to binary trees.