B+ Trees & Disk Indexing
Subject: Database Management Systems
High-yield database disk indexing structure using B+ Trees.
Concept Summary
In relational databases (like PostgreSQL, MySQL, Oracle), B+ Trees are the gold standard for disk indexing. Unlike standard B-Trees where data pointers are scattered across internal nodes, B+ Trees store all record pointers in leaf nodes. Because the leaf nodes are linked sequentially, scanning a range of keys (e.g., `WHERE age BETWEEN 20 AND 30`) simply traverses the leaf linked list without re-traversing the tree structure.
Key Revision Rules & Formulas
- B+ Trees store all actual data pointers exclusively in linked leaf nodes.
- Internal nodes store only search keys and child node pointers, keeping index height small.
- Leaf nodes form a doubly-linked list enabling fast O(log N + K) range scans.
- Ideal for disk-based databases because block I/Os are minimized.
Common Exam Pitfalls
- Mistaking B-Tree for B+ Tree: B-Trees store data pointers in internal nodes; B+ Trees store data ONLY in leaf nodes.
- Assuming B+ Tree height increases rapidly: Binary tree height is log2(N), but B+ Trees have large fanout (order > 100), keeping height small (typically 3–4 levels).
Sample Practice Questions
Question 1: Why are B+ Trees preferred over B-Trees for disk-based database indexing?
- Data pointers are stored in root node only
- Leaf nodes store all data & are linked sequentially for fast range queries
- B+ Trees have lesser height than binary trees
- B+ Trees eliminate key duplication
Explanation: B+ Trees store all actual data pointers in linked leaf nodes, enabling efficient sequential range scans and fewer disk I/Os.