CSE Roadmap

Core tier · about 3 hours · 5 parts

Part 3 of 5 · 1 min read

Internal nodes, leaf nodes, and the linked leaf chain

Internal nodes route the search; leaf nodes are linked together in sorted order.

Think of the phone book's thumb-tabs on the side of the pages, each tab marking a letter range, while the actual pages behind each tab sit in one continuous, ordered sequence.

In plain words: a B+-tree's internal nodes hold only keys and pointers to child nodes, used purely to route a search toward the right leaf, matching the general search-tree idea from the previous page. The leaf nodes hold the actual key and row-pointer entries, and are additionally linked to each other in sorted order, leaf to leaf, forming one continuous chain. This leaf chain is exactly what makes range scans efficient: once the first matching leaf is found, the rest of the range is read by following the chain forward, without ever going back up to the internal nodes.

A worked example. Scanning placed_on BETWEEN '2026-01-01' AND '2026-01-31' finds the leaf holding January 1st once, then follows the leaf chain forward through every later date in January, without repeating any tree traversal.

The key lines. No new SQL; the leaf chain is an internal structural detail of how the earlier range query executes.

Leaf chain

A B+-tree's leaf chain is the set of pointers linking leaf nodes together in sorted key order, letting a range scan move from one leaf to the next without retraversing the tree.

Example: the continuous ordered run of phone-book pages behind the alphabet tabs is the leaf chain; the tabs themselves are the internal nodes.