Database Indexing Deep Dive: B-Trees, LSM Trees, and Query Planner Tradeoffs

Indexes are the difference between a query that returns in milliseconds and one that melts a database node. Yet teams often treat them as a checklist item: add an index on every column that appears in a WHERE clause, hope the planner uses it, and move on. In practice, an index is a data structure contract with three costs: read amplification, write amplification, and space amplification. Choosing the right index means understanding the storage engine, the query workload, and the optimizer that connects them.

The Index as a Data Structure Contract

At a high level, an index maps a search key to a location. For a point lookup, that location is a row identifier or a primary key. For a range scan, the index must also preserve order. For a full-text search, the key might be a token. The same logical index can be implemented as a B-tree, a hash table, a log-structured merge tree, a bitmap, or an inverted index. Each implementation makes different tradeoffs.

• Read amplification: How many pages or files must be read to answer a query. A secondary B-tree index may require several tree traversals plus heap fetches. An LSM tree may check multiple SSTables and Bloom filters before finding a key.
• Write amplification: How much extra data is written per logical insert or update. B-trees may split pages and rewrite them. LSM trees rewrite data during compaction. Too many indexes can multiply write cost across every write path.
• Space amplification: How much storage the index consumes relative to the base data. Indexes can easily double or triple storage. LSM trees may temporarily hold multiple versions of the same key.

Selectivity and cardinality determine whether an index is useful. A column with millions of distinct values is a good candidate for a B-tree index on equality and range predicates. A column with a handful of values, such as status or country, may be better served by a bitmap index or a partial index. A covering index can eliminate heap fetches entirely, but it duplicates more data.

B-Tree and B+Tree Indexes: The Default for Relational Workloads

Most relational databases, including PostgreSQL, MySQL InnoDB, SQL Server, and Oracle, use a B+tree variant for their default index. B+trees are balanced, ordered, and optimized for block storage. Internal nodes store separator keys and child pointers. Leaf nodes store keys and row locators, and they are linked to support efficient range scans.

The key property is fanout. If each 8 KB page can hold hundreds of keys, a tree over millions of rows stays only three or four levels deep. A point lookup reads a few pages, and a range scan reads a linked list of leaves. That predictability is why B+trees remain the workhorse for transactional systems.

Clustered vs Secondary Indexes

A clustered index defines the physical order of the table. In InnoDB, the primary key is the clustered index, and secondary indexes store the primary key value as their row locator. In PostgreSQL, tables are heap-organized by default, though CLUSTER can physically reorder a table once. A secondary index lookup may therefore require a second lookup into the heap or clustered index. That extra hop is called a heap fetch or bookmark lookup.

Composite and Covering Indexes

Column order in a composite index matters. An index on (tenant_id, created_at) supports queries that filter by tenant_id and range-scan by created_at. It also supports queries that filter only by tenant_id. It does not efficiently support queries that filter only by created_at. The leftmost prefix rule is not a limitation to memorize; it is a consequence of how the tree is sorted.

A covering index includes all columns required by a query, so the engine can answer from the index alone. For example, an index on (customer_id, order_date, total_amount) can cover a query that selects total_amount for a customer and date range. Covering indexes reduce read amplification but increase space and write cost. They are most valuable for high-frequency read queries where the extra storage is acceptable.

Partial, Expression, and Unique Indexes

Partial indexes index only a subset of rows, such as WHERE status = ‘active’. They are smaller, cheaper to maintain, and often more selective. Expression indexes, also called functional indexes, index the result of an expression, such as lower(email). They allow the planner to use an index for queries that apply the same expression. Unique indexes enforce constraints and provide fast lookup for existence checks. Each of these is a B-tree variant with a narrower contract.

LSM Trees: Write-Optimized Storage for High-Ingest Workloads

Log-structured merge trees power many NoSQL databases, time-series engines, and NewSQL systems, including RocksDB, Cassandra, ScyllaDB, HBase, and parts of TiDB and CockroachDB. The core idea is to make writes sequential. New writes go to a write-ahead log and an in-memory memtable. When the memtable fills, it is flushed to an immutable sorted string table, or SSTable. Background compaction merges SSTables and removes obsolete versions.

LSM trees excel at write-heavy workloads: event ingestion, metrics, logs, messaging, and key-value stores with high update rates. They avoid the random page writes that can plague B-trees under heavy insert load. But they shift complexity to reads and compaction.

Read Path and Bloom Filters

A read must check the memtable, then SSTables from newest to oldest. Without help, that could mean many file reads. Bloom filters provide a probabilistic shortcut: if the filter says the key is absent, the engine can skip the SSTable. If it says the key may be present, the engine reads the file. Bloom filters reduce read amplification for point lookups but do not help range scans as directly.

Compaction Strategies

Compaction merges overlapping SSTables, discards tombstones, and removes old versions. Size-tiered compaction merges similar-sized files and is common in write-heavy systems. Leveled compaction organizes files into levels with non-overlapping key ranges, which improves read performance and space efficiency at the cost of higher write amplification. Tiered+leveled and hybrid strategies aim to balance both.

• Write amplification: The same logical byte may be rewritten many times as data moves through levels.
• Read amplification: More levels or more overlapping files mean more reads per lookup.
• Space amplification: Old versions and tombstones consume space until compaction removes them.

LSM tuning is workload-specific. A system with mostly inserts and rare reads can tolerate size-tiered compaction. A system with read-heavy point lookups and strict latency SLOs may need leveled compaction, larger Bloom filters, and careful level sizing. There is no universal configuration.

Hash Indexes, Bitmaps, and Specialized Indexes

Not every index is a tree. A hash index maps a key to a bucket using a hash function. It is excellent for equality lookups and useless for range scans. PostgreSQL supports hash indexes, and many in-memory stores use hash tables as their primary structure. Hash indexes are compact and fast when the workload is point lookups on a unique or high-cardinality key.

Bitmap indexes represent a set of row identifiers for each distinct value. They are efficient for low-cardinality columns and analytic queries that combine multiple predicates with AND and OR. They compress well and can be combined with bitwise operations. However, they perform poorly under high-concurrency updates because updating a bitmap can require locking large portions of the index.

Specialized indexes target specific data types and query patterns:

• Inverted indexes: Map tokens or terms to documents. Used for full-text search, log search, and search engines.
• GiST and GIN: PostgreSQL index types for geometric data, arrays, JSONB, and full-text search.
• BRIN: Block range indexes store min and max values per block range. They are tiny and effective for naturally ordered data such as timestamps.
• Vector indexes: HNSW, IVF, and PQ indexes support approximate nearest-neighbor search for embeddings. They trade recall for latency and memory.

The Query Planner: Where Indexes Meet Reality

An index only helps if the query planner chooses it. The planner parses the query, explores access paths, estimates cardinalities, and compares costs. Its decisions depend on statistics, cost constants, and the shape of the query. When estimates are wrong, the plan can be catastrophically wrong.

Most planners use histograms, distinct-value counts, and correlation statistics. They estimate selectivity for predicates, then estimate join sizes. A common failure is the independence assumption: the planner assumes columns are uncorrelated. If city and postal_code are correlated, the estimated row count may be far too low or too high. Stale statistics are another source of bad plans, especially after bulk loads or schema changes.

Explaining the Plan

Every engineer working with databases should be comfortable with EXPLAIN and EXPLAIN ANALYZE. Look for the access method, join strategy, estimated rows versus actual rows, and buffer usage. A sequential scan is not always bad; for a query that returns most of a table, it is often cheaper than an index scan with many random heap fetches. An index-only scan is not always free; it depends on the visibility map or clustering factor.

Watch for these signals:

• Nested loop with high outer row estimate: This can explode into millions of inner lookups.
• Hash join with spills: The hash table did not fit in memory, causing disk I/O.
• Filter after index scan: The index returns many rows, but most are discarded by a filter. A better composite or partial index may help.
• Rows removed by join filter: The join order or statistics may be poor.
• Heap fetches: A secondary index lookup on a heap-organized table can be expensive if rows are not physically clustered.

Designing Indexes That Earn Their Keep

Index design should start from the workload, not from the schema. Identify the highest-impact queries by total execution time, frequency, and business criticality. Then design candidate indexes and test them with realistic data volumes and distributions.

Use these principles:

• Index for the query, not the column. A composite index is often better than several single-column indexes because the planner can use one index to satisfy multiple predicates.
• Order columns by equality first, then range, then sort. For a query with WHERE tenant_id = ? AND status = ? AND created_at > ?, an index on (tenant_id, status, created_at) is usually strong.
• Consider covering indexes for hot read paths. Include the selected columns when the extra write and space cost is justified.
• Use partial indexes for skewed workloads. If 99 percent of queries target active rows, index only active rows.
• Avoid redundant indexes. An index on (a) is redundant if (a, b) already exists. The reverse is not true.
• Monitor unused indexes. They consume space and slow down writes. Drop or disable them after verifying they are not used by critical reports.
• Beware of over-indexing. Every index adds write amplification, can increase lock contention, and makes schema changes riskier.

Operational Considerations: Maintenance, Bloat, and Concurrency

Indexes are not static objects. In PostgreSQL, updates and deletes leave dead tuples. VACUUM reclaims space, but indexes can still become bloated. A bloated index reads more pages and may be chosen less often. REINDEX or pg_repack can rebuild indexes, but large tables require careful planning. Concurrent index creation avoids long write locks, but it takes longer and can fail, leaving an invalid index behind.

In MySQL InnoDB, the change buffer can defer secondary index writes for non-unique indexes, reducing random I/O. However, the change buffer has limits and can become a bottleneck. In LSM systems, compaction runs in the background and competes with foreground traffic for disk bandwidth. Tuning compaction threads, file sizes, and Bloom filters is an ongoing operational task.

Cloud-managed databases hide some of this complexity, but they do not eliminate the tradeoffs. Serverless databases may charge per read and write, so an inefficient index can directly increase cost. Managed LSM services may expose compaction metrics and allow tuning, but defaults are not optimal for every workload.

Common Failure Modes and How to Diagnose Them

Many index problems have recognizable signatures:

• Function on an indexed column: WHERE date(created_at) = ‘2024-01-01’ cannot use a plain index on created_at. Use a range predicate or an expression index.
• Implicit cast: Comparing a string column to a numeric literal can force a cast and disable index usage. Keep types consistent.
• Leading wildcard LIKE: WHERE name LIKE ‘%smith’ cannot use a standard B-tree index. Consider a trigram or full-text index.
• OR across different columns: The planner may choose a full scan. A composite index or UNION ALL with separate indexes can help.
• Low selectivity: An index on a boolean column is rarely useful on its own. A partial index on the rare value may be better.
• Parameter sniffing: A cached plan optimized for one parameter value may be terrible for another. Plan guides or forced parameterization can help in some systems.
• Stale statistics: Run ANALYZE after large data changes. Increase statistics targets for skewed columns.
• Too many indexes: Write latency increases, bloat grows, and the planner spends more time evaluating access paths.

A Practical Workflow for Index Tuning

Use a repeatable process instead of guessing:

1. Capture the workload. Use pg_stat_statements, performance_schema, or cloud query insights to find top queries by total time and frequency.
2. Reproduce the query. Run it with EXPLAIN ANALYZE on production-like data. Capture plans, row estimates, actual rows, and buffer usage.
3. Identify the bottleneck. Is it a sequential scan, a bad join order, a heap fetch, or a sort spill? The fix may not be an index.
4. Design a candidate index. Choose columns, order, partial predicate, and included columns. Consider whether a covering index is worth it.
5. Test safely. Create the index concurrently in production if possible. Measure query latency, write throughput, and storage growth.
6. Validate the plan. Re-run EXPLAIN ANALYZE. Confirm the planner uses the index and that actual rows match estimates.
7. Monitor and iterate. Track index usage, bloat, and write latency. Remove indexes that no longer earn their keep.

Conclusion

Indexing is not about adding more indexes. It is about making deliberate tradeoffs between read speed, write cost, and storage. B+trees remain the default for transactional workloads because they are predictable and versatile. LSM trees dominate high-ingest systems because they turn random writes into sequential ones. Hash, bitmap, inverted, BRIN, and vector indexes solve specific problems that a B-tree cannot. The query planner ties it all together, and its estimates are only as good as the statistics and query shapes it sees.

The best index is the one that matches the workload, fits the storage engine, and is measured under realistic conditions. Learn the data structures, read the plans, and treat every index as a contract with a cost. That mindset turns index tuning from guesswork into engineering.