What Are Indexes?

Indexes are supplementary data structures that allow a database management system or information retrieval engine to locate records rapidly without scanning the entire data store. By maintaining an organized mapping from key values to the physical or logical locations of matching records, an index transforms a query that would otherwise require examining every row in a table into a targeted lookup that follows a much shorter path. Indexes are fundamental to the performance of relational databases, full-text search systems, and document retrieval engines operating at scale.

The concept of an index in computing draws directly from its library analogy: just as a book's index lists terms and points to relevant pages, a database index lists column values and points to corresponding rows. The implementation, however, uses algorithmic data structures designed for the access patterns of computational systems, with the choice of structure determining the query types an index can efficiently support.

Index Structures and Types

Several data structures are used to implement indexes, each suited to different query patterns. B-tree indexes are the default choice in most relational database systems, including PostgreSQL and MySQL. A B-tree (balanced tree) organizes key values hierarchically so that equality comparisons, range queries using operators such as <, >, and BETWEEN, and sort-order retrieval all complete in O(log n) time, where n is the number of indexed entries. The PostgreSQL documentation for index types enumerates seven index types in that system: B-tree, Hash, GiST (Generalized Search Tree), SP-GiST (space-partitioned variant), GIN (Generalized Inverted Index for multi-component values such as arrays), BRIN (Block Range INdex for large tables with correlated physical storage), and Bloom filter extensions. Hash indexes store 32-bit hash codes and support only equality comparisons, offering faster lookups for exact matches but no range capability. Spatial index types such as R-trees and GiST accommodate geometric queries, including bounding-box intersection and nearest-neighbor searches, used in geographic information systems and spatial databases.

Inverted Indexes in Information Retrieval

Inverted indexes are the foundational structure of full-text search and document retrieval systems. Rather than organizing entries by record identifier, an inverted index maps each distinct term to the set of documents that contain it, along with optional metadata such as term frequency and positional offsets. When a user submits a query, the search engine intersects and merges the posting lists for each query term to produce a ranked result set. Search engines at internet scale, including those powering web search and enterprise search platforms, are built on variations of the inverted index. The structure is also central to the Apache Lucene library, which underlies Elasticsearch and Apache Solr. As described in an overview of database indexing basics, inverted indexes trade write overhead for dramatic read acceleration, since each document ingestion requires updating potentially many posting lists.

Trade-offs and Design Considerations in Information Systems

Indexes accelerate reads at the cost of write performance and storage overhead. Every insert, update, or delete to an indexed table requires corresponding updates to all applicable indexes, increasing write latency proportional to the number and complexity of indexes maintained. Index selection therefore involves analyzing the query workload: columns appearing frequently in WHERE clauses, JOIN predicates, and ORDER BY expressions are strong index candidates, while columns rarely queried add maintenance cost without proportional benefit. Composite indexes (covering multiple columns) can satisfy queries that filter or sort on several attributes simultaneously. Strategies for B-tree, hash, and specialized index selection outline how query semantics and data distribution should guide index design in production information systems.

Applications

Indexes have applications across a range of information management contexts, including:

• Relational database query optimization in enterprise and web-scale applications
• Full-text search engines for document and content retrieval
• Geographic information systems using spatial indexes for proximity queries
• Knowledge graph and graph database traversal using adjacency list indexes
• Time-series databases employing columnar or range-partition indexes