Scan or index
The app asks for books from 2006. With no index, the DBMS cannot know where those rows are, so it reads every row and tests its year: a sequential scan. 6 rows here; in a big table, millions.
CREATE INDEX year_idx ON books (year); builds a second structure. The DBMS reads each row once and copies two things: the year and a pointer to the row. Then it sorts the copies by year.
The sorted entries fill leaf pages, and each leaf links to its neighbours. A root page holds the separator 2002: smaller years are in leaf 1, 2002 and up in leaf 2. This is a B-tree, PostgreSQL’s default index.
Searching the tree
Now WHERE year = 2006 uses the index. It starts at the root: 2006 is not below 2002, so it follows the pointer to leaf 2. One comparison skipped a whole leaf; with hundreds of keys per page, each level skips far more.
In leaf 2 the entries are sorted, so 2006 is quick to find. Its pointer says row 4. The DBMS reads just that row: The Road. Root, leaf, row: the steps grow with the tree’s height, not the table’s size.
WHERE year BETWEEN 1990 AND 2010 goes down once, to the first year that could match: 1998. Then it walks right along the leaves, 2002, 2006, and stops at 2012. The answers come out already sorted by year.
The price of an index
Now the front desk adds Piranesi (2020). The table gets row 7, and the index must also get (2020, row 7), in sorted order, in leaf 2. Every index on a table adds work to every insert.
Leaf 2 is full, so it splits: 2002 and 2006 stay, 2012 and 2020 go to a new leaf 3, and the root gains the separator 2012. When a root fills up it splits too, and the tree grows a level taller.
You never tell SQL to use an index; the planner decides by estimated cost. EXPLAIN shows its choice: Index Scan using year_idx. When a query needs most rows, or the table is tiny, a Seq Scan is cheaper and wins.
Each index takes disk space and adds work to every insert, to every update of its column, and to clearing out deleted rows. Index the columns you often filter, join or sort on, where a query keeps few rows. Then check with EXPLAIN.
What happens
;; step 1/10 · scan SELECT name FROM books WHERE year = 2006; plan: Seq Scan on books row 1 1965 = 2006? no row 2 2002 = 2006? no row 3 1998 = 2006? no row 4 2006 = 2006? yes keep row 5 2012 = 2006? no row 6 1988 = 2006? no 6 rows read to find 1 the work grows with the size of the table
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. 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.