BiteSizedChunks.comLearn one small thing at a time.
Course contentsShow
← Databases & SQL
Lesson 837 of 1,9538. PostgreSQL InternalsFree lesson

Index Storage and B-Tree Layouts

You will describe how B-tree indices manage branch and leaf nodes to facilitate logarithmic search times.

In this lesson, you will learn how B-tree indices use a hierarchical structure to turn slow full-table scans into lightning-fast logarithmic searches.

The Structure of a B-tree

In PostgreSQL, a B-tree index isn't just a flat list of values; it is organized into a tree of pages. Think of a standard 8KB page as a container holding either pointers to other pages or actual data references. The B-tree is divided into two primary types of nodes: Branch Nodes and Leaf Nodes.

Branch Nodes: The Road Signs

Branch nodes act as the navigation system of the index. They contain keys that serve as boundaries, telling the database which child page to visit next. When you search for a specific value, the database starts at the Root Node (the top-level branch) and compares your target value against the keys stored there. Based on this comparison, it "drops down" to the appropriate child page. This process continues through successive branch levels until the database reaches the bottom of the tree.

Leaf Nodes: The Destination

Leaf nodes are the bottom layer of the B-tree. Unlike branch nodes, leaf nodes do not point to other index pages. Instead, they contain the actual indexed values and a TID (Tuple Identifier), which is a direct pointer to the physical location of the row in the table (the heap).

For example, if you search for WHERE id = 500:

  1. The engine checks the Root, sees that id < 1000 is in the left branch, and follows it.
  2. It hits a Branch, sees that id > 400 is in the middle sub-branch, and follows it.
  3. It arrives at a Leaf, finds the entry for 500, and uses the attached TID to fetch the row from the table instantly.

Because the tree is balanced—meaning every leaf node is exactly the same distance from the root—every search operation performs roughly the same number of steps. This ensures predictable, logarithmic performance, allowing the database to find one specific record among millions with just three or four page reads.

Key Takeaway: By using branch nodes as a map to navigate down to leaf-level pointers, B-trees ensure that the database performs a predictable, logarithmic number of steps to locate any record.