Describe how a B+tree index is laid out in storage: what does an internal (branch) node contain versus a leaf node, and how does a key lookup use each of them?
answer
- Internal = separators + child pointers, no data
- Leaves = all keys, sorted, + row pointer
- n keys → n+1 children
- All leaves same depth (balanced)
- Node size = page size = I/O unit
basics
~20 sA B+tree is a balanced tree of page-sized nodes. Internal nodes store only separator keys and child pointers used to route a search downward. Leaf nodes store every indexed key in sorted order with a pointer to the row. A lookup descends root to leaf.
solid answer
~60 sA B+tree index is a balanced search tree whose nodes are storage pages (commonly 4-16 KB). There are two node kinds: - **Internal (branch) nodes** hold *separator keys* and *child pointers* only — no row data. A node with n keys has n+1 children; the keys say "everything below this pointer is < K1, then between K1 and K2, ...". Their only job is routing. - **Leaf nodes** hold *every* key in the index, in sorted order, each paired with a pointer to the row (a row id, or the primary key in a clustered table). Leaves usually sit in a linked list so the engine can walk in key order. All leaves are at the same depth — the tree is balanced by construction, so every key costs the same number of page reads. A lookup starts at the root page, binary-searches within the page to pick the right child, follows the pointer, and repeats until it hits a leaf; there it binary-searches for the key and gets the row pointer. Cost is roughly one page read per level plus the row fetch.
code
text · 8 linesroot (internal)
[ 100 | 250 ]
/ | \
v v v
[..99] [100..249] [250..] <- internal or leaf level
leaf page (sorted entries)
101->rid(7,3) 104->rid(2,9) 110->rid(7,4) ... --> next leafgo deeper
Be able to state the two node kinds, that leaves hold all keys in sorted order with row pointers, and that a lookup walks root-to-leaf.
Add why nodes are page-sized, that entries within a page are binary-searched, and that balance makes every lookup cost the same.
Connect layout to the cost model: page reads per level, upper levels cached, and which query shapes (equality, range, ordered output, prefix) the layout serves.
Frame it as a disk-oriented design choice — maximizing decisions per page touched — and discuss where that assumption weakens, such as memory-resident or write-optimized structures.
## What a B+tree index is An index is a separate structure the engine maintains next to the table so it can find rows by key without reading every row. Almost every relational engine's default index is a **B+tree**: a balanced, multi-way search tree in which each node occupies exactly one storage **page** — the fixed-size block (commonly 4 KB, 8 KB or 16 KB) that is the unit of disk I/O and of buffer-pool caching. Node size is page size because the engine pays for a page whether it reads one byte of it or all of it, so the structure is designed to extract maximum decision-making from each page it touches. ## Internal nodes: pure routing An internal (branch) node contains only **separator keys** and **child pointers** (page numbers). If a node holds keys `K1 < K2 < K3`, it holds four child pointers: subtree with keys `< K1`, `[K1, K2)`, `[K2, K3)`, `>= K3`. There is no row data and, in a B+tree, no payload attached to those separators. A separator does not even have to be a key that exists in the table — it only has to divide the key space correctly. Because internal entries are small (key plus a 4-8 byte page pointer), hundreds of them fit in one page. That is what makes the tree wide and shallow. ## Leaf nodes: the actual index entries Leaf nodes contain **every indexed key value**, held in sorted order within the page, each paired with a **row pointer**. What the pointer is depends on the storage model: in heap storage it is a physical row identifier (file, page, slot); in an index-organized/clustered table the leaves of the primary index hold the full row itself, and secondary index leaves hold the primary key. Leaf pages are typically linked to their neighbours, so once you land on a leaf you can walk forward in key order without going back through the root. All leaves live at the same depth. The tree is kept balanced by construction: a node that overflows on insert is split and a separator is pushed up, which is the only way the tree ever grows a level. So there are no long and short paths — every key costs the same number of page accesses. ## How a search actually runs 1. Read the **root** page (in practice it is permanently in cache). 2. **Binary-search inside the page** to find which separator interval the search key falls in; follow that child pointer. 3. Repeat for each level. 4. At the leaf, binary-search for the key and read the row pointer. 5. Fetch the row, unless the index alone answers the query. So the work is two-tiered: *between* pages you navigate a tree (one page read per level), *within* a page you do an in-memory binary or linear search over a sorted slot array. Only the between-page steps can cost I/O, which is why level count, not key count, dominates the cost model. ## Why B+tree instead of a binary search tree A binary tree over 1 billion keys is about 30 levels deep, and each level is potentially a separate random page read: 30 I/Os per lookup. A B+tree with a fanout of ~500 covers the same billion keys in four levels. The difference is entirely about the *branching factor*: on disk, the expensive thing is the number of pages touched, so you want each page touched to eliminate as much of the search space as possible. High fanout is the whole design intent. Balance matters for the same reason. An unbalanced tree fed sorted inserts degenerates toward a linked list, and worst-case lookups become linear. B+tree splits guarantee the worst case equals the average case. ## What the layout buys you Because leaves hold all keys in sorted order and are linked, one structure serves several access patterns: equality lookup, range predicates, prefix matching on the leading column, ordered retrieval without a separate sort, and min/max by walking to the leftmost or rightmost leaf. What it cannot serve is a predicate that does not preserve the key ordering — for example a search on an arbitrary transformation of the column, which needs a different index definition entirely. ## The one-line summary to say out loud Internal nodes are a routing directory of separators; leaves are the sorted, complete list of keys plus row pointers; all leaves are at the same depth; a lookup is one page read per level plus the row fetch.
- Why do B+tree leaf pages link to their neighbours?So that after locating the first qualifying key the engine can continue in sorted order by following the sibling pointer, instead of re-descending from the root for each subsequent key. That makes ordered retrieval and range predicates a sequential leaf walk rather than repeated tree traversals. It also means the index can supply rows already sorted by the key, avoiding a separate sort step.
- Does an internal node's separator key have to be a value that exists in the table?No. A separator only has to correctly partition the key space, so engines are free to store a shortened or synthetic boundary value — for example just enough leading bytes of a string to distinguish the two subtrees. Shorter separators pack more entries per page, raising fanout. The complete, authoritative set of key values lives only in the leaves.
- How does the tree stay balanced as rows are inserted?Inserts always go to the correct leaf; if that leaf page is full it splits into two and a separator key is propagated up to the parent. If the parent is full it splits too, and if the split reaches the root a new root is created — which is the only way the tree gains a level. Because growth happens at the root rather than at the leaves, every leaf stays at the same depth.
A phone book with tabbed dividers: the tabs (internal nodes) only tell you which section to open, and the printed entries (leaves) are all in the pages themselves, in alphabetical order.
saying these in an interview costs you the question
- Saying internal nodes store row data — in a B+tree only leaves carry keys with row pointers
- Describing a B+tree as a binary tree, so each node has two children
- Claiming the tree can be unbalanced and degrade to a list with sorted inserts
- Thinking a lookup scans the leaf level linearly instead of descending from the root
- Assuming a node is one key rather than a page holding hundreds of entries