PadhaikoAll subjects

Past exam question: 2065 Shrawan (Regular / Back), Q6

Data Structure and Algorithms · 4 marks

Open in the Padhaiko app

Topic: Balanced binary tree · Introduction to red-black tree · B-Tree: Need…

Question

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:

  1. Every node has at most children and sorted keys.
  2. Every internal node (except the root) has at least children and keys.
  3. The root has at least 2 children if it is not a leaf.
  4. All leaves lie at the exact same level.

Efficiency of Multi-Way Search Trees (B-Trees):

  1. 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.
  2. 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.

All past exam questions for Data Structure and Algorithms