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.
Computer Science / B-Trees, B+ Trees & Disk Indexing
FREE TO EXPLORELABORATORY 19 · COMPUTER SCIENCE
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. Explore interactive search algorithms, compare operation counts and analyse complexity scaling.
COMPUTE · BENCHMARK · ANALYSE
Your virtual algorithm laboratory.
IN-NODE BINARY SEARCH KEY COMPARISONS C—
EXECUTION STATUS
Ready to execute tree height h benchmark.
Adjust tree height h n, then execute benchmark.
Operation counts are generated deterministically by the exact algorithmic execution model. Modern hardware benchmarks additionally reflect cache line prefetching and branch misprediction penalties.
Algorithmic assumptions and limits
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.
Computational tools & environment.
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.
FOLLOW THE METHOD
A reason behind every step.
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. Suggested independent settings: 2, 3, 4, 5, 6, 7, 8 levels.
01
Configure B+ Tree Order & Initialize 4KB Buffer Pool
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.
02
Load Root Page Block into Buffer Pool
Fetch the root disk page (Block ID: 0x01) into an available buffer pool frame. Record 1 disk page I/O block read.
03
Execute In-Page Binary Search at Current Level
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.
04
Traverse Down Multi-Way Child Page Pointers
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.
05
Access Leaf Node Record & Verify Sequential Linkage
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.
06
Perform Asymptotic Regression Across Tree Heights
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².
YOUR NOTEBOOK · 0 OBSERVATIONS
Turn measurements into asymptotic insight.
Points are your recorded benchmark observations. The regression line validates B-Trees, B+ Trees & Disk Indexing complexity scaling.
LINEAR ASYMPTOTIC FIT · y = mx + b
C(h) = k_node · h + C_0 = 8.0000 · h + 0.0000 comparisons
| # | B+ Tree height / Search path depth h (levels) (levels) | In-node binary search key comparisons C (comparisons) | Tree search depth h (levels) | Key comparisons C(h) = 8.0000 · h + 0.0000 (comparisons) | Remove |
|---|
No readings yet. Execute a tree height h benchmark and record it.
Calculate it yourself.
CHECK YOUR UNDERSTANDING