Indexes

An index is a data structure that enables fast retrieval of records or documents based on the values of certain fields. By organizing keys in a way that supports quick lookups, indexes reduce the amount of data the system must scan.

In databases, an index lets a query locate rows without scanning the entire table. Common forms include clustered indexes, which determine the physical order of rows, and non-clustered indexes, which store pointers to the data. The most widely used structure is the B-tree or its variant B+ tree, which supports efficient range and equality queries. Other index types include hash indexes for exact matches and specialized indexes such as GiST or GIN in some systems, as well as bitmap and BRIN indexes for specific workloads. A unique or primary key constraint often creates an index automatically; multiple-column (composite) indexes and covering indexes help optimize complex predicates and selected columns.

Index design considers selectivity, cardinality, and query patterns. A good index supports the queries that are most often used, and may be partial (covering a subset of rows) or functional (based on expressions). Over-indexing adds storage, slows writes, and increases maintenance costs, while missing indexes can lead to full scans.

In information retrieval, inverted indexes map terms to the documents that contain them, possibly recording term frequency and positions to support ranking and phrase queries. Such indexes are central to search engines and many document databases.

Maintenance tasks include monitoring fragmentation, reindexing, and adjusting fill factors. Proper indexing is a balance between faster reads and increased write and storage overhead.