Indexes in depth
Without an index, a DBMS must read every row to answer WHERE year = 2006. Watch CREATE INDEX copy each year and a pointer to its row into a sorted B-tree, follow a lookup from the root to one leaf and on to one row, walk a range along the linked leaves, and see a full leaf split when a new row arrives. Then read the plan with EXPLAIN and learn what an index costs.
5 quick questions
Pick an answer to see why. Your score saves with your progress.
01The books table has no index on year. What does the DBMS do to answer SELECT name FROM books WHERE year = 2006?
Rows in a table are in no useful order for year, so without an index the only way to be sure is to read and test every row. EXPLAIN shows this as Seq Scan on books.
02What does CREATE INDEX year_idx ON books (year) store?
Each index entry is the key (here the year) and a pointer to the table row (PostgreSQL calls it a TID). The entries are kept sorted in leaf pages, with a root of separator keys above them.
03The root holds the separator 2002. Leaf 1 holds 1965, 1988, 1998 and leaf 2 holds 2002, 2006, 2012. Which pages does a lookup for year = 2006 read?
2006 is not below 2002, so the root sends the lookup to leaf 2. There it finds 2006 with a pointer to row 4, The Road. Leaf 1 is never read.
04Why can WHERE year BETWEEN 1990 AND 2010 ORDER BY year return its rows already sorted, with no sort step?
The walk visits 1998, 2002, 2006, 2012 and stops at 2012. Leaves are sorted and linked, so the matches come out in year order: Holes, Coraline, The Road.
05Piranesi (2020) is inserted. Leaf 2 already holds 3 of 3 entries. What happens to the index?
Every insert must add an entry to every index on the table. A full leaf splits in two and its parent gains a separator; when a root splits, the tree grows one level taller, so every leaf stays at the same depth.
Glossary
- Index
- A separate structure that a DBMS keeps next to a table so it can find rows by a column's value without reading every row.
- Sequential scan
- Reading every row of a table and testing each one. EXPLAIN in PostgreSQL shows it as Seq Scan.
- B-tree
- PostgreSQL's default index type: sorted leaf pages of entries, linked to their neighbours, under inner and root pages of separator keys.
- Leaf page
- A bottom page of a B-tree. Each entry holds a key and a pointer to a table row.
- Separator key
- A key in a root or inner page that says which page below to visit: smaller keys go left, equal or larger go right.
- Row pointer (TID)
- Where a row lives in the table: in PostgreSQL, the page number and the row's position on that page.
- Page split
- What happens when a new entry does not fit in a full page: half the entries move to a new page and the parent gains a separator.
- Query planner
- The part of the DBMS that chooses how to run a query, for example a Seq Scan or an Index Scan, by estimated cost. EXPLAIN shows its choice.
Notes and sources
- The figure’s leaves hold 3 entries. A PostgreSQL page is 8 kB, and an entry for an integer key takes about 20 bytes, so a full leaf holds about 407. A million rows then need only 3 levels: a root, one inner level and the leaves.
- The row pointer is what PostgreSQL calls a TID: the table page number and the row’s position on that page. The figure writes it as a row number.
- This is the textbook B+-tree split (half the entries move right). PostgreSQL chooses the split point more carefully, for example leaving the left page nearly full when new keys keep arriving at the right end.
- PostgreSQL picks plans from cost estimates. On a table of six rows it would read the one table page (Seq Scan); the Index Scan on the card is the plan for the same query on a large table. SQLite uses the index even here.
- An UPDATE that changes no indexed column can often skip the index in PostgreSQL (a heap-only tuple, HOT update). A DELETE leaves the row’s index entries in place; VACUUM removes them later.
- Without ORDER BY, SQL promises no order. The range query asks for ORDER BY year, and the B-tree gives that order for free.
- SQLite versions before 3.36 print SCAN TABLE books instead of SCAN books; the meaning is the same.
- PostgreSQL documentation: Indexes, Introduction
- PostgreSQL documentation: Index Types
- PostgreSQL documentation: B-Tree Indexes (implementation)
- PostgreSQL documentation: Multicolumn Indexes
- PostgreSQL documentation: Using EXPLAIN
- PostgreSQL documentation: Database Page Layout
- PostgreSQL documentation: Heap-Only Tuples (HOT)
- SQLite: EXPLAIN QUERY PLAN
- SQLite: Query Planning
- Python documentation: sqlite3
- Silberschatz, Korth and Sudarshan, Database System Concepts, 7th ed., ch. 14 Indexing
Quiz Unlocks after the last step.