B-Trees, B+ Trees & Disk Indexing lab report

1. Title and aim

B-Trees, B+ Trees & External Memory Disk Indexing: Multi-Way Balanced Search, Block I/O Alignment, and Secondary Storage Optimization. To investigate external memory algorithms and the Disk Access Machine (DAM) model, analyze multi-way search trees across fanout orders m = 256, evaluate B-Trees against B+ Trees and Binary Search Trees (BST), verify block I/O alignment and in-page binary search within 4KB disk pages, and empirically demonstrate the linear in-node comparison law C(h) = k_node · h + C_0 = 8.0000 · h + 0.0000 comparisons across tree heights h ∈ [2, 8] levels.

2. Abstract

Seven benchmark trials were generated across B+ Tree index heights / search depths h = 2 to h = 8 levels (total in-node binary search key comparisons C from 16 to 64 comparisons). An ordinary least-squares regression of key comparisons against tree height yielded an empirical scaling slope of 8.0000 comparisons/level and an intercept of 0.0000 comparisons, demonstrating exact agreement with Rudolf Bayer's multi-way block indexing model C(h) = 8h (difference = 0.0000%). The empirical telemetry confirms that by aligning high-fanout node pages (order m = 256) with 4096-byte disk blocks, each index level evaluates in exactly log₂(256) = 8 scalar comparisons while requiring strictly h physical block I/O reads.

3. Apparatus and fixed settings

• Disk Access Machine (DAM) Model Simulator: Hardware memory hierarchy profiler simulating 4KB block transfers between external non-volatile secondary storage (SSD/HDD) and internal volatile DRAM buffer caches under the Aggarwal-Vitter model.
• 4KB Page Frame Buffer Pool & LRU Eviction Manager: Database buffer cache subsystem maintaining 64 pinned page frames, tracking cache hit ratios, page dirty bits, and clock-based LRU page replacement.
• Multi-Way B+ Tree Index Engine (Order m = 256): High-fanout balanced search tree engine supporting 255 keys and 256 child pointers per 4096-byte node, proactive node splitting, and leaf record segregation.
• In-Page Binary Search Comparator: Branch-free binary search unit executing exactly log₂(256) = 8 scalar key comparisons per visited disk page to resolve child branch routing.
• Sequential Leaf Node Pointer Matrix (Range Scan Unit): Bidirectional doubly-linked leaf chaining bus enabling sequential table scans without ascending index tree levels.
• Write-Ahead Logging (WAL) & ACID Transaction Logger: Durability manager simulating sequential append-only log writes, page checkpointing, and crash recovery under ARIES protocols.
• Disk page block size normalized to industry standard 4096 bytes (4 KB).
• Index entry layout: 8-byte 64-bit integer key + 8-byte child page pointer (16 bytes/entry).
• B+ Tree fanout order m = 256 child pointers and 255 keys per internal page.
• Buffer pool cache simulated with 64 page frames and LRU (Least Recently Used) page eviction.
• In-node key search implemented using branch-free binary search over contiguous sorted page arrays.

4. Theory and graph choice

In computing systems, memory is organized hierarchically: fast, expensive, volatile primary memory (CPU L1/L2/L3 caches and DRAM) operates at nanosecond timescales, while massive, economical, non-volatile secondary storage (Solid-State Drives and Magnetic Hard Disk Drives) operates at microsecond or millisecond latencies. Standard main-memory data structures—such as AVL trees, Red-Black trees, and binary search trees—assume uniform random-access memory where pointer dereferences execute in constant time. However, when dataset volumes surpass DRAM capacity, transferring single records from disk becomes a catastrophic performance bottleneck: rotating mechanical disks incur 5 to 10 ms seek times, while NVMe SSDs read data in fixed physical flash blocks (typically 4KB or 8KB pages). If an AVL tree of 16 million records (height h ≈ 24 levels) were stored on disk, searching for a single record would require 24 random disk block I/Os, taking nearly a quarter of a second! In 1970, Rudolf Bayer and Edward M. McCreight solved this external memory dilemma by inventing the B-Tree. Designed specifically for the Disk Access Machine (DAM) model (Aggarwal and Vitter, 1988), a B-Tree is a self-balancing multi-way search tree that aligns node sizes directly with operating system disk blocks (typically 4096 bytes). With 4KB pages and 16-byte index entries, each node achieves an extraordinary fanout of m = 256 child pointers. Consequently, a B-Tree can index 16.78 million records in a tree of height only h = 3 levels, reducing disk seeks from 24 down to just 3 block reads—an 8× reduction in physical I/O! The architecture reached maturity with the B+ Tree, which segregates index nodes (storing only routing keys and child page pointers) from leaf nodes (storing actual data records) and links all leaves into a doubly-linked sequential list, enabling lightning-fast range queries. Inside each loaded 4KB page, the CPU executes in-memory binary search over the 255 sorted keys in log₂(256) = 8 comparisons, yielding strictly C(h) = 8.0000 · h comparisons across h traversal levels. Today, B+ Trees serve as the universal storage engine core of relational databases (MySQL InnoDB, PostgreSQL, SQLite, Oracle), modern file systems (NTFS, XFS, APFS, Btrfs), and hardware flash translation layers (FTL). In this laboratory investigation, students benchmark multi-way search across tree heights h ∈ [2, 8], verify the linear comparison law C(h) = 8.0000 · h + 0.0000 via ordinary least-squares regression, explore B+ Tree node splitting and merging, contrast random pointer hopping with block I/O paging, and analyze buffer pool management and Write-Ahead Logging (WAL).

The mathematical regression fits the linear model y = mx + b, where x = h represents B+ Tree index traversal height in levels, y = C represents total in-node binary search key comparisons, m represents the comparison slope k_node, and b represents the baseline comparison offset (theoretically C_0 = 0.0000 comparisons). The gradient has physical units comparisons/level.

5. Method

1. Select the tree height parameter h ∈ [2, 3, 4, 5, 6, 7, 8] levels with node order m = 256 (255 keys per 4KB page). Initialize the 64-frame buffer pool cache and flush secondary storage pointers.
2. Fetch the root disk page (Block ID: 0x01) into an available buffer pool frame. Record 1 disk page I/O block read.
3. Within the loaded 4KB page, perform binary search over the 255 sorted keys to identify the child page pointer satisfying key[i] ≤ target < key[i+1]. Record exactly 8 in-page scalar key comparisons.
4. Dereference the selected child Block ID. If the page is resident in the buffer cache, record a cache hit; otherwise, execute a physical disk block read into the buffer pool. Increment the search depth counter.
5. Upon reaching the leaf level (depth h), execute a final 8-comparison binary search to locate the exact payload record. Inspect the next-leaf pointer to verify sequential range scan capability.
6. Repeat the experimental indexing benchmark across tree heights h ∈ [2, 3, 4, 5, 6, 7, 8] levels. Perform ordinary least-squares linear regression of total in-node key comparisons C(h) against h to determine the per-level comparison slope k_node, intercept C_0, and coefficient of determination R².

6. Observations and calculation table

All benchmark observations use strictly controlled memory buffers. Values are recorded deterministically from the algorithmic comparator register. Residuals are computed relative to the ordinary least-squares regression line.

Download the sample observations (CSV) ↓

7. Worked calculation for one observation

8. Graph, gradient and final calculation

Circular markers represent empirical benchmark observations. The solid line represents the ordinary least-squares asymptotic linear fit.

9. Uncertainty and comparison

Percentage difference = |estimate − theoretical value| / |theoretical value| × 100 = 0.0000%.

For n = 7 benchmark observations, Σresidual² = 0.00000; s² = Σresidual²/(n − 2). Gradient standard error = √[s²/Σ(x − x̄)²] = 1.8898e-07. Intercept standard error = √[s²(1/n + x̄²/Σ(x − x̄)²)] = 1.0177e-06.

Propagating the fit parameters yields a fit standard error of 1.8898e-07 comparisons/level, with an ideal coefficient of determination R² = 1.000000.

In external memory algorithms and database indexing analysis, the in-node comparison count C(h) = k_node · h + C_0 = 8.0000·h + 0.0000 comparisons across traversal height h is an exact algorithmic invariant for order m = 256 nodes. Unlike continuous physical instrumentation, there is no analog sensor noise, thermal drift, or calibration variance in counting discrete in-page binary comparisons or block I/O transfers. However, in physical database storage servers, wall-clock transaction and query latency are heavily modulated by external memory and operating system dynamics: (1) Database buffer pool cache hit ratios: accessing a page resident in DRAM memory frames consumes ~50–100 ns, whereas a buffer miss requiring an NVMe SSD flash page read incurs 10–50 µs (~500× slower), and a mechanical HDD sector seek incurs 5–10 ms (~100,000× slower); (2) Operating system page cache double-buffering: databases utilize direct I/O (`O_DIRECT`) to bypass OS kernel page cache replication and avoid double-buffering latency; (3) Multi-core latch contention on root and internal nodes: concurrent reader/writer transactions cause lock and latch thrashing on high-level routing nodes, resolved via optimistic lock coupling (latch crabbing); and (4) Sequential leaf scanning vs random in-order traversal: the B+ Tree doubly-linked leaf architecture allows range scans (`WHERE id BETWEEN a AND b`) to stream contiguous pages at multi-gigabyte sequential disk throughput, bypassing upper index levels entirely. Ordinary least-squares linear regression of observed in-node comparisons against tree height h across depths from 2 to 8 levels yields an empirical scaling slope k_node = 8.0000 comparisons/level and intercept C_0 = 0.0000 comparisons with zero residual variance (R² = 1.00000), verifying the multi-way indexing complexity bound Θ(h) with mathematical certitude.

10. Result and discussion

The empirical benchmark observations provide rigorous quantitative verification of External Memory Algorithm theory and the Disk Access Machine (DAM) model. In secondary storage architectures, the astronomical latency gap between volatile DRAM (50–100 ns) and non-volatile flash SSDs (10–50 µs) or rotating HDDs (5–10 ms) renders traditional binary search trees (AVL or Red-Black trees) unviable: indexing 16 million records requires 24 binary levels, imposing 24 random disk seeks (up to 240 ms per query). The B-Tree, invented by Rudolf Bayer and Edward McCreight (1970), eliminates this bottleneck by matching node capacity to operating system disk block clusters (typically 4096 bytes). With an order of m = 256 child pointers and 255 keys per 4KB page, a B+ Tree indexes over 16.78 million records in a tree of height only h = 3 levels, reducing disk seeks from 24 down to 3 block reads—an 8× reduction in physical I/O overhead. Within each visited 4KB page in the buffer pool, contiguous sorted key alignment enables branch-free binary search across the 255 keys in exactly log₂(256) = 8 scalar comparisons. Across all benchmark trials from h = 2 to h = 8 levels, the empirical regression slope m = 8.0000 comparisons/level and intercept b = 0.0000 confirm this invariant with zero residual variance (R² = 1.00000). Comparative architectural analysis elucidates fundamental trade-offs across storage indexing paradigms: Binary Search Trees execute in O(log₂ N) time but suffer disastrous I/O fragmentation due to 32-byte node footprints. B+ Trees segregate routing index keys from leaf data records, maintaining a doubly-linked leaf chain that enables raw sequential disk throughput on range queries (SELECT ... BETWEEN). Hash Indexes achieve O(1) point lookups in memory but cannot execute range scans and suffer catastrophic performance degradation under external memory bucket overflows. Log-Structured Merge-Trees (LSM-Trees, used in RocksDB and Cassandra) optimize write-heavy workloads by buffering updates in memory (MemTable) and appending immutable SSTables to disk, trading read amplification (inspecting multiple levels) for sequential write throughput. Finally, transaction durability analysis emphasizes the vital role of Write-Ahead Logging (WAL) and the ARIES recovery protocol: buffering dirty B+ Tree pages in DRAM maximizes throughput, while sequential append-only WAL flushes ensure complete crash recovery with zero data loss.

11. Precautions and limitations

• Verify that the node key count does not violate the minimum degree invariant (t - 1 ≤ n ≤ 2t - 1) after dynamic deletion operations; trigger sibling borrowing or node merging upon underflow.
• Ensure node memory structures are strictly 4096-byte aligned in memory to prevent crossing operating system virtual memory page boundaries.
• In B+ Tree range scans, maintain buffer pool read locks (shared latches) on current and adjacent leaf pages during pointer walking to prevent concurrent split race conditions.
• Always flush Write-Ahead Log (WAL) records to persistent storage using fsync() before confirming transaction commits to client applications.

The simulated laboratory environment models idealized external memory computation where disk page block reads and in-node binary search comparisons execute deterministically (C(h) = 8h comparisons per search path). In physical database servers, wall-clock transaction throughput is heavily modulated by buffer pool cache hit ratios (DRAM vs NVMe flash access latencies), OS file system page cache double-buffering, multi-core latch contention (B-Tree reader/writer latch thrashing), SSD wear-leveling and garbage collection stalls, and synchronous fsync() log flushing bottlenecks. In the B+ Tree disk indexing benchmark across search path depths h in [2, 8] levels with node order m = 256 (where each 4KB disk page stores 255 sorted keys and 256 child page pointers), index retrieval executes in two coordinated phases: (1) external memory block I/O reading exactly h disk pages into the database buffer pool; and (2) in-page binary search within each loaded 4KB page. Because each page stores B - 1 = 255 keys, binary search executes exactly log₂(256) = 8 scalar key comparisons per page level to identify the appropriate child page pointer or target data record. Across a traversal path of height h, the cumulative in-node comparison count is strictly governed by the exact linear model C(h) = 8.0000 · h + 0.0000 comparisons with zero theoretical intercept C_0 = 0.0000 comparisons. Ordinary least-squares regression across all benchmark trials yields an ideal coefficient of determination R² = 1.000000 with zero residual variance.

12. Conclusion

This laboratory investigation quantitatively verified the multi-way branching mechanics, block I/O alignment, and in-page binary search scaling of B-Trees and B+ Trees. Through systematic benchmarking across tree depths from h = 2 to 8 levels, we verified the empirical comparison slope k_node = 8.0000 comparisons/level and baseline intercept C_0 = 0.0000 comparisons with an ideal R² = 1.00000. The investigation established the microarchitectural efficiency and theoretical necessity of B+ Tree page alignment, high-fanout routing, and buffer pool caching, proving why B+ Trees remain the universal, irreplaceable storage engine backbone of relational database management systems, operating system file systems, and enterprise storage infrastructure.