B & B+ Trees, Multi-Level Indexing & Disk I/O Arithmetic
“Internal and leaf node order inequalities, B+ tree splits, and disk I/O calculations.”
1.The Disk I/O Bottleneck
§ 6.1.Main memory access takes ~100 nanoseconds; reading a disk block takes ~5-10 milliseconds (50,000× slower!). An enterprise table with 10 million rows cannot be scanned sequentially on every query.
Indexing creates balanced multi-level search trees on disk that reduce search complexity from linear O(N) block scans to O(log_p N) disk block transfers. In real systems, a B+ Tree with height 3 can index billions of records while requiring only 3 disk reads to locate any record.
2.B-Tree vs B+ Tree: Why B+ Trees Rule Databases
§ 6.2.Modern database engines (MySQL InnoDB, PostgreSQL, Oracle) exclusively use B+ Trees rather than standard B-Trees.
The Core Difference:
• Standard B-Tree: Stores keys AND actual data record pointers in both internal nodes and leaf nodes. Because record pointers take up space in internal nodes, the fanout (node order p) is small, resulting in taller trees and more disk I/Os.
• B+ Tree: Stores ONLY search keys and block pointers in internal nodes. All data record pointers reside strictly in the leaf nodes. Furthermore, all leaf nodes are connected via a doubly-linked list.
Why B+ Trees are Superior:
1. Massive Fanout: Internal nodes don't store record pointers, allowing many more keys per disk block (higher order p), yielding shallower trees.
2. Blazing Range Queries: Finding values between ₹10,000 and ₹50,000 in a B-Tree requires costly in-order tree traversal across random disk blocks. In a B+ Tree, search locates the first leaf block, then simply walks the linked list horizontally along contiguous disk blocks.
3. Interactive B+ Tree Order & Capacity Calculator
Enter your disk block size, key size, and pointer sizes to solve the exact algebraic inequalities for internal and leaf node orders and compute tree height and I/O costs.
B+ Tree Node Order & Capacity Calculator
Solves p * P_b + (p - 1) * Key <= BlockSize and leaf inequalities.
Formula Inequality:
p · Pb + (p − 1) · K ≤ B
With values plugged in:
p · 8 + (p − 1) · 10 ≤ 512
⇒ p · 18 ≤ 522 ⇒ p = 29
Formula Inequality:
m · (K + Pr) + Pb ≤ B
With values plugged in:
m · (10 + 8) + 8 ≤ 512
⇒ m · 18 ≤ 504 ⇒ m = 28
Multi-level Index Search Performance for Table
4. GATE Classic: B+ Tree Node Order Numerical
| Block Size (B)512 Bytes | Search Key (K)10 Bytes | Block Pointer (Pb)8 Bytes | Record Pointer (Pr)8 Bytes |
An internal node of order p contains p block pointers and (p - 1) search keys. Total size cannot exceed block size B.
A leaf node stores m search key-record pointer pairs and 1 block pointer to the next leaf node.
5. B+ Tree Indexing Quiz
Test your understanding of tree height and node split bounds.
In a B+ Tree where internal nodes have maximum order p = 10, what is the minimum number of keys an internal node (other than root) must contain?
6. 1-Minute B+ Tree Revision Card
“B+ Tree: Keys only in internal nodes; keys + data pointers in leaves; leaves linked horizontally.”
- •Internal order inequality: p · Pb + (p - 1) · K ≤ B.
- •Leaf order inequality: m · (K + Pr) + Pb ≤ B.
- •Min keys non-root internal: ⌈p/2⌉ - 1. Min keys non-root leaf: ⌈m/2⌉.
- •Root min keys: 1 key (2 pointers). Max keys: p - 1.
- •Disk I/Os for search = Height + 1 (Height index blocks + 1 data block).
- •In internal nodes, pointers are p and keys are p - 1; in leaf nodes, pointers and keys are both m (plus 1 next block pointer).
- •Range queries in B+ Trees do not traverse back up to the root; they walk horizontally along the leaf pointers.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
The classic paper defining B-tree variants, split mechanics, and storage efficiency.
Standard reference for B+ tree insertion splits, deletion borrow/merges, and order algebra.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-focused numerical problem-solving with clear worked examples.
Fast conceptual coverage with step-by-step GATE numericals.
Systematic textbook-style explanations ideal for first-time learners.
Deep theoretical rigor on normalization and transaction serializability.