Expert · Module 27 · Lesson 1 of 5
Postgres B-tree indexes
How Postgres stores indexes in 8 KB pages: Lehman–Yao high keys, splits that cascade to a new root, the fillfactor rule, and how dead and duplicate index tuples get reclaimed.
By the end you can
- Explain why a Postgres index is a tree of 8 KB pages and how a search descends it using high keys
- Predict where a page split happens, what the parent receives, and when the tree grows a level
- Describe how bottom-up deletion and deduplication reclaim space from dead and duplicate index tuples
Builds on B-trees and pages.
01 · A question first
An equality lookup on a table with a hundred million rows can finish in four page reads: three internal pages and one leaf, each 8 KB. The tree inside Postgres does it with a high key on every page except the rightmost one, splits that leave the right edge near 90% of full, and a root that is the only page allowed to add a level. This lesson follows those rules one insert at a time.
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Why an index is a tree of pages
- What one page contains
- High keys and the race to the right
- The trace above: splits that pay for themselves
- Reading sideways
- Dead and duplicate tuples
- Where you will meet it
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
03 · Practice
Something wrong with this lesson? Report a problem