How indexes work

The problem: reading everything

Ask SHOP for the orders of customer 1 and the database has a choice. If nothing helps it, it reads every row of orders and keeps those with customer_id = 1. That is a full table scan. With 8 rows nobody notices. With 5 crore orders on a sale day, each scan reads gigabytes, and a page that ran this query on every visit would grind to a halt.

What an index is

An index is a separate structure that stores the values of one or more columns in sorted order, each with a pointer to its row. In SQLite the pointer is the rowid; in PostgreSQL it is the row's physical location; in MySQL's InnoDB, secondary indexes store the primary key. Because the values are sorted, the database can find a value without looking at every entry.

B-trees in plain words

Almost every database uses a B-tree (balanced tree) for ordinary indexes. Picture a tree of pages. The top page holds a few hundred sorted keys that split the whole range into parts ("A to F go left, G to M next..."). Each part points to a page lower down that splits again, until the bottom pages (leaves) hold the actual values and row pointers.

• Sorted: values are in order, so a range like order_date between two dates is one walk along the leaves.
• Balanced: every leaf is the same distance from the top, so every lookup takes the same few steps.
• Wide: each page holds hundreds of keys, so even crores of rows need only about three or four levels.
• Fast: the number of steps grows with the logarithm of the row count, written O(log n). Doubling the table adds roughly one comparison, not double the work.

Indexes you already have

Primary keys and UNIQUE constraints are indexed automatically, because the database must check them quickly on every insert. In SQLite, an INTEGER PRIMARY KEY is the rowid itself, so the table is stored sorted by it. A composite key such as order_items (order_id, product_id) gets an automatic index named sqlite_autoindex_order_items_1.

Creating, listing and dropping indexes

CREATE INDEX idx_orders_customer ON orders(customer_id);
SELECT name, tbl_name FROM sqlite_master WHERE type = 'index';
-- sqlite_autoindex_order_items_1 | order_items
-- idx_orders_customer            | orders
DROP INDEX idx_orders_customer;

The query itself does not change. You still write WHERE customer_id = 1; the query planner, the part of the database that decides how to run a query, notices the index and uses it. Other engines list indexes differently: \di in PostgreSQL's psql or the pg_indexes view, and SHOW INDEX FROM orders in MySQL.

The cost of an index

• Writes: every INSERT, every DELETE, and every UPDATE of an indexed column must also update each index. A table with ten indexes does eleven writes per new row.
• Storage: an index is a copy of its columns plus pointers. Indexes on a big table can be gigabytes.
• Memory: indexes compete with data for the cache. Unused indexes waste it.

Selectivity: which columns deserve an index?

Selectivity is how few rows a value picks out. An email or an order id picks one row out of crores: very selective, a perfect index. A status column with four values, where Delivered covers 90% of rows, picks almost everything; reading the index and then nearly every row is slower than a plain scan, so the planner ignores such an index. Good candidates are columns in WHERE, JOIN ... ON and ORDER BY of frequent queries, with many distinct values.

Common mistakes

• Indexing every column "just in case". Fix: index for real, frequent queries; drop indexes nothing uses.
• Forgetting the foreign key columns. Fix: index orders.customer_id, order_items.product_id and similar join columns.
• Indexing a low-selectivity column such as a yes/no flag. Fix: skip it, or use a partial index on the rare value (next topic).
• Creating the same index twice under different names. Fix: list existing indexes before adding one.
• Judging speed on tiny test tables. Fix: test with realistic row counts; on 8 rows a scan is always fine.