How a B-tree index works
On This Lesson 4 topics
This lesson is planned. The outline below lists the topics it will cover. The full lesson has not been published yet.
In this lesson
explain why a B-tree finds rows in a few page reads.
Planned topics
- A B-tree is a balanced tree of sorted pages: root, internal pages, leaf pages that point to table rows (heap tuples).
- A lookup descends only 3–4 levels even for millions of rows.
- Sorted leaves make equality, range, and
ORDER BYfast. - It cannot help with
LIKE '%abc'or with a function wrapped around the column. - Pages are 8 kB and hold many entries, so the tree stays shallow.
Draft outline details
Demonstration
a diagram of a root, two internal pages, and leaf pages with customer_id values; trace a lookup of 4711. Optionally inspect tree height with the pageinspect extension (verify availability before recording).
Check your understanding
Why does an index lookup on 10 M rows need only a few page reads?
Show answer
The tree is shallow and wide.
Practice
Apply this lesson with the module's lab, exercises and quiz.
Marking a lesson complete is optional and you can undo it any time. Your progress stays in this browser.