Database Index

A database index is a data structure that accelerates data retrieval from a database table at the cost of additional storage and slower writes. But this definition is impoverished. An index is not merely a performance optimization; it is a physical hypothesis about the distribution of future queries, encoded into the geometry of storage. When you create a B-tree index on a column, you are not merely 'speeding up lookups' — you are asserting that the query workload will consist of range queries and point lookups on that column, and you are reshaping the physical layout of data to match that assertion. The index is a bridge between the logical world of declarative queries and the physical world of block-addressable storage, and its design is one of the deepest systems problems in computing.

The B-Tree as Default Infrastructure

The B-tree is the dominant database index structure, and its dominance is not accidental. It is a physical adaptation: a B-tree's node size matches the disk block size, minimizing the number of random seeks required for a lookup. As described in the B-tree article, the structure turns the memory hierarchy from an adversary into an ally. Virtually every relational database — InnoDB, PostgreSQL, SQL Server — uses B-trees or B+ trees as the default indexing mechanism. The query optimizer treats the B-tree as a transparent acceleration layer, but the physical reality is never transparent: page splits, fragmentation, and fill factor degradation are physical processes that leak into query performance in unpredictable ways.

Hash Indexes: The Point-Lookup Specialist

A hash index maps keys directly to storage locations through a hash function, achieving O(1) average lookup time for exact matches. It cannot support range queries, because hash functions destroy locality: keys that are adjacent in the sort order are scattered across the hash space. The choice between a B-tree and a hash index is therefore a choice about query semantics, not merely performance. If your workload is exclusively point lookups, a hash index is superior. If you need range queries, order-by operations, or prefix matching, the hash index is useless. This is not a tuning decision; it is a commitment to a query language.

Spatial Indexes: When One Dimension Is Not Enough

Traditional indexes assume one-dimensional ordering. Spatial indexing — via R-trees, k-d trees, or space-filling curves like the Hilbert curve — solves the problem of multi-dimensional query predicates. The R-tree groups nearby objects into nested bounding rectangles, enabling efficient nearest-neighbor and range queries. The Hilbert curve maps multi-dimensional space to a one-dimensional index while preserving spatial locality. These indexes are not incremental adaptations of B-trees; they are qualitatively different structures that encode spatial topology rather than linear ordering. The choice of spatial index is a claim about the geometry of the data and the distribution of spatial queries.

LSM-Tree Indexes: The Write-Optimized Alternative

The LSM-tree (Log-Structured Merge-tree) takes a radically different approach to indexing. Instead of updating a B-tree in place, it buffers writes in memory and periodically merges sorted runs into immutable files. This design trades read latency for write throughput, making it dominant in write-heavy workloads like time-series databases, logging systems, and key-value stores. The LSM-tree index is not merely a different data structure; it is a different theory of time and state. Where the B-tree treats the index as a living structure that must be continuously repaired, the LSM-tree treats the index as an accretion of historical facts, each immutable and timestamped. This philosophical difference has profound systems consequences for consistency, compaction, and read amplification.

Covering Indexes and Selectivity

A Covering index is an index that contains all the columns needed to answer a query, eliminating the need to look up the base table. It is a denormalization strategy encoded into the index layer. The benefit is dramatic: a query can be answered entirely from the index, reducing I/O by orders of magnitude. The cost is storage and write amplification: every column in the covering index must be updated on every write.

Index selectivity measures the fraction of rows that a query predicate eliminates. A selective index on a unique column (e.g., user_id) is highly effective. A non-selective index on a boolean column (e.g., is_active) may be worse than no index at all, because the database engine must scan a large fraction of the table anyway, and the index adds random I/O. The systems designer must understand that indexing is not an automatic good — it is a selective amplification of query patterns, and its value depends entirely on the statistical distribution of the data and the workload.

The Index as Epistemic Infrastructure

The database index is a form of epistemic infrastructure. It encodes what the system expects to be asked, and in doing so, it shapes what the system can answer efficiently. A system with only B-tree indexes is optimized for ordered, range-based reasoning. A system with hash indexes is optimized for identity-based reasoning. A system with spatial indexes is optimized for geometric reasoning. The index layer is not neutral; it is a cognitive architecture imposed on the data.

The common mistake is to treat indexing as a post-hoc optimization, something you add after the schema is designed and the queries are written. This is backwards. The choice of index is the choice of what questions the system will answer well, and what questions it will answer poorly. A database without the right index does not merely run slowly; it runs a different algorithm, one that may produce different results under concurrency, one that may fail entirely under load. The index is not an accelerator. It is a declaration of intent, and its absence is a declaration of indifference. The systems designer who does not index is not a minimalist; they are a gambler, betting that the query distribution will never diverge from the physical layout of the table. That bet is almost always lost.