Lesson 01 · 14 min
How an index works inside
The B-tree, column order in a composite index, covering indexes, and the cases where an index does not help.
14 minLesson 1 of 10Practice includedAsk AI on any point
In the basic course we created an index and saw Index Scan in EXPLAIN. Now let's look at what actually sits on disk. It decides which queries the index will speed up and which it will not.
The B-tree: pages, levels, leaves
A plain CREATE INDEX in PostgreSQL creates a B-tree. It is a balanced tree of 8 KB pages. The root and inner pages store separator keys and pointers down. Leaf pages store sorted keys and the row address in the table (TID). Leaves are linked to each other, so a BETWEEN range is read sequentially, without going back to the root.
- The tree is wide: one page holds hundreds of keys. For tens of millions of rows the depth is usually 3 or 4 levels.
- Looking up one value: a few index page reads plus one table page read.
- Keys are sorted, so a B-tree works for
=,<,>,BETWEEN,ORDER BYandLIKE 'abc%'(non-C collations needtext_pattern_ops). - Every index is updated on each INSERT, each UPDATE of the key, and each DELETE. Indexes speed up reads and slow down writes.
Composite index: column order matters
The index (user_id, created_at) is sorted by user_id first, and within one user by created_at. Like a phone book: by last name, then by first name. Finding everyone named Smith is easy, finding every John without a last name is not.
Covering index and Index Only Scan
If every column the query needs is in the index, the database does not have to visit the table. In the plan this is an Index Only Scan. Extra columns you do not search by are added with INCLUDE: they live only in the leaves and do not affect sorting.
When the index is not used
- A function on the column:
WHERE lower(email) = '[email protected]'does not see an index onemail. Fix: an expression indexCREATE INDEX ON users (lower(email)). - A leading wildcard:
LIKE '%gmail.com'does not use a B-tree. For substring search there is GIN withpg_trgm. - Type mismatch: comparing a column with a value of another type may need a cast and break the plan.
- Low selectivity: if the condition returns a large share of the table, a sequential read is cheaper than thousands of random jumps from the index.
- A small table: reading a few pages in full is simpler.
- Stale statistics: the planner misjudges the number of rows.
ANALYZE orders;helps.
- PostgreSQL: Index types, extensions, when to choose it
Check
Lock it in before you move on
1. There is an index
(user_id, created_at). Which query uses it best?2. Why add
INCLUDE (total)to an index?3. Why does
WHERE lower(email) = ...ignore a regular index on email?4. A condition returns 60% of the rows of a large table. What will the planner most likely choose?