CSE Roadmap

Core tier · about 2 hours · 5 parts

Part 3 of 5 · 1 min read

What an index actually is

A separate structure mapping column values to row locations, built once and reused by many queries.

Think of a library's card catalog. Instead of walking every shelf to find a book, the catalog is sorted by title and tells a visitor exactly which shelf and position to walk to directly.

In plain words: an index is a separate data structure, stored alongside the table, that maps values of one or more columns to the locations of the rows that hold them. Building an index costs extra storage and some maintenance work on every write, covered on the "When indexes hurt" page later in this level. In exchange, a query that filters on an indexed column can jump almost directly to the matching rows instead of scanning the whole table.

A worked example. An index on orders.customer_id lets the earlier query jump straight to customer 42's rows, instead of reading the entire orders table.

The key lines.

CREATE INDEX idx_orders_customer ON orders (customer_id);
SELECT * FROM orders WHERE customer_id = 42;
-- with the index: the database locates matching rows directly, without a full scan

Index

An index is a separate structure mapping values of one or more columns to the locations of the rows containing them, built to speed up lookups at the cost of extra storage and write maintenance.

Example: a library's card catalog, sorted by title and pointing to a shelf location, is an index over the library's books.