B+ tree indexes
An index is a separate structure that lets the database find rows without scanning the whole table. The B+ tree is the workhorse index of relational databases.
What an index is
An index maps search-key values to the locations of matching rows, like the index of a book mapping topics to page numbers. Without an index, a query filtering on a column must examine every row. With one, the database can jump to matching rows, typically turning O(n) scans into O(log n) lookups plus the rows actually needed.
B+ tree structure
A B+ tree is a balanced, multiway search tree. Internal nodes hold only keys that guide the search; leaf nodes hold the keys together with row pointers, or the rows themselves, and are linked to their neighbours in key order. Each node fills a page, so with hundreds of keys per node, the tree is only 3 or 4 levels deep even for billions of rows.
Lookups and range scans
An equality lookup descends from the root to one leaf: about 3 or 4 page reads, with the top levels usually already in the buffer pool. A range query, such as all orders between two dates, finds the first matching leaf and then follows the leaf links in order, reading only the leaves holding matching keys. This sequential behaviour makes B+ trees excellent for ranges and sorting.
Insertion and deletion
Insertion places a key in the correct leaf. If the leaf overflows, it splits into two, and a separator key is copied up into the parent, which may split in turn; if the root splits, the tree grows a level. Deletion may merge or redistribute underfull nodes. All leaves remain at the same depth, so performance never degrades the way an unbalanced tree's would.
Clustered and secondary indexes
A clustered index determines the physical order of rows; a table can have only one. In InnoDB, the primary key index is clustered and holds the full rows. Secondary indexes on other columns store the key plus a reference to the row, such as its primary key, so a lookup through a secondary index may need a second traversal to fetch the full row.
Composite and covering indexes
A composite index covers several columns in order, such as (last_name, first_name). It serves queries filtering on last_name, or on last_name and first_name, but generally not first_name alone: the leftmost-prefix rule. A covering index contains every column a query needs, so the database answers from the index alone without visiting the table, an index-only scan.
Costs of indexes
Indexes are not free. Every insert, update, or delete must also update every affected index, slowing writes; each index uses storage; and the optimiser must consider more options. Good practice is to index columns used frequently in WHERE clauses, joins, and ORDER BY, especially selective ones, and to remove indexes that queries never use.
Worked example
A table of 100,000,000 users with an index on email. Each 16 KB B+ tree node holds roughly 400 entries. Levels hold 400, 160,000, 64,000,000, and then 25.6 billion entries, so 4 levels cover 100 million emails. A login lookup by email needs about 4 index page reads, often only 1 or 2 from storage because upper levels are cached, plus one read for the row, instead of scanning millions of pages.
Key takeaways
Indexes map key values to row locations, avoiding full scans. B+ trees keep routing keys in internal nodes and data or pointers in linked leaves, with node-sized pages giving only 3 or 4 levels. Equality lookups follow one path; range scans walk linked leaves. Splits and merges keep all leaves at equal depth. A table has at most one clustered index; secondary indexes may need a second lookup. Composite indexes follow the leftmost-prefix rule; covering indexes allow index-only scans. Indexes speed reads but slow writes and use space.
Flashcard
Maps key values to row locations
Check your understanding
An index exists on (country, city). Which query can use it most effectively?