A database index is a data structure maintained by a database management system to locate records, evaluate conditions, or produce results in a useful order without examining all the underlying data. An index associates searchable values with records, record locations, or other information sufficient to answer a query. Although commonly described as an auxiliary structure, an index can also organize the primary storage of a table.
Indexes are central to the performance of databases because they change how much data a query must inspect and how that data is accessed. Looking up one customer in a table containing a billion customers may require only a short traversal through an index rather than a scan of the entire table. The advantage is conditional: indexes consume space, increase the work required for updates, and do not necessarily help queries that retrieve a large proportion of a table.
Index design connects logical data modeling, storage algorithms, query optimization, transaction processing, and distributed systems. Different structures support ordered comparisons, equality searches, text retrieval, spatial predicates, and similarity search. Their effectiveness depends not only on their theoretical complexity but also on data distribution, storage layout, concurrency, and the database’s workload.
Logical role and physical organization
An index is defined by a mapping from search keys to searchable objects. A search key may be one column, a tuple of columns, a computed expression, a word extracted from a document, or a geometric representation. It need not be a candidate key in the relational sense: an index on a surname may associate the same surname with thousands of rows. In a relational database, the index is normally separate from the logical definition of the relation, even when it determines how the relation is physically stored.
Index entries contain some combination of key values, row identifiers, physical addresses, and payload data. A row identifier may name a page and slot, identify a version of a row, or encode a primary-key value that must be looked up in another structure. These alternatives affect lookup cost and maintenance. A physical location can provide direct access but may need adjustment when records move; a logical identifier can remain stable while introducing another search.
A clustered index organizes the stored records according to its key, or places the records themselves in the leaves of an ordered structure. A secondary index provides another access path without being the table’s principal organization. Terminology varies among systems. InnoDB stores table records in a clustered primary-key index and includes the primary-key columns in secondary index records. PostgreSQL normally stores table rows in a separate heap, while its indexes refer to heap tuples. PostgreSQL’s CLUSTER operation physically reorders a table at a particular time but does not continuously preserve that ordering during later changes.
The distinction between dense and sparse indexes concerns coverage. A dense index typically has an entry for every indexed record or distinct search-key value, with a way to find all matching records. A sparse index records selected boundaries, such as one key per data page. Sparse indexing generally relies on an underlying order: a boundary identifies the region that must then be searched. Multilevel ordered indexes can use sparse upper levels even when their leaves densely represent the indexed records.
An index is not equivalent to a backup or a cache. It is usually maintained as part of the database’s persistent state, although it can often be rebuilt from authoritative data. It also differs from a materialized view, which stores the result of a query and may contain joins or aggregates. The boundary is not absolute: covering indexes store selected row values, and some database systems implement indexed views whose maintenance resembles that of indexes.
Ordered trees and range access
The most widely used general-purpose database indexes are based on the B-tree family. Rudolf Bayer and Edward McCreight introduced the B-tree in 1970, with a journal account appearing in 1972. Its central property is high fan-out: each internal node stores many separator keys and child references. By matching nodes to storage pages, the structure reduces the number of page accesses needed to reach a record.
A B+ tree stores data entries at the leaf level and routing information in internal nodes. Leaves are commonly connected in key order, allowing the system to descend once to the start of a range and then continue through adjacent leaves. This supports equality lookups, inequalities, ordered iteration, minimum and maximum searches, and some forms of grouping. Product documentation often uses “B-tree” broadly for structures with B+ tree characteristics.
For entries and an effective fan-out , the number of levels grows approximately as
If an internal node can direct searches to about 200 children, a billion entries can be reached through only a few levels, depending on leaf capacity and occupancy. Root and upper-level pages are often cached, so a search may incur fewer physical reads than its tree height suggests. The relevant computational complexity therefore has both a comparison component and a storage-access component; counting only comparisons can conceal the main practical cost.
Insertion locates the target leaf and adds an entry. If the page lacks space, the implementation may redistribute entries or split the page, installing a separator in its parent. Splits can propagate upward and occasionally create a new root. Deletion may leave free space, trigger consolidation, or defer reclamation. Actual implementations frequently relax textbook occupancy rules to avoid expensive restructuring during concurrent operations.
Page layout significantly influences performance. Prefix compression reduces repeated key material, while suffix truncation can shorten internal separator keys when complete keys are unnecessary for routing. A configurable fill factor may reserve space for future insertions. Sequentially increasing keys tend to concentrate insertion on the rightmost leaf; random keys spread writes but can cause more scattered page access and fragmentation.
Ordered indexes also provide capabilities beyond filtering. An index on (customer_id, order_date) can yield one customer’s orders chronologically without a separate sort. However, an index’s order is useful only when its comparison rules match the query, including direction, collation, and treatment of null values. Physical page adjacency is not guaranteed merely because leaf entries are logically ordered.
Hash indexes and log-structured designs
A hash index applies a hash function to a search key and uses the result to select a bucket or directory entry. Its conceptual basis is the hash table, adapted to persistent storage, variable-length records, concurrency, and recovery. When the hash function distributes keys well and bucket occupancy is controlled, equality lookup can have expected constant-time bucket access, although collisions and overflow pages add work.
Hashing does not normally preserve key order. An index designed for account_id = 417 therefore does not automatically help with account_id BETWEEN 400 AND 500 or with ordered output. Even an equality lookup may require comparison of original values because distinct keys can share a hash value. Duplicate-heavy data can also concentrate many entries in one bucket regardless of how uniformly different values are distributed.
Dynamic hashing addresses growth without requiring a complete reorganization after every capacity increase. Extendible hashing uses a directory indexed by selected hash bits and splits buckets as needed. Linear hashing expands through a controlled sequence of bucket splits, progressively changing which portion of the hash space uses a larger bucket address range. These techniques trade directory overhead, split behavior, and overflow management differently. Their practical value depends on whether equality access outweighs the broader capabilities of ordered indexes.
A log-structured merge tree, or LSM tree, takes a different approach to balancing reads and writes. Described by Patrick O’Neil and colleagues in 1996, it accumulates updates in a memory-resident component and periodically writes sorted runs to storage. Background compaction merges runs, reorganizes keys, and discards obsolete versions when they are no longer needed. LSM designs are widely used in persistent key–value storage engines, which may in turn implement a database’s primary and secondary indexes.
An LSM lookup may need to consult several components rather than follow one tree path. Bloom filters can rule out runs that definitely do not contain a key, reducing unnecessary reads. They can produce false positives but, when correctly constructed and maintained, do not produce false negatives for represented keys. Range searches merge ordered iterators from relevant runs and resolve duplicate versions.
LSM design is often explained through read, write, and space amplification. Compaction rewrites data beyond the original update volume; overlapping runs increase lookup work; and multiple versions consume storage until cleanup. Leveled and tiered compaction policies balance these effects differently. Consequently, neither “hash indexes are constant time” nor “LSM trees are write optimized” is a complete performance prediction: workload shape, memory allocation, durability settings, and background maintenance remain decisive.
Specialized indexes for analytical and complex data
Some query predicates do not fit a single ordered mapping from scalar values to rows. A bitmap index represents a value or condition through a vector of bits indicating which rows satisfy it. Boolean operations combine these vectors efficiently: an analytical query can intersect the bitmaps for a region, product category, and time period before fetching qualifying rows. Compression can make the representation economical when bit patterns have suitable structure.
Bitmap indexing is especially associated with read-heavy analytical workloads and data warehouses. Low-cardinality attributes are a common application, but compressed and encoded bitmap schemes can also support higher cardinalities. Update behavior matters as much as cardinality: changing many rows concurrently can create maintenance or locking costs that make a particular bitmap implementation unsuitable for transaction-heavy tables. A temporary bitmap assembled by a query executor should not be confused with a persistent bitmap index.
An inverted index maps terms or features to the objects containing them. Its basic components include a term dictionary and a posting list for each term. Text-oriented postings may record document identifiers, term frequencies, and token positions. Positions allow phrase evaluation, while frequencies contribute to relevance scoring. This structure connects database indexing with information retrieval and is also useful for arrays, tags, and document fields containing multiple values.
Spatial indexes represent location and extent rather than just scalar order. An R-tree, introduced by Antonin Guttman in 1984, groups objects through bounding rectangles. A query first identifies rectangles that could intersect the requested region, then tests the actual geometries where necessary. Overlapping bounding regions can require traversal of multiple branches, so performance depends on spatial distribution and packing. A bounding-box match is often only a candidate match, not proof that the exact spatial predicate holds.
Block-level summaries provide a much smaller alternative to indexing individual records. Minimum and maximum values for each block can exclude blocks whose ranges cannot satisfy a predicate. PostgreSQL’s block range indexes, or BRIN indexes, summarize ranges of physical pages; related “zone map” techniques appear in analytical systems. These structures are particularly effective when a column, such as event time, correlates with physical storage order. They offer little pruning when nearly every block spans the full value range.
A vector index supports similarity search over numerical embeddings. Techniques include graph-based search, inverted partitions, and quantization. Many implementations return approximate nearest neighbors, trading exactness for speed and memory efficiency. This differs fundamentally from a conventional equality index, whose purpose is to locate all qualifying entries under defined comparison rules. Combining similarity ranking with ordinary filters introduces additional planning questions, such as whether filtering should occur before, during, or after candidate generation.
Composite keys, expressions, and covering access
A composite index orders or organizes entries using more than one attribute. In a conventional ordered index on (a, b, c), comparison is lexicographic: values of a are compared first, then b within equal values of a, and then c. This makes the leading attributes particularly important. A condition on a usually identifies a contiguous region, while a condition on c alone may leave matching entries scattered throughout the structure.
The familiar “leftmost prefix” rule describes this organization, but it is not an absolute statement about every optimizer. Some systems perform skip scans, repeated probes over distinct leading values, or combinations of indexes. Equality constraints on leading columns commonly allow a later range constraint to define a narrow interval. A range condition on an earlier column can reduce how strongly later columns bound that interval, although later conditions may still filter index entries before table rows are fetched.
For example, consider an orders table with an index on (customer_id, order_date). The query
SELECT order_date, total
FROM orders
WHERE customer_id = 42
AND order_date >= DATE '2024-01-01'
ORDER BY order_date;
can use the customer identifier to select one part of the index and the date condition to choose its starting position. The resulting entries are already ordered by date for that customer. Reversing the columns creates a different access path: it favors date-oriented access across customers but generally does not isolate one customer’s records as directly.
A covering index contains all values required by a particular query. Some systems allow non-key columns through an INCLUDE clause, distinguishing payload from ordering attributes. This can avoid fetching full records, but “index-only” access is implementation-dependent. Under certain visibility schemes, the executor must still consult table storage unless auxiliary information establishes that the indexed row is visible to the current transaction. Wider indexes also occupy more pages and increase maintenance work.
An expression index stores the result of a computation, such as a normalized email address or a date extracted from a timestamp. Its usefulness depends on the system recognizing that the query expression matches the indexed expression. Expression behavior must be sufficiently stable for stored index entries to remain valid; database products therefore impose restrictions on permitted functions.
A partial index, also called a filtered index in some systems, contains only rows satisfying a predicate. An index restricted to unprocessed jobs can be much smaller than a full-table index. The optimizer must establish that the query’s conditions imply the index predicate before relying on it. Unique partial indexes can enforce uniqueness within a selected subset. Uniqueness itself follows product-specific rules for nulls, collations, and comparisons, rather than a universal interpretation of textual equality.
Query planning, selectivity, and cost
The existence of an index does not mean that using it is the cheapest execution strategy. A query optimizer compares possible access paths within a broader plan that may include joins, sorting, aggregation, and parallel execution. A table scan can outperform indexed access when a query retrieves many rows, particularly if index lookups lead to scattered reads while the scan processes pages sequentially.
Selectivity describes the fraction of rows satisfying a condition, although terminology occasionally varies between discussions of predicates and key distinctness. If a table contains rows and a predicate is estimated to match a fraction , the expected qualifying cardinality is
The cost of an index path depends not just on , but on the number and arrangement of pages containing those rows. Ten thousand matches tightly clustered in a few hundred pages can be cheaper to fetch than the same number dispersed across ten thousand pages.
Optimizers estimate cardinalities from statistics such as row counts, distinct-value counts, common-value frequencies, histograms, and correlations with physical order. Combined predicates are particularly difficult. If city and postal code are strongly dependent, multiplying their individual selectivities under an independence assumption can substantially underestimate the number of matches. Extended or multicolumn statistics can capture some of these relationships, but they do not eliminate estimation error.
A simplified comparison separates index traversal, entry processing, and row retrieval:
where is the number of table pages and is an estimated scan cost per page. Real models also include cache effects, processor work, prefetching, parallelism, and storage-device characteristics. There is no universal percentage of matching rows below which an index must be beneficial.
Predicate form affects the available access paths. A condition such as price * 1.2 > 120 may be harder to use directly with an ordinary index on price than an equivalent range condition recognized by the optimizer. Implicit type conversions, mismatched collations, and functions applied to indexed columns can also obstruct access. Conversely, optimizers can sometimes rewrite expressions or derive bounds, so syntactic appearance alone does not determine index use.
Indexes influence joins as well as standalone filters. An indexed nested-loop join repeatedly probes an inner relation using values from an outer relation; it can be efficient when the outer input is small and probes are selective. For larger inputs, a hash join or merge join may be cheaper. The 1979 access-path selection work on System R established influential methods for cost-based relational planning, including the joint consideration of access methods and join order.
Transactional correctness and concurrent access
An index must remain consistent with the database’s transaction rules, not merely with the latest values visible on storage. Inserting, deleting, or updating a row can affect several indexes, and failures must not leave a committed row inaccessible through an index that should contain it. Index maintenance is therefore integrated with transaction commit, recovery, and isolation rather than treated as an independent optimization.
Write-ahead logging records information needed to recover changes before the corresponding data pages become durable. Recovery can replay committed structural changes and handle incomplete operations according to the engine’s design. Index page splits require particular care: a crash between moving entries and installing routing information must not make keys permanently unreachable. Different systems log physical changes, logical operations, or combinations suited to their recovery architecture.
Concurrency control distinguishes short-lived protection of in-memory structures from transaction-level protection of logical data. A page latch may protect a tree node while it is read or modified. A lock may protect a key or key range until a transaction reaches an appropriate boundary. These mechanisms serve different purposes: holding a transaction lock does not by itself make an in-memory page safe to modify concurrently.
Under multiversion concurrency control, several versions of a logical row can coexist. An index may contain references to versions that are not visible to a particular snapshot, requiring additional checks. Old entries cannot always be reclaimed immediately after an update because an earlier transaction may still need them. Vacuuming, garbage collection, or compaction eventually removes obsolete state once visibility rules permit it.
Uniqueness checking must account for concurrent operations. Two transactions inserting the same supposedly unique value cannot both be allowed to commit simply because neither initially saw the other’s uncommitted row. The engine must coordinate through locks, conflict detection, waiting, or validation. Likewise, serializable execution may need to protect the absence of records in a searched range. Otherwise, another transaction can insert a new matching row, creating a phantom that invalidates assumptions made by the first transaction.
Online index construction adds another consistency problem. A builder scans existing data while concurrent transactions continue modifying the table. A correct protocol must reconcile the scan with those changes and establish a point at which the completed index is valid for ordinary queries. Implementations use combinations of snapshots, change capture, additional passes, validation, and brief synchronization phases. “Online” or “concurrent” construction therefore does not necessarily mean that no locks are taken or that every operation remains unaffected throughout the build.
Construction, maintenance, and workload design
Creating an index over an existing table is often more efficient as a bulk operation than as a sequence of ordinary insertions. A common method extracts key–identifier pairs, sorts them, and builds leaf and internal pages in order. When the entries exceed available memory, external sorting produces sorted runs and merges them using temporary storage. Parallel extraction and sorting can shorten construction, but storage bandwidth and the final organization of the index remain limiting factors.
Every additional index contributes to write cost. An insertion generally adds entries to all applicable indexes; deletion makes entries removable; and an update may remove old keys and insert new ones. Changing an unindexed column can sometimes avoid index work through storage-engine-specific optimizations. Conversely, an index that stores many included columns can require maintenance even when its search-key columns remain unchanged.
The storage cost is not simply the size of the indexed values. Entries also contain row references, headers, alignment overhead, and sometimes visibility or version information. Internal pages, unused page space, and retained obsolete entries add further overhead. For a secondary index that stores a wide primary key in each entry, the choice of primary key can materially affect the total size of every secondary structure.
Fragmentation and bloat have several meanings. Splits can leave partially filled pages; deletion can leave reusable space; obsolete versions may remain pending cleanup; and logical key order can diverge from physical placement. Rebuilding may compact an index, but it also consumes input/output bandwidth, temporary space, and transaction-log capacity. A recently compacted structure may soon expand again if the workload naturally requires free space for random insertions. Maintenance must therefore be interpreted in relation to the storage engine rather than a single fragmentation percentage.
Index selection is a workload-level problem. A structure that accelerates one query may slow a frequent update path, occupy memory needed by another index, or add substantial replication traffic. Closely related indexes can sometimes be consolidated, but a longer composite index is not always an interchangeable substitute for a shorter one: it can be larger, less cache-efficient, or ordered differently from what another query needs. An index enforcing a constraint also has a correctness role independent of measured query use.
Performance evaluation distinguishes estimated plans from observed execution. Plan inspection can reveal index scans, row lookups, residual filtering, and sorting, while runtime statistics expose actual row counts and page activity. Testing must account for warm versus cold caches, parameter distributions, concurrent load, and background work. Automatic tuning systems use workload histories and hypothetical cost estimates to propose index changes, but their conclusions remain dependent on the workloads and cost models they observe.
Partitioned and distributed indexes
Partitioning divides a logical table into separately managed subsets, often by range, list membership, or a hash of a partition key. A local index covers one partition, while a global index spans several or all partitions. Local indexes simplify operations such as dropping an old time partition because the corresponding index data can be removed with it. Global indexes can provide direct access by a non-partitioning key but require additional coordination when partitions change.
Partition pruning and indexing solve related but distinct problems. Pruning identifies partitions that cannot contain relevant rows; an index locates entries within the remaining data. A query on a partition key may eliminate nearly all partitions without using an index. Conversely, a highly selective lookup on another column may still need to search every partition if there is no global access path or routing information.
In distributed computing, an index may be colocated with the records it describes or partitioned independently. Colocation makes local updates and reads simpler, but secondary-key searches may need to contact many shards. Independently partitioning a global secondary index by its own key enables targeted lookup, followed by retrieval from the shard holding the base record. That second stage adds network communication and may require coordination across ownership boundaries.
Consistency is especially significant for distributed secondary indexes. If base-row updates and index updates occur in one distributed transaction, the system can provide strong guarantees at the cost of coordination. If index maintenance is asynchronous, recently inserted records may temporarily be missing from index results, and deleted or changed records may leave stale candidates. Fetching and checking a returned base row can reject some stale entries, but it cannot discover a new row whose index entry has not yet arrived.
Sharding also changes the effects of key distribution. A monotonically increasing timestamp or identifier can concentrate writes on the newest range partition or the right edge of a distributed ordered index. Hash partitioning spreads writes more evenly but sacrifices direct locality for range scans. Techniques such as partition splitting, composite partition keys, and controlled key prefixes balance distribution against the number of partitions a query must contact.
Distributed index queries frequently merge results from multiple nodes. An ordered query with a limit can request local candidates and combine them, while aggregates may be partially computed near storage. Snapshot consistency requires the participating nodes to interpret visibility coherently. Repartitioning and replica movement must also preserve routing correctness while data changes location. These concerns show why a distributed index is not merely a conventional index stored on several machines: its access path includes network routing, failure handling, and coordination protocols.
Historical development and continuing research
Database indexing grew from file-access methods developed before relational databases. Sequential files, sorted files, and indexed-sequential organizations balanced efficient batch processing with direct record lookup. Early systems often exposed physical access paths more directly to programmers. The relational approach separated logical queries from storage organization, making it increasingly important for the system to choose indexes without requiring applications to prescribe the exact access sequence.
The B-tree’s introduction in 1970 provided a durable framework for dynamically maintained ordered storage. During the 1970s, relational prototypes demonstrated how indexes could be selected within declarative query processing. Patricia Selinger and colleagues’ 1979 System R paper made cost-based access-path selection a foundational part of database engineering. Later work expanded the repertoire: R-trees addressed spatial objects in 1984, and LSM trees formalized a merge-based approach to update-intensive storage in 1996.
Hardware changes repeatedly altered the relative cost of index operations. On rotating disks, reducing random seeks was a dominant objective. Solid-state storage reduced mechanical latency but retained important differences between reads, writes, and large sequential transfers. In-memory databases shifted greater attention toward processor branches, cache misses, synchronization, and allocation. A shallow tree can still be expensive when each level requires an unpredictable memory access across the memory hierarchy.
Compression is consequently both a space technique and an execution technique. Smaller keys allow more entries per page and can improve cache residency, while compressed bitmaps permit operations over many row indicators at once. Column-oriented analytical systems often combine dictionaries, sorted segments, block summaries, and late materialization rather than relying on one traditional row-oriented index. The distinction between storage encoding and indexing can become blurred when the encoded representation directly supports predicate evaluation.
Learned indexes, prominently developed in research published in 2018 by Tim Kraska and colleagues, explore using machine learning models to predict where keys occur in sorted data. The model approximates a key’s position, after which a bounded or otherwise controlled search establishes the correct result. Such designs do not remove the need for correctness mechanisms. Updates, distribution changes, prediction errors, model storage, and retraining costs all affect whether they outperform carefully engineered conventional structures.
Other research directions include adaptive indexes that reorganize data as queries arrive, automated physical design, cache-conscious and latch-reducing tree structures, and indexes for combinations of structured predicates and similarity search. Comparative evaluation remains difficult because an index can appear superior under one key distribution or read–write ratio and inferior under another. Relevant measurements include tail latency, sustained update throughput, recovery time, storage amplification, and performance while maintenance is active—not only isolated lookup speed.