Home › Reference › Glossary › Index

Index

A sorted lookup structure beside a table, so the database finds rows without scanning them all.

In the lesson

A table is stored on pages, each holding about a hundred rows, in the order the rows were added. (That's PostgreSQL's way; MySQL's InnoDB keeps rows sorted by primary key instead, but a search on any other column is no better off.) To find the rows with seller = 123, the only way without an index is to read every page and check each row: a scan, whose cost grows with the table.

In short: An index is a sorted structure that turns a scan of the table into a short walk.

Taught in Chapter 19: Indexes.

More from the same chapter

• B-tree: The sorted tree most databases use for an index. A lookup walks a few levels, and the tree gains a level only when the table grows by hundreds of times.
• Bloom filter: A small bit array that says a key is definitely not in a set, or maybe is. A maybe is sometimes wrong; a no is right every time.
• Compaction: An LSM tree's background merge of its sorted files, which drops overwritten and deleted values.
• Covering index: An index that holds every column a query needs, so the database answers it without reading the table.
• Geohash: A latitude and longitude encoded as a string in which nearby points mostly share a prefix, so a cell can be found with an ordinary index.
• Inverted index: For every word, the list of documents that contain it. What full-text search reads instead of scanning.
• LSM tree: A store that writes to memory and appends sorted files, merging them in the background. Cheap writes, reads that may check several files.
• Quadtree: A map split into four, and the busy parts split again, so a dense city gets small cells and an ocean one large one.
• Query planner: The part of a database that chooses how to run a search, such as a table scan or an index, from statistics about the data.
• Selectivity: The share of a table's rows a search returns. The smaller the share, the more an index is worth having.
• Table scan: Answering a query by reading every row of a table, at a cost that grows with its size.