With a few hundred keys per page, three levels address tens of millions of rows. An equality lookup is therefore three or four page reads, and the upper levels are almost always cached in memory. A binary tree over the same rows would be about twenty-four levels deep — twenty-four dependent reads. The linked leaves are what make a range cheap: WHERE signup_date BETWEEN '2024-01-01' AND '2024-01-31' searches down once to the first date and then walks the leaves sideways until it passes the last.

Search cost grows with the logarithm of the table, so doubling the table adds a fraction of a level. That is why "add an index" turns an O(n) scan into roughly O(log n) work.

The clustered index: the table is the primary key

In InnoDB the table is not a heap with an index beside it. The table is stored as a B+tree on the primary key — the clustered index — and its leaf pages hold the complete rows.

Clustered index (PRIMARY) on customers.id — its leaves are the rows:

Consequences worth saying out loud in an interview:

• a table has exactly one clustered index, because rows can be physically ordered only one way;
• a lookup or range on the primary key reads the rows directly — the fastest access there is;
• if you declare no primary key, InnoDB uses the first UNIQUE index whose columns are all NOT NULL, and failing that it invents a hidden 6-byte row id — so always declare one;
• a short, ever-increasing key (an INT AUTO_INCREMENT) appends new rows at the right edge of the tree; a random key such as a UUID string inserts into the middle, splits pages and leaves them half full.

Secondary indexes store the primary key

Every other index is a secondary (non-clustered) index. Its leaves hold the indexed column values plus the primary key of the row — not a physical address.

So SELECT * FROM customers WHERE city = 'Pune' is two searches: one down idx_customers_city to collect ids 1 and 3, then one down the clustered index per id to fetch each full row. If the filter matches a few rows, that is cheap. If it matches a third of the table, those per-row lookups jump all over the clustered index and a plain scan wins — which is why the optimizer sometimes ignores an index you created. Two useful corollaries:

• a long primary key makes every secondary index bigger, because each entry repeats it;
• a query that needs only the indexed columns and the primary key never visits the clustered index at all — a covering index, the subject of a later lesson.

PostgreSQL differs here: its tables are heaps, every index (including the primary key's) points at a physical tuple location, and there is no clustered index maintained automatically (CLUSTER reorders once).

Selectivity decides whether an index helps

An index pays off when a lookup returns a small fraction of the table. The measure is selectivity: distinct values divided by rows.

SELECT COUNT(DISTINCT email)   / COUNT(*) AS email_selectivity,    -- ≈ 1.0
       COUNT(DISTINCT city)    / COUNT(*) AS city_selectivity,     -- maybe 0.01
       COUNT(DISTINCT is_active) / COUNT(*) AS active_selectivity  -- 2 / rows ≈ 0
FROM customers;

email is ideal. city helps when the cities are many and evenly spread. is_active (two values) rarely helps on its own: half the table matches, and the optimizer will scan. The server keeps estimates of these counts — the cardinality shown by SHOW INDEX, refreshed by ANALYZE TABLE — and plans from them, not from your intentions.

What an index costs

Indexes are not free, and "why not index every column?" is a classic question. Each index:

• is written on every change: an INSERT adds an entry to every index, a DELETE removes one from each, an UPDATE of an indexed column moves its entry;
• takes disk and buffer pool memory, crowding out data pages you would rather keep cached;
• gives the optimizer more plans to weigh, and occasionally a worse one;
• can be redundant: an index on (customer_id) is covered by one on (customer_id, placed_on).

A UNIQUE index is also a constraint: the server refuses a duplicate, so it must check the index before every insert. And it cannot be created while duplicates exist — finding them first is a practical skill you will use in the checkpoint.

Other kinds of index in MySQL

• B-tree — the default for InnoDB, and what "index" means unless stated otherwise.
• FULLTEXT — word search with MATCH … AGAINST, for prose columns where LIKE '%word%' cannot use a B-tree.
• SPATIAL — R-tree indexes on geometry columns.
• Hash — only for MEMORY tables; InnoDB builds an internal adaptive hash index over hot B-tree pages by itself.
• Functional indexes (MySQL 8.0.13+) — an index on an expression, written with double parentheses: CREATE INDEX idx_year ON orders ((YEAR(placed_on)));.
• Invisible indexes (8.0) — ALTER TABLE t ALTER INDEX idx INVISIBLE hides one from the optimizer while it is still maintained, so you can test dropping it safely.

Practise

The exercises run on SQLite behind a MySQL layer, so they judge the rows your queries return, not the plan. You will create an index and run the lookup it serves, and then measure the selectivity of candidate columns — the number you should look at before creating any index.