B-Tree & B+Tree Database Index Depth & I/O Calculator

1. The Mechanical Foundations of B-Tree Database Indexes

Modern relational and analytical database engines (including PostgreSQL, MySQL InnoDB, SQLite, Oracle, and Microsoft SQL Server) rely on the B+Tree data structure as their default general-purpose indexing architecture. Invented by Rudolf Bayer and Edward M. McCreight in 1970, and refined into the B+Tree by H. Wedekind in 1974, this self-balancing search tree was engineered specifically to solve the physical constraints of block-oriented persistent secondary storage (rotational hard disks and solid-state drives).

In memory-based software, balanced binary search trees (such as Red-Black or AVL trees) achieve optimal theoretical asymptotic search complexity of $O(log_2 N)$. However, when applied to disk-resident storage, a binary tree is catastrophically inefficient:

• For $N = 100,000,000$ (100 million) records, a binary tree requires $log_2(10^8) approx 27$ sequential pointer dereferences.
• On persistent storage where each node read fetches an entire disk block (e.g. 8 KB or 16 KB), traversing 27 individual disk pages on an HDD (8 ms per seek) would consume over 200 milliseconds for a single point query.
• Even on a high-speed NVMe SSD (20 µs latency), 27 random page reads take over 540 microseconds.

The B+Tree resolves this bottleneck through massive branching fanout ($B$). By sizing each tree node to occupy exactly one physical disk page (e.g. 8,192 bytes in PostgreSQL or 16,384 bytes in InnoDB), a single page holds hundreds or thousands of index keys. This huge fanout ($B approx 300 ext{–}1,200$) squashes the tree depth down to just 3 or 4 levels for hundreds of millions of records.

2. Structural Anatomy: B-Tree vs B+Tree

While the terms "B-tree" and "B+tree" are frequently conflated in casual conversation, modern relational database engines implement the B+Tree variant exclusively for primary and secondary indexes:

3. Mathematical Sizing: Fanout, Height, and Page Capacity

3.1 Page Space & Usable Payload

A database page of raw size $P_{ ext{size}}$ contains fixed metadata headers (PageHeaderData, checksums, transaction flags) denoted $P_{ ext{head}}$ (e.g. 24 bytes in Postgres, 120 bytes in InnoDB). In addition, production databases enforce an operating fill factor ($FF$) to accommodate in-place updates without immediate splitting:

3.2 Internal Node Branching Fanout ($B_{ ext{int}}$)

An internal routing slot consists of the indexed search key ($S_{ ext{key}}$), a child page pointer ($S_{ ext{ptr}}$, typically 6 or 8 bytes), and page slot directory overhead ($S_{ ext{slot}} approx 2 ext{ bytes}$):

3.3 Leaf Node Fanout ($B_{ ext{leaf}}$)

A leaf node slot stores the indexed key plus the table heap pointer (or Tuple ID / clustered primary key in secondary indexes):

3.4 Tree Height / Depth Formulation

The total number of leaf pages required to store $N$ table rows is:

The total height of the B+Tree ($h$) is determined by the internal fanout required to index all $L$ leaf pages:

where $h=1$ represents a tiny index fitting entirely in a single root page.

4. Disk I/O & Query Latency Modeling

When executing a point lookup query (e.g. SELECT * FROM users WHERE id = 12345;), the database traverses the B+Tree from the root page down to the specific leaf page, incurring $h$ page inspections:

4.1 The Buffer Pool Cache Effect

In production database servers, the root page and top intermediate branch levels reside almost permanently in the database RAM buffer pool (Postgres shared_buffers or InnoDB Buffer Pool):

• Level 1 (Root Page): Consists of exactly 1 page ($approx 8 ext{ KB}$). Cache hit probability $approx 100%$.
• Level 2 (Top Intermediate Branch): Consists of $B_{ ext{int}}$ pages ($approx 300 ext{–}1000$ pages $approx 2.4 ext{–}8 ext{ MB}$). Cache hit probability $approx 99.9%$.
• Leaf Level: Consists of tens of thousands of pages. Physical disk seeks occur primarily when accessing random cold leaf pages.

The expected number of physical disk I/O operations for a point query is:

5. The UUID Primary Key Anti-Pattern: Page Splits & Bloat

One of the most catastrophic database architecture anti-patterns is using completely random 128-bit UUIDs (such as standard UUID v4) as clustered B-tree primary keys. The physics of B-tree page allocation explains why:

• Sequential Keys (BIGINT / AUTO_INCREMENT / UUIDv7): Successive values are strictly greater than prior values. New records append monotonically into the rightmost leaf page. Once full, a clean page allocation occurs, maintaining an optimal ~90% to 95% fill factor with zero fragmentation.
• Random Keys (UUIDv4): New keys distribute with equal statistical probability across all leaf pages. When an arbitrary page fills, the database must execute a 50/50 Page Split: allocating a new page, moving half the keys to the new page, and updating parent pointers.
• Catastrophic Consequences: Average page fill factor collapses from 90% down to ~67% (a 33% bloat penalty). The physical index footprint expands by 50%, cache thrashing destroys buffer pool hit rates, and write amplification degrades NVMe SSD lifespan.

6. Worked Mathematical Sizing: 50 Million Row Index

Database: PostgreSQL, Page Size $P_{ ext{size}} = 8,192 ext{ bytes}$, Header $P_{ ext{head}} = 24 ext{ bytes}$, Fill Factor $FF = 70%$. Table Size $N = 50,000,000 ext{ rows}$. Key: BIGINT (8 bytes). Heap Pointer: Postgres TID (6 bytes). Slot directory overhead: 2 bytes.

Step 1: Usable Payload per Page

Step 2: Fanout Calculations

Step 3: Leaf Pages & Tree Height

Step 4: Total Index Size

Step 5: Query Latency

On an NVMe SSD (20 µs seek latency) with a 95% buffer pool hit ratio:

Even for 50 million records, a point query finishes in 3 microseconds!