Postgres in depth · Chapter 47 of 65

How a B-tree finds a row

By the end of this chapter you can open a B-tree index page by page with pageinspect, follow Postgres's own path from the root to one row, and explain why some keys make an index bigger than others. Build it in your browser: a real editor and terminal, AI that explains, and tests that tell you when it works.

  • Part: Inside Postgres
  • 4 tasks
  • PostgreSQL
  • In the all labs plan

The first 2 chapters of Postgres in depth are free. This one comes with the all labs plan.

Why you need this

Sana looks up one lesson event among 200,000 and the answer comes back in 0.02 ms. Priya says "it's the index", but an index is just more 8 KB pages in a file (chapter 42). How can four pages out of thousands be enough? And why did the team that switched to random uuid keys see its index grow by a third? You have used indexes as a black box; today you open one.

What you build: 4 tasks

Each task has tests. You write the code in the lab's editor and press Check.

  1. Task 1

    tree-shape.sql: the shape of a B-tree

    The Check builds lesson_events exactly as the lesson does, with the index lesson_events_lesson_idx on lesson_id. Describe that tree in one row: the block number of its root, how many levels it has (counting the leaf level), how many leaf pages it has, and how many pages sit above the leaves (the root included).

    Return four columns: root, levels, leaf_pages and internal_pages.

    Careful: block 0 is the metapage, not a tree page, and the metapage numbers the leaf level 0.

  2. Task 2

    find-entry.sql: the index entry behind one row

    Sana is chasing lesson event 123456. Find the entry of the primary key index lesson_events_pkey that points at that row: the block number of its leaf page, the entry's item offset on that page, and the heap tuple id it points to.

    Return three columns: leaf_block, itemoffset and htid.

    Careful: an index entry stores the row's address (its ctid), not its id; ask the table for the row's ctid instead of typing it.

  3. Task 3

    dedup.sql: what deduplication saves

    lesson_events_type_idx indexes event_type, which has five values over 200,000 rows. Create a second index on the same column called lesson_events_type_nodedup, with deduplication switched off, then return the size in pages (8 KB each) of both indexes.

    Return two columns: index_name and pages, one row per index. Any order.

    Careful: deduplication is a storage parameter of the index, given when you create it.

  4. Task 4 · interview question

    Interview: random-keys.sql, random keys and page splits

    "Why do random uuid primary keys make an index bigger?" The Check builds seq_keys and random_keys as the lesson's last code block does: 100,000 rows each, inserted one key after another, in increasing order for seq_keys and in random order for random_keys.

    Return the number of leaf pages and the average leaf density of both primary key indexes, random_keys_pkey and seq_keys_pkey.

    Return three columns: index_name, leaf_pages and avg_leaf_density. Order by index_name.

    Careful: pgstattuple's index function measures a B-tree; create the extension once in your own database.

What you will learn

  • The B-tree's shape: the metapage, the root, internal pages, leaves, and levels.
  • bt_metap, bt_page_stats, bt_page_items: pageinspect's B-tree functions.
  • The search: from the root to a leaf entry to the row's ctid.
  • Page splits and deduplication: why insert order and repeated values change an index's size.

More in Inside Postgres

Build "How a B-tree finds a row" yourself

LCO, an edtech company, moves its platform onto a single Postgres server you run. A real editor and terminal in your browser, AI that explains, and a Check that says when it works.

The first 2 chapters of Postgres in depth are free. This one comes with the all labs plan.