Database Indexing Internals

Database Indexing Internals

Definition: The physical on-disk data structures, B+ Trees, LSM Trees, hash tables, that database storage engines use to locate rows without scanning an entire table.

How It Works

  • B+ Tree: a balanced, multi-way search tree kept on disk. Internal nodes hold only keys and child pointers; leaf nodes hold the actual data (or pointers to it) and are linked together in a sorted chain for fast range scans. Used by PostgreSQL, MySQL InnoDB, SQL Server.
  • LSM Tree (Log-Structured Merge-tree): writes go to an in-memory MemTable first, then flush to immutable, sorted SSTables on disk. A background compaction process merges SSTables over time to bound the number a read has to check. Optimized for write-heavy workloads: Cassandra, RocksDB, LevelDB.
  • Hash index: a hash function maps a key to a bucket. O(1) average lookup for exact-match equality, but useless for range queries (>, <, BETWEEN) since hashing destroys ordering.
  • Clustered index: the table’s rows are physically stored in index key order, there is exactly one per table (it is the table). Secondary index: a separate structure mapping a non-primary key to either a row pointer or the primary key, requiring an extra lookup (“bookmark lookup”) to fetch full row data.
  • Covering index: a (usually composite) index that includes every column a query needs, letting the engine answer entirely from the index without touching the table at all (“index-only scan”).
  • Partial index: an index built over only the rows matching a filter (e.g. WHERE status = 'pending'), smaller and cheaper to maintain than a full-table index when queries only ever care about a subset of rows.

Fanout and height. A B+ Tree’s height is roughly log_fanout(row_count). With a typical fanout of 200 keys per internal node, a table of 100 million rows needs a tree only log_200(100,000,000) ≈ 3.03, so 4 levels including the leaf, deep. That is why B+ Tree lookups stay fast even as tables grow into the billions of rows: each additional order of magnitude in size adds at most one more level to traverse.

Under the Hood

Every level of a B+ Tree corresponds to one disk page read in the worst case, so the diagram below doubles as a cost model: a lookup on this 3-level tree costs at most 3 page reads (root, internal, leaf), no matter which key is being searched for. A B+ Tree index on orders.order_id, height 3, fanout kept small here for readability (real fanout is often 100-500 per node):

Worked example 1: point lookup

  • Given: SELECT * FROM orders WHERE order_id = 700.
  • Step 1: read the root, 700 > 500, descend right to the internal node with keys 650/800.
  • Step 2: 650 <= 700 < 800, descend to the leaf 650, 700, 750.
  • Step 3: scan the leaf (or binary search it), find 700, follow its row pointer.
  • Answer: 3 disk page reads total regardless of table size, versus a full scan reading every page in the table.

Worked example 2: range query using leaf links

  • Given: SELECT * FROM orders WHERE order_id BETWEEN 640 AND 720.
  • Step 1: descend to the leaf containing 650 exactly as above, 2 levels down.
  • Step 2: scan forward within that leaf, then follow the next leaf pointer to the leaf containing 700, 750, without ever revisiting the root.
  • Answer: the sorted, linked leaf layer is what makes range scans cheap. A hash index cannot do this at all: it would have to check every bucket.

Worked example 3: write amplification in an LSM tree

  • Given: a Cassandra table receiving 10,000 writes/sec, MemTable flush threshold 64 MB.
  • Step: MemTable fills, flushes to a new immutable SSTable on disk, this repeats continuously under load.
  • Step: background compaction periodically merges several SSTables into one, discarding overwritten and tombstoned keys.
  • Answer: each logical row may be rewritten several times across compaction levels before it settles, this extra I/O is “write amplification,” the cost an LSM tree pays to keep reads bounded.

Worked example 4: covering index avoids the table entirely

  • Given: SELECT customer_id, status FROM orders WHERE customer_id = 42, and a composite index on (customer_id, status).
  • Step: the engine descends the index tree to the leaf entries for customer_id = 42.
  • Step: since status is already stored in the index leaf alongside the key, there is nothing left to fetch from the table.
  • Answer: an “index-only scan,” zero bookmark lookups into the heap/table, often 5-10x faster than a normal index scan on a wide table.

Why It Matters

An index turns an O(N) table scan into an O(log N) tree descent or O(1) hash lookup. On a 100-million-row table, that is the difference between a query returning in milliseconds and one that takes minutes, and it is usually the single biggest lever available for query performance without touching application code.

  • It shapes hardware cost, not just latency: fewer pages read per query means fewer IOPS, which on cloud databases translates directly into dollars.
  • Choosing the storage engine’s underlying structure (B+ Tree vs LSM) is often the single biggest decision in picking a database for a workload, because it fixes the read/write trade-off for the system’s whole lifetime.
  • Index design is one of the few performance levers a team can pull without a schema migration or application redeploy, CREATE INDEX CONCURRENTLY in PostgreSQL can add one to a live table with minimal locking.

Index Maintenance

Indexes are not free once built. A B+ Tree page that fills up must split into two half-full pages, which fragments the tree over time; a REINDEX/rebuild periodically restores a compact layout. An LSM tree’s compaction does the equivalent job continuously in the background, at the cost of extra disk I/O and temporary 2x disk space during a large compaction pass. Every index also needs its statistics kept current, see Query Optimization and Execution, or the planner will misjudge how selective it is and skip it in favor of a sequential scan.

Deleting rows does not usually shrink an index immediately either. PostgreSQL marks index entries dead and reclaims the space during vacuum; InnoDB merges underfull pages lazily. A table that churns rows heavily can end up with an index physically larger than the data it indexes until maintenance catches up.

Common Pitfalls

  • Over-indexing: every index must be updated on every INSERT/UPDATE/DELETE, so 15 indexes on a hot write table can throttle write throughput far more than any single query benefits.
  • Indexing a low-cardinality column (like a boolean is_active) expecting it to help, when the optimizer will often ignore it and scan anyway because half the table matches either value.
  • Using a secondary index and forgetting the bookmark lookup cost: fetching 100,000 rows via a secondary index can be slower than a sequential scan because of the random I/O per row, unless the index is covering.
  • Composite index column order mismatch: an index on (country, created_at) cannot efficiently serve WHERE created_at > x alone, the leading column must be part of the filter for a B+ Tree index to be used.
  • Assuming an index is free to maintain. On an LSM-backed store, adding a secondary index effectively doubles write amplification, since every write now touches two LSM structures instead of one.
  • Indexing a function result (WHERE LOWER(email) = 'x') but creating a plain index on email, the planner cannot use it since the stored keys don’t match what the query computes, a functional/expression index is needed instead.
  • Forgetting that a leading wildcard (LIKE '%term') cannot use a standard B+ Tree index, since the sorted prefix gives no way to jump to matches, only a trailing wildcard (LIKE 'term%') can.

Comparison

StructurePoint lookupRange queryWrite costBest for
B+ TreeO(log N)Efficient (sorted leaves)Moderate, in-place page updatesRead-heavy, mixed workloads (PostgreSQL, MySQL)
LSM TreeO(log N), multiple SSTables checkedEfficient, but merges sorted runsLow per-write, high total (compaction)Write-heavy workloads (Cassandra, RocksDB)
Hash IndexO(1) averageNot supportedLowExact-match only, e.g. session key lookups
Bitmap IndexFast for low-cardinality AND/ORPoorExpensive updatesAnalytical filters on columns with few distinct values

The B+ Tree vs LSM Tree choice is really a read/write trade-off dial, not a strict better/worse ranking. A B+ Tree updates data roughly in place, so reads stay predictable but writes to random keys cause random disk I/O. An LSM Tree turns random writes into sequential ones by always appending, so writes are cheap, but a single read may have to check the MemTable plus several SSTables before it can be sure it has the freshest value, unless bloom filters narrow the search first.

Example

PostgreSQL’s default index type is B-tree (technically a B+ Tree variant), which is why WHERE created_at BETWEEN x AND y and ORDER BY created_at can both use the same index efficiently. Cassandra’s storage engine is LSM-based end to end: every write, whether to the base table or a secondary index, lands in a commit log and MemTable before being flushed to SSTables, which is what lets it absorb extremely high write throughput at the cost of background compaction work.

MySQL’s InnoDB always stores the table itself as a clustered index keyed on the primary key, if no primary key is declared, InnoDB silently generates a hidden one, because the engine has no concept of a “heap” table the way PostgreSQL does. Every secondary index in InnoDB therefore stores the primary key value, not a raw row pointer, as its bookmark, so a wide or changing primary key makes every secondary index bigger and slower to maintain.

PostgreSQL and SQL Server both expose a “fill factor,” the percentage of a page left intentionally empty at index build time so future inserts and updates can happen in place without an immediate page split. A fill factor of 90 on a heavily-updated index trades a bit of extra disk space for noticeably fewer splits and less fragmentation over the index’s lifetime.

Referenced by

Dig deeper