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

Indexes are the silent engine behind fast database queries. They turn random reads into targeted lookups, range scans into sequential leaf traversals, and full-text searches into instant term matching. But indexes are not free. Every index consumes storage, adds write overhead, and must be maintained as data changes. The art of indexing is matching the right structure and key order to the queries your application actually runs.

This article examines the internals of common index structures, how query planners choose them, and practical strategies for designing indexes that improve read performance without destroying write throughput.

Why Indexes Exist

Without an index, a database must scan every row or every page of a table to find matching records. That is fine for tiny tables, but it collapses under production data volumes. An index is a redundant data structure that maps key values to row locations. The trade-off is fundamental: you pay on writes and storage to gain on reads.

• Read amplification: how many pages or rows must be read to answer a query. Indexes reduce this for selective queries.
• Write amplification: how much extra work each insert, update, or delete causes. Every index must be updated.
• Space amplification: how much extra storage the index consumes, including fragmentation and temporary files.

Good indexing is not about creating the most indexes. It is about creating the fewest indexes that serve the most valuable query patterns.

The Core Index Structures

B-Trees and B+ Trees

B-trees and B+ trees are the workhorses of relational databases. A B+ tree stores keys in internal nodes and data pointers in leaf nodes. Leaves are linked, so range scans can traverse from one leaf to the next without returning to the root. The tree stays balanced, which guarantees logarithmic search time.

When a page fills, it splits. When a page becomes too empty, it may merge. These operations keep the tree healthy but add write cost. Database engines tune this behavior with fill factors, page sizes, and merge thresholds.

B+ trees excel at point lookups and ordered range queries. That is why they dominate in PostgreSQL, MySQL InnoDB, SQL Server, and Oracle for transactional workloads.

Hash Indexes

Hash indexes map a key to a bucket using a hash function. They provide O(1) equality lookups and are compact for point queries. They cannot efficiently serve range queries, ordering, or prefix matching because hashing destroys order.

Hash indexes are useful for in-memory tables, session stores, and equality-only lookups. They also appear in specialized engines and as internal structures for joins and aggregations.

LSM Trees

Log-Structured Merge trees are designed for write-heavy workloads. Writes first go to a write-ahead log and an in-memory memtable. When the memtable fills, it is flushed to disk as an immutable sorted string table, often called an SSTable. Over time, background compaction merges SSTables to remove deleted data and reduce read amplification.

The read path checks the memtable, then immutable memtables, then disk levels from newest to oldest. Bloom filters help skip SSTables that cannot contain the key. LSM trees are used by RocksDB, LevelDB, Cassandra, ScyllaDB, HBase, and many modern distributed databases.

LSM trees trade read amplification for write efficiency. Compaction can create high background I/O and latency spikes if not tuned. Compaction strategies include leveled, tiered, and size-tiered, each balancing read, write, and space amplification differently.

Bitmap Indexes

Bitmap indexes represent each key value as a bit vector. They are efficient for low-cardinality columns such as status, region, or boolean flags. Bitwise operations can combine multiple conditions quickly, which makes them valuable in analytical workloads.

They are less common in transactional databases because updates can be expensive when bitmaps must be rebuilt. Oracle and some data warehouses use them heavily. PostgreSQL does not include a general bitmap index type, but its bitmap heap scan can combine multiple B-tree indexes at query time.

Inverted Indexes

Inverted indexes map terms to the documents or rows that contain them. They power full-text search, log analytics, and search engines. A term dictionary points to posting lists of document identifiers, often with positions and frequencies.

Inverted indexes support token search, phrase search, fuzzy matching, and ranking. PostgreSQL GIN indexes, Elasticsearch, OpenSearch, and Lucene all rely on inverted index structures.

Index Types by Database

• PostgreSQL: B-tree, Hash, GiST, SP-GiST, GIN, and BRIN. BRIN is useful for very large tables with naturally ordered data, such as time-series tables.
• MySQL InnoDB: Clustered primary key index, secondary indexes that store the primary key, and adaptive hash indexes. Secondary lookups often require a second lookup into the clustered index.
• SQL Server: Clustered and nonclustered B-tree indexes, columnstore indexes, filtered indexes, and included columns.
• MongoDB: B-tree based indexes including compound, multikey, text, geospatial, hashed, wildcard, and TTL indexes.
• ClickHouse: Sparse primary indexes, skip indexes, and projections. It is optimized for analytical scans rather than point lookups.

Selectivity, Cardinality, and the Query Planner

Selectivity is the fraction of rows a condition is expected to match. High selectivity means few rows, which makes an index attractive. Low selectivity means many rows, which often makes a sequential scan cheaper than random index lookups.

Cardinality is the number of distinct values in a column. A unique column has high cardinality. A boolean column has low cardinality. The query planner uses statistics such as histograms, most common values, null fraction, and distinct counts to estimate selectivity.

When you run EXPLAIN ANALYZE, you see the plan the database chose and the actual runtime. Look for sequential scans on large tables, nested loops with high row counts, and estimates that differ wildly from reality. Bad estimates often come from stale statistics or correlated columns.

EXPLAIN ANALYZE
SELECT *
FROM orders
WHERE customer_id = 42
ORDER BY created_at DESC
LIMIT 20;

Planner cost parameters matter. PostgreSQL uses settings like random_page_cost, effective_cache_size, and work_mem. On SSDs, the default random page cost may be too high, causing the planner to avoid indexes that would actually be fast. Tuning these values can change plans without changing a single index.

Designing Effective Indexes

Composite Indexes and Column Order

Composite indexes follow the leftmost prefix rule. An index on (tenant_id, status, created_at) can efficiently serve queries that filter on tenant_id, or tenant_id and status, or all three columns. It cannot efficiently serve a query that filters only on status without tenant_id.

Place equality columns first and range or sort columns later. For a query like WHERE tenant_id = ? AND status = ? AND created_at > ? ORDER BY created_at, the order (tenant_id, status, created_at) is strong because the first two columns are equality predicates and the third supports both the range and the ordering.

Covering Indexes and Index-Only Scans

A covering index includes every column needed by a query, so the database can answer from the index alone. This avoids heap or table lookups. PostgreSQL supports INCLUDE columns, SQL Server has included columns, and MySQL can use a covering index when all selected columns are part of the index.

Covering indexes are powerful for frequent read queries, but they make the index wider. Wider indexes consume more storage and increase write cost. Use them selectively for high-impact queries.

Partial Indexes

A partial index indexes only the rows that satisfy a predicate. For example, if most queries target active orders, an index on created_at where status = 'active' can be much smaller and faster than a full index. Writes to inactive rows do not update it.

Partial indexes are supported by PostgreSQL, SQL Server filtered indexes, and some other engines. They are ideal for skewed data where only a small subset is frequently queried.

Expression and Functional Indexes

If queries filter on an expression, create an index on that expression. For example, WHERE LOWER(email) = '[email protected]' can use an index on LOWER(email). Without it, the database must compute the expression for every row.

The same applies to date truncation, JSON fields, and computed columns. The query must match the indexed expression exactly, or the planner may not use it.

Multi-Column vs Multiple Single-Column Indexes

Multiple single-column indexes can sometimes be combined with bitmap AND or OR operations. This can work for low-selectivity filters, but it is often less efficient than a well-designed composite index. Composite indexes are more predictable for frequent, high-value query patterns.

Write Amplification and Maintenance

Every index adds write cost. An insert must write to the table and every index. An update to an indexed column must update every affected index. A delete must remove entries from every index. On write-heavy systems, over-indexing is a common cause of poor throughput.

B-tree indexes suffer from page splits, fragmentation, and bloat. LSM trees suffer from compaction write amplification and temporary space usage. Both need monitoring and maintenance.

Useful maintenance tasks include:

• ANALYZE or UPDATE STATISTICS: refresh planner statistics after significant data changes.
• REINDEX or index rebuild: reduce bloat and fragmentation when performance degrades.
• VACUUM or OPTIMIZE TABLE: reclaim space and improve visibility in engines that need it.
• Index usage monitoring: find unused indexes and remove them. In PostgreSQL, inspect pg_stat_user_indexes. In SQL Server, use sys.dm_db_index_usage_stats. In MongoDB, use $indexStats.

LSM vs B-Tree in Production

B-tree indexes are read-optimized and predictable. They are excellent for transactional systems with frequent point reads, updates, and range queries. They keep data sorted on disk, which supports efficient ordered scans.

LSM trees are write-optimized. They turn random writes into sequential writes, which is ideal for high-ingest workloads such as logs, metrics, events, and messaging. The cost is background compaction, read amplification, and potential latency variability.

Modern systems often blend both approaches. For example, some MySQL deployments use RocksDB as an alternative storage engine. Distributed SQL databases may use LSM-based storage for replication and compaction while exposing B-tree-like indexes to users. The right choice depends on the read-write ratio, latency requirements, and operational maturity.

Query Patterns and Index Anti-Patterns

• Functions on indexed columns: WHERE DATE(created_at) = '2024-01-01' cannot use a plain index on created_at. Use a range or an expression index.
• Leading wildcard LIKE: LIKE '%foo' cannot use a standard B-tree index. Use full-text search or trigram indexes.
• Implicit type casts: Comparing a string column to a number can prevent index use and cause full scans.
• OR across different columns: This can lead to bitmap OR or full scans. Consider UNION ALL with separate indexes or a composite index.
• Low-cardinality indexes alone: An index on a boolean column rarely helps unless it is partial or combined with other columns.
• Over-indexing write-heavy tables: Every extra index slows inserts, updates, and deletes.
• Ignoring covering indexes: Frequent queries that fetch a few extra columns may benefit from INCLUDE columns.
• Never running EXPLAIN: Index design without measuring query plans is guesswork.

Practical Walkthrough: Indexing an Orders Table

Consider an orders table with columns id, customer_id, status, created_at, total, and region. Different queries need different indexes.

• Customer order history: WHERE customer_id = ? ORDER BY created_at DESC LIMIT 20. Use (customer_id, created_at DESC).
• Pending orders by region: WHERE region = ? AND status = 'pending' ORDER BY created_at. Use (region, status, created_at).
• Completed orders dashboard: WHERE status = 'completed' AND created_at >= ?. Use (status, created_at). If status has low cardinality, consider a partial index on created_at WHERE status = 'completed'.
• Covering summary: SELECT customer_id, total FROM orders WHERE status = 'completed' AND created_at >= ?. Use (status, created_at) INCLUDE (customer_id, total) where supported.

After creating indexes, run EXPLAIN ANALYZE for each query. Verify that the plan uses the intended index and that actual row estimates are close. If the planner chooses a sequential scan, check selectivity, statistics, and cost parameters.

Monitoring and Iteration

Indexes are not set-and-forget. Workloads change, data distributions shift, and new queries appear. Track slow query logs, index hit ratios, cache hit ratios, and bloat. Use tools such as pg_stat_statements, MySQL Performance Schema, SQL Server Query Store, and MongoDB profiler.

Review indexes regularly. Remove unused or redundant indexes. A redundant index might share a leftmost prefix with a composite index and add only write cost. Keep the indexes that serve real queries and drop the rest.

Conclusion

Indexing is a design discipline, not a checklist. B-trees and LSM trees solve different problems. Query planners rely on statistics and cost models that you can influence. The best index strategy starts with real query patterns, measures with EXPLAIN, and iterates as the workload evolves. Get the indexes right, and the database does less work to return the same answers.