B-Trees, B+ Trees & Disk Indexing theory

Computer memory architectures are fundamentally governed by physical and economic constraints on latency and bandwidth.



1. The Memory Latency Gap:

- CPU Registers & L1/L2/L3 Caches: Operate at 0.5 to 10 nanoseconds, embedded directly onto the processor die;

- DRAM (Main Memory): Operates at 50 to 100 nanoseconds, limited by bus capacitance and row precharge delays;

- Solid-State Drives (NVMe Flash): Operate at 10 to 50 microseconds (10,000 to 50,000 ns), reading data in 4KB or 8KB flash pages;

- Hard Disk Drives (HDD): Operate at 5 to 10 milliseconds (5,000,000 to 10,000,000 ns) due to mechanical arm seek and rotational latency.

Secondary storage is between 100× (SSD) and 100,000× (HDD) slower than DRAM!



2. The Disk Access Machine (DAM) Model:

Formulated by Alok Aggarwal and Jeffrey Vitter in 1988, the DAM model formalizes external memory computation:

- Data resides on high-capacity secondary storage partitioned into blocks of size B (e.g., 4096 bytes);

- Internal memory can hold M elements (M/B blocks);

- CPU computation on data resident in internal memory is modeled as free; the performance metric is strictly the number of Block I/O transfers between disk and memory.



3. Catastrophic Breakdown of Binary Search Trees in External Memory:

In a balanced binary search tree (AVL or Red-Black tree) storing N records:

- Each node contains only 1 key and 2 child pointers (consuming ~32 bytes). An entire 4096-byte disk block would be loaded to access a single 32-byte node, wasting 99.2% of transfer bandwidth!

- Tree height is h ≈ log₂(N). For N = 16,777,216 records, h = 24 levels. Searching for a record requires 24 random block reads. On an HDD, 24 seeks take 24 × 10 ms = 240 ms per query (only 4 queries/sec)! B-Trees solve this by packing hundreds of keys into every 4KB block, reducing tree height to 3 levels.

In 1970, Rudolf Bayer and Edward M. McCreight defined the B-Tree as a balanced multi-way search tree characterized by a minimum degree parameter t ≥ 2.



1. The Formal B-Tree Invariants:

For a B-Tree of minimum degree t:

- Invariant 1 (Key Ordering): Every node x contains n[x] sorted keys: key₁[x] ≤ key₂[x] ≤ ... ≤ key_{n[x]}[x]. If x is an internal node, it contains n[x] + 1 child pointers c₁[x], c₂[x], ..., c_{n[x]+1}[x];

- Invariant 2 (Search Range Partitioning): The keys in child subtree c_i[x] fall strictly within the range bounded by key_{i-1}[x] and key_i[x];

- Invariant 3 (Node Capacity Bounds):

* Every internal node other than the root has at least t - 1 keys and at least t children;

* Every node can contain at most 2t - 1 keys (and 2t children). A node with 2t - 1 keys is termed full;

* The root must contain at least 1 key if the tree is non-empty;

- Invariant 4 (Uniform Leaf Depth): All leaf nodes reside at the exact same depth h, guaranteeing perfect global balance.



2. Tree Height Bound:

In the worst case where every node contains the minimum allowable number of keys (t - 1):

- The root has 1 key and 2 children;

- At depth 1, there are 2 nodes, each with t children (2t children total);

- At depth d, there are 2 · t^{d-1} nodes;

Summing keys across all levels shows that for N keys, the tree height is strictly bounded by:

h ≤ ⌊log_t ((N + 1) / 2)⌋ + 1.

For t = 128 (order m = 256), a tree of height h = 3 can store over 4.2 million keys, and height h = 4 can store over 540 million keys!

While classical B-Trees store data records in both internal nodes and leaves, the B+ Tree (developed in the late 1970s) introduces an architectural separation that optimizes secondary storage access.



1. Structural Differences Between B-Trees and B+ Trees:

- Internal Node Segregation: In a B+ Tree, internal nodes store strictly index keys and child page pointers—they NEVER store user data records! Internal nodes serve purely as a multi-way routing index;

- Data Concentration in Leaves: Every actual payload data record resides exclusively in the leaf nodes. Keys appearing in internal routing nodes are duplicated in the leaves;

- Doubly-Linked Sequential Leaf Chain: All leaf nodes are linked sequentially into a bidirectional linked list (prev_page and next_page pointers).



2. Why B+ Trees Outperform Classic B-Trees in Production:

- Higher Fanout (Shallower Trees): Because internal nodes do not store bulky data payloads (which can be hundreds of bytes), a 4KB internal page can hold vastly more keys and pointers. For 16-byte index entries vs 256-byte data records, fanout jumps from m = 16 to m = 256, cutting tree height in half;

- Blazing Range Queries (SELECT WHERE x BETWEEN a AND b): In a classic B-Tree, a range scan requires an in-order tree traversal, continually ascending and descending parent/child pointers (causing random disk seeks). In a B+ Tree, the database navigates down to the first leaf in O(log_B N) time, then simply walks the sequential linked list at leaf level at raw sequential I/O speeds (e.g. 5000 MB/s on NVMe SSDs);

- Predictable Search Latency: Every single search query traverses exactly h levels to reach a leaf, ensuring uniform predictable query response times.

When a 4KB disk block is transferred into the buffer pool, the CPU must efficiently locate the correct child branch pointer among the sorted keys resident in that page.



1. 4KB Disk Page Memory Layout:

A standard database index page (e.g. in MySQL InnoDB or PostgreSQL) contains:

- Page Header (64 bytes): Stores Page ID, LSN (Log Sequence Number), level, and key count;

- Contiguous Sorted Key Array: For order m = 256, the page contains 255 8-byte keys = 2040 bytes;

- Child Pointer Array: 256 8-byte page IDs = 2048 bytes;

Total page size = 64 + 2040 + 2048 = 4152 bytes (aligned to 4KB / 8KB boundary).



2. In-Page Search Mechanics: Linear Scan vs Binary Search:

- Linear Scan: Inspecting keys sequentially requires an average of 128 comparisons per node, wasting CPU cycles;

- Binary Search: Because keys are stored in a contiguous sorted array, the CPU performs binary search over the 255 keys. Because 255 < 2⁸ = 256, binary search is mathematically guaranteed to terminate in exactly:

k = ⌈log₂(255 + 1)⌉ = log₂(256) = 8 scalar key comparisons!



3. Asymptotic Search Complexity Derivation:

Across an entire search traversal path from root to leaf across a tree of height h levels:

- The algorithm visits exactly h distinct 4KB disk pages;

- Inside each page, binary search executes exactly 8 comparisons;

- Therefore, the cumulative key comparison count across the search path is strictly:

C(h) = 8.0000 · h + 0.0000 comparisons,

providing the exact linear regression invariant verified in this laboratory!

B-Trees and B+ Trees maintain perfect balance dynamically without ever requiring global restructuring.



1. Proactive Node Splitting on Insertion:

When inserting a new key into a B-Tree:

- A naive approach traverses to the leaf and inserts. If the leaf has 2t - 1 keys (full), it splits, which can cause a cascading split back up to the root, requiring multi-pass locking;

- Proactive Pre-Splitting (Single-Pass Top-Down): As the algorithm descends the tree during insertion, whenever it encounters any node with 2t - 1 keys, it splits that node IMMEDIATELY before continuing downward!

- Mechanics of a Split: A full node with 2t - 1 keys is split around its median key (key_t):

* Left node retains keys key₁ to key_{t-1};

* Median key key_t is promoted to the parent node;

* Right node receives keys key_{t+1} to key_{2t-1};

Because the parent was guaranteed not full on the way down, the promoted median key always fits! If the root splits, a new root is created with 1 key and 2 children, increasing tree height by exactly 1.



2. Node Merging and Redistribution on Deletion:

When a key is deleted and a node's key count drops below the minimum threshold t - 1 (underflow):

- Borrowing (Redistribution): If an immediate sibling node has ≥ t keys, borrow a key via rotation through the parent node;

- Merging: If both left and right siblings have only t - 1 keys, merge the node with a sibling and pull down the separating key from the parent. If the parent becomes empty, the tree height shrinks by 1.

Relational database engines cannot afford to execute synchronous disk writes on every transactional modification.



1. The Buffer Pool Architecture:

The Buffer Pool is a dedicated region of main memory (DRAM) managed by the database engine (e.g. innodb_buffer_pool_size):

- Partitioned into fixed-size frames (matching the 4KB or 16KB disk page size);

- When a page is requested, the buffer manager checks the Page Table (a hash map). If present (Cache Hit, ~50 ns), the page is pinned in memory;

- If absent (Cache Miss), an I/O read is issued to secondary storage, and an existing unpinned page is evicted using LRU (Least Recently Used) or Clock replacement policies.



2. Dirty Pages and Asynchronous Flushing:

When an UPDATE or INSERT modifies a B+ Tree page in the buffer pool, the page is marked as Dirty. Writing the modified 4KB page back to disk immediately would require random synchronous I/O, destroying write throughput. Instead, dirty pages are buffered in memory and flushed to disk asynchronously by background threads.



3. Write-Ahead Logging (WAL) & ARIES Protocol:

If the server loses power while dirty pages reside only in DRAM, data would be permanently lost, violating ACID Durability! Write-Ahead Logging (WAL) resolves this dilemma:

- The WAL Invariant: Before any dirty page can be written to disk, and before any transaction commits, a sequential append-only log record describing the delta change MUST be flushed to disk (fsync);

- Sequential log writes execute orders of magnitude faster than random 4KB page writes;

- Crash Recovery (ARIES): Upon reboot, the engine scans the WAL log: Redo re-applies all committed changes to B+ Tree pages, and Undo rolls back uncommitted transactions, guaranteeing 100% data integrity.

In modern big data engineering, B+ Trees and LSM-Trees represent two contrasting storage architectures optimized for different workload profiles.



1. The B+ Tree Trade-Off Profile:

- Optimized for Read-Heavy Workloads & Point Lookups: Navigating 3 or 4 levels delivers guaranteed O(log_B N) read latency;

- Write Amplification on Random Updates: Modifying a single 32-byte record requires reading and rewriting an entire 4KB or 16KB disk page. On flash storage (SSDs), in-place updates cause high Write Amplification Factors (WAF = 10 to 30) and flash memory cell wear;

- Dominates Traditional RDBMS: MySQL InnoDB, PostgreSQL, SQLite, Oracle.



2. The Log-Structured Merge-Tree (LSM-Tree) Architecture:

Invented by Patrick O'Neil et al. (1996), LSM-Trees eliminate in-place page overwrites:

- MemTable (DRAM): All incoming writes (INSERT, UPDATE, DELETE) are appended sequentially to a WAL and inserted into an in-memory sorted SkipList or Red-Black tree;

- SSTables (Disk): When the MemTable fills, it is flushed sequentially to disk as an immutable Sorted String Table (SSTable) at Level 0;

- Compaction: Background threads merge-sort overlapping SSTables into deeper levels (Level 1, Level 2), eliminating duplicate and deleted keys;

- Trade-Off: Writes execute at raw sequential disk speed (ultra-low write amplification), but reads must inspect multiple SSTables across levels (mitigated using Bloom Filters);

- Dominates Distributed NoSQL & Modern Storage: RocksDB, Apache Cassandra, Google Bigtable, ScyllaDB, CockroachDB.