Database indexing is the use of auxiliary data structures, called indexes, that let a database find records quickly without scanning every row, trading extra storage and slower writes for faster reads. An index works like the index at the back of a book: instead of reading every page to find a topic, the reader looks it up in a sorted list that points to the pages. Indexes are among the most important tools for performance in relational databases, search engines, graph databases and the stores that support vector search.
Why indexes matter
Without an index, a query that looks for a customer by email must read the whole table, a full table scan whose cost grows with the number of rows. With an index on the email column, the database can jump almost directly to the matching row, often reducing a search through millions of rows from seconds to milliseconds. As data grows, the difference between indexed and unindexed queries becomes the difference between a responsive application and an unusable one.
Common index types
- B-tree: a balanced tree that keeps keys sorted and supports equality, range and ordering queries. It is the default in most systems.
- Hash index: maps keys to locations with a hash function, fast for exact matches but unable to support ranges.
- Bitmap index: uses bit arrays for columns with few distinct values, useful in analytics.
- Inverted index: maps each term to the documents that contain it, the basis of full-text and keyword search, and often combined with semantic methods in hybrid search.
- Spatial index: structures such as R-trees and GiST for geographic and geometric data.
- Composite index: covers several columns together, useful when queries filter on them in a common order.
- Covering index: includes all columns a query needs so that the table need not be read.
- Partial and expression indexes: index only some rows or the result of a function.
- Clustered index: determines the physical order of rows in the table.
- Vector index: structures such as HNSW and IVF for approximate nearest neighbor search over embeddings.
How a B-tree works
A B-tree has a root node, internal nodes and leaf nodes. Each node holds a sorted list of keys with pointers to child nodes or to rows. A search starts at the root, compares the target with the keys, follows the right pointer and repeats until it reaches a leaf. Because each node holds many keys, the tree is shallow: even billions of rows may need only three or four levels, so a lookup touches a few pages of storage. Inserts split full nodes to keep the tree balanced.
Costs and trade-offs
- Storage: each index uses space, sometimes as much as the table.
- Slower writes: every insert, update or delete must also update the indexes.
- Maintenance: indexes can fragment and need rebuilding, and statistics must stay current so that the optimizer chooses well.
- Memory: frequently used indexes should fit in memory for the best speed.
- Over-indexing: too many indexes slow writes and may never be used.
Designing good indexes
- Index for real queries: study the slowest and most frequent queries rather than guessing.
- Choose selective columns: columns that narrow results sharply benefit most.
- Order composite keys carefully: place equality columns first and range columns later.
- Use query plans: tools such as EXPLAIN show whether an index is used.
- Drop unused indexes: monitor usage and remove those that do not help.
- Mind the data type and function use: wrapping a column in a function can prevent an ordinary index from being used.
- Test with realistic data: performance on small samples may mislead.
Indexing in search and AI
Search engines build inverted indexes that map words to documents and rank results with measures such as BM25. For semantic search, documents are split by chunking, converted into embeddings and placed in a vector index, so that similar items can be found without comparing the query with every vector. The same principle, trading build time and memory for fast lookup, underlies each. In retrieval-augmented generation, the speed and quality of the index directly affect how well an assistant can find relevant passages. Indexes are also central to every knowledge base.
Common mistakes
- Creating an index on every column.
- Ignoring write-heavy workloads where indexes add cost.
- Forgetting to update statistics after large data loads.
- Indexing columns with very few distinct values, which often gives little benefit.
- Using leading wildcards in text patterns, which defeat ordinary indexes.
A worked example
An online shop’s orders table has 50 million rows. A page that shows a customer’s recent orders runs a query filtered by customer identifier and sorted by date, and it takes six seconds. The team creates a composite index on customer identifier and order date. The query plan changes from a full scan to an index lookup, and the page loads in 20 milliseconds. Nightly import jobs become slightly slower because of the extra index, an acceptable cost for the improvement.
Reading a query plan
Databases include an optimizer that decides how to run each query, and tools such as EXPLAIN show its chosen plan. A plan that mentions an index scan or index seek is using an index, while one that mentions a sequential or full table scan reads everything. Developers compare estimated and actual row counts to see whether the optimizer’s statistics are accurate, check the cost numbers and look for steps that sort or join large sets. Reading plans is the most reliable way to decide which index to add and to confirm that it helped.
Index maintenance in practice
Over time, heavy updates and deletions leave gaps and uneven pages in indexes, which can slow scans and waste space. Administrators schedule rebuilds or reorganizations, refresh statistics after large loads and monitor index size and usage. Many systems can build an index online without blocking writes, which matters for large production tables. Before dropping an index that looks unused, teams check usage over a full business cycle, since a rarely run month-end report may depend on it.
History
Indexes appeared with the earliest file systems and database systems in the 1960s, using sorted files and tree structures. The B-tree of 1970 solved the problem of efficient disk-based ordered indexes and became the standard. Later decades added hash, bitmap, spatial and full-text indexes, and the 2010s brought indexes for high-dimensional vectors as machine learning turned text and images into embeddings.
FAQs
Does every column need an index? No. Index the columns used in frequent filters, joins and sorts.
Why do indexes slow writes? Each change must also update the index structures so that they stay accurate.
Is a vector index the same as a B-tree? No. A vector index uses structures designed for similarity in many dimensions, while a B-tree orders keys along one dimension.
More in Retrieval and Knowledge Systems
Key facts
- The B-tree, invented by Rudolf Bayer and Edward McCreight in 1970, remains the default index structure in most relational databases.1
- PostgreSQL supports several index types, including B-tree, hash, GiST, SP-GiST, GIN and BRIN.2
- Approximate nearest neighbor indexes such as HNSW extend the idea of indexing to high-dimensional vectors used in similarity search.3
Related concepts
Quick checkWhat is database indexing?Show answer
It is the use of auxiliary data structures that let a database locate records quickly without scanning all rows, at the cost of extra storage and slower writes.
Sources
- Bayer and McCreight, Organization and Maintenance of Large Ordered Indexes, Acta Informatica, https://link.springer.com/article/10.1007/BF00288683
- PostgreSQL Documentation, Index Types, https://www.postgresql.org/docs/current/indexes-types.html
- Malkov and Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, https://arxiv.org/abs/1603.09320
Editorially reviewed by Specialty Digest Editorial TeamLast reviewed November 17, 2026Researched and drafted with AI assistanceReport an issue
