Database Indexing Demystified: B-Trees, LSM-Trees, and Query Planners

1. Executive Summary & Core Conflict

When relational database queries degrade in production, software engineers are routinely advised to "just add an index." On surface inspection, indexing appears to be a trivial operational win: create a b-tree on the query's filtering column, transform an $O(N)$ sequential table scan into an $O(\log N)$ tree traversal, and observe p99 execution times drop from seconds to milliseconds.

This simplistic assumption conceals serious storage-engine realities.

Every index is not a free lookup shortcut; it is a materialized, ordered, concurrent data structure that must be synchronously maintained on disk across every write, update, and delete transaction. Unconsidered indexing introduces massive write amplification, where a single 100-byte row insertion forces multiple 8 KB page writes across several secondary index trees, saturating disk write bandwidth, fragmenting buffer pools, and ballooning storage costs.

Furthermore, engineers frequently discover that a query planner deliberately ignores an existing index, opting instead for a full sequential scan. This is not a planner defect; it is a mathematically calculated decision driven by disk I/O cost models. Random page lookups over secondary indexes can easily cost orders of magnitude more CPU cycles and physical disk seek time than streaming contiguous pages sequentially through kernel page caches.

To master database performance, backend architects must look past syntax and understand the physical mechanics of storage engines: page layout, tree fan-out, write amplification, and the mathematical cost models evaluated by query planners.

2. Deep Technical Breakdown

The Anatomy of B+ Trees: In-Place Mutation Engine

Relational storage engines like PostgreSQL, MySQL (InnoDB), and SQLite rely on the B+ Tree for clustered and secondary indexing. Unlike classic binary search trees or standard B-Trees, B+ Trees store all actual record pointers (or clustered row tuples) exclusively in leaf nodes, while interior nodes store solely routing keys and page offsets.

Page Layout and Fan-Out

A B+ Tree operates on fixed-size disk blocks called pages (typically 8 KB in PostgreSQL, 16 KB in InnoDB). An internal page consists of an array of $K$ keys and $K+1$ child page pointers. The fan-out factor $B$ determines tree height:

$$\text{Height} \approx \lceil \log_{B}(N) \rceil$$

Assuming an 8 KB page size, an 8-byte index key, and a 6-byte page pointer, an internal node can hold approximately 500 keys ($B \approx 500$). For a dataset of 100,000,000 rows:

$$\text{Height} \approx \lceil \log_{500}(10^8) \rceil \approx 3$$

A tree depth of 3 means any row among 100 million records can be reached in at most 3 page traversals. Because root and intermediate pages reside permanently in the database buffer pool (RAM), resolving an indexed read typically incurs exactly one physical disk read (the target leaf page). Leaf nodes are doubly linked, enabling efficient horizontal range scans without re-traversing upper branches.

The Anatomy of LSM-Trees: Append-Only Ingestion

Modern write-intensive datastores (RocksDB, Cassandra, ScyllaDB, ClickHouse) abandon in-place page mutation entirely in favor of Log-Structured Merge-Trees (LSM-Trees):

1. Write-Ahead Log (WAL): Mutations append sequentially to a disk log for crash recovery.
2. MemTable: Concurrently, the write enters an in-memory sorted structure (SkipList or Red-Black Tree), incurring zero random disk I/O.
3. SSTables (Sorted String Tables): When the MemTable fills (e.g., 64 MB), it freezes and flushes to disk as an immutable, sorted SSTable file.
4. Compaction: Because updates and deletes append new versions or tombstones, background threads run compaction (Size-Tiered or Leveled), reading multiple SSTables, executing merge-sort, discarding obsolete records, and outputting consolidated SSTable runs.

LSM-Trees achieve unmatched write throughput by converting random writes into sequential disk I/O, trading off point-lookup latency and introducing periodic compaction I/O overhead.

The Query Planner Cost Model

When an SQL query executes, the optimizer evaluates alternative execution plans and computes an estimated Cost metric based on catalog statistics (pg_statistic):

$$\text{Total Cost} = (N_{\text{pages}} \times \text{seq_page_cost}) + (N_{\text{tuples}} \times \text{cpu_tuple_cost}) + (N_{\text{index_pages}} \times \text{random_page_cost}) + (N_{\text{index_tuples}} \times \text{cpu_index_tuple_cost})$$

In standard PostgreSQL defaults:

• seq_page_cost = $1.0$ (sequential disk block read)
• random_page_cost = $4.0$ (random seek on spinning disks; typically lowered to $1.1$ on NVMe SSDs)
• cpu_tuple_cost = $0.01$
• cpu_index_tuple_cost = $0.005$

If a query filters a table where 35% of rows match the predicate, a B+ Tree index scan requires random seeks across 35% of heap pages. The planner observes that $0.35 \times \text{total pages} \times 4.0$ exceeds $1.0 \times \text{total pages}$, aborts the index scan, and executes a sequential scan.

3. Production Edge Cases & Failure Modes

Edge Case 1: Index Bloat from MVCC Updates

In engines utilizing Multi-Version Concurrency Control (MVCC) like PostgreSQL, an UPDATE statement writes a brand-new row tuple and marks the old version expired. If an indexed column is updated, or non-HOT updates occur, secondary indexes must receive new entries pointing to the new physical tuple offset.

Under high update throughput, autovacuum may fail to reclaim dead index leaf pages quickly enough, causing index sizes to balloon to multiple times the raw table size and destroying RAM cache hit rates.

Mitigation: Monitor bloat via pg_stat_user_indexes, tune autovacuum aggressiveness (autovacuum_vacuum_cost_limit = 2000), and run REINDEX CONCURRENTLY during scheduled low-traffic periods.

Edge Case 2: The Soft-Delete Cardinality Trap

Applications frequently introduce a deleted_at TIMESTAMP NULL column to support soft deletes:

SELECT * FROM orders WHERE tenant_id = 'tenant_123' AND deleted_at IS NULL;

A compound index on (tenant_id, deleted_at) indexes millions of historical soft-deleted records. If 98% of rows are soft-deleted, the index wastes gigabytes of memory indexing dormant data.

Mitigation: Implement a partial index:

CREATE INDEX idx_orders_active ON orders (tenant_id) 
WHERE deleted_at IS NULL;

This reduces index footprint by up to 98% and accelerates live writes.

Edge Case 3: Implicit Type Coercion Invalidating Indexes

If an index is defined on a VARCHAR column (account_number), but a client passes a numeric literal:

SELECT * FROM accounts WHERE account_number = 10049283;

The engine must implicitly cast every row to a numeric type (WHERE CAST(account_number AS numeric) = 10049283). Because the index keys are strings, the expression disables index traversal and triggers a full sequential scan.

Mitigation: Enforce strict ORM typing, configure database linter rules, and inspect pg_stat_statements for high-duration queries with unexpected sequential scans.

4. Comparative Markdown Table

5. Pragmatic Decision Framework / Checklist

Before adding or modifying database indexes, execute this step-by-step checklist:

Step 1: Pre-Creation Query Analysis

• Profile the query using EXPLAIN (ANALYZE, BUFFERS) in staging with production-scale row counts.
• Inspect Buffers: shared hit=X read=Y. High read numbers indicate physical disk I/O, while hit reflects RAM buffer cache efficiency.
• Verify column selectivity: if a column has low cardinality (e.g., boolean status flags with 80/20 distribution), avoid single-column B-Trees; prefer partial indexes or composite indexing.

Step 2: Composite Index Column Ordering

• Apply the Equality First, Range Second heuristic for multi-column indexes:
  1. Primary position: Columns evaluated using exact equality (WHERE status = 'ACTIVE').
  2. Trailing position: Columns evaluated using inequality, ranges, or sorting (AND created_at >= '2026-01-01' ORDER BY created_at DESC).
• Evaluate covering indexes with INCLUDE clauses:
  sql

  CREATE INDEX idx_users_email ON users (email) INCLUDE (first_name, role);
  

  This satisfies index-only scans without expanding the B+ Tree sorting keys.

Step 3: Lifecycle and Maintenance Governance

• Never run raw CREATE INDEX on high-traffic production databases; always use CREATE INDEX CONCURRENTLY to avoid exclusive table write locks.
• Audit unused and duplicate indexes monthly using queries against pg_stat_user_indexes. Any index with zero scans over a 30-day window should be dropped to reclaim write throughput.
• Adjust random_page_cost in configuration on NVMe drives (set to 1.1 instead of legacy spinning disk default 4.0) so the query planner recognizes SSD random seek speed.