How Does a B-Tree Index Work Internally?
Learn how a B-tree index is structured, how lookups descend the tree, and why linked leaves make range scans fast.
Expected Interview Answer
A B-tree index is a balanced, sorted tree of fixed-size nodes where every leaf sits at the same depth, letting the database find any key in O(log n) disk reads by repeatedly narrowing a range at each internal node.
Each internal node stores an ordered array of separator keys and pointers to child nodes; a search compares the target key against the separators to decide which child to descend into, repeating until it reaches a leaf. Leaves store the actual key plus a pointer to the row (or the row itself, for a clustering index), and are typically linked together so range scans can walk sideways without climbing back up. Because nodes are sized to match a disk page, and the tree stays balanced through splits and merges on insert and delete, lookups, range scans, and ordered traversal all stay fast even as the table grows to millions of rows.
- Logarithmic-time point lookups
- Efficient ordered range scans via linked leaves
- Stays balanced automatically on insert and delete
- Matches disk page size for minimal I/O per level
AI Mentor Explanation
Think of a national player registry organized as zone folders, then state folders inside each zone, then a final alphabetical player list inside each state folder — three hops narrow millions of players down to one shelf. A B-tree searches the same way: each internal node’s separator keys tell you which child folder to open next, and you only read a handful of folders instead of scanning every player. The leaf-level lists are also strung together so browsing "all players from M to Z" means walking sideways through a few linked folders, not reopening the zone index each time.
Descending a B-Tree Index to Find a Key
Root node
- separator keys
- child pointers
Internal node
- separator keys
- child pointers
Leaf node
- key
- row pointer
- next-leaf link
Step-by-Step Explanation
Step 1
Start at the root
Compare the search key against the root node’s separator keys to pick a child pointer.
Step 2
Descend through internal nodes
Repeat the comparison at each level, narrowing the range by one node per hop.
Step 3
Reach a leaf node
The leaf holds the matching key plus a pointer to the row, or the row itself for a clustered index.
Step 4
Walk linked leaves for ranges
For range queries, follow the leaf-to-leaf links sideways instead of re-descending the tree.
What Interviewer Expects
- Explanation of how internal nodes route searches level by level
- Understanding that all leaves sit at the same depth (balanced tree)
- Awareness that leaves are linked to support efficient range scans
- Knowledge that node size is tied to disk page size to minimize I/O
Common Mistakes
- Confusing a B-tree with a binary search tree (nodes hold many keys, not one)
- Forgetting that leaves are linked for range scans
- Not mentioning that the tree self-balances on insert and delete
- Assuming lookup cost grows linearly instead of logarithmically
Best Answer (HR Friendly)
“A B-tree index is a balanced, multi-level tree where each node holds a sorted set of keys pointing to the next level down, so finding any row takes only a handful of steps even in a huge table. Because it stays balanced and keeps its bottom-level entries linked in order, it is efficient both for looking up a single value and for scanning a range of values.”
Code Example
-- Most databases default to a B-tree index type
CREATE INDEX idx_orders_order_date
ON Orders (order_date);
-- Point lookup: descends the tree in O(log n) reads
SELECT * FROM Orders WHERE order_date = '2026-01-15';
-- Range scan: descends once, then walks linked leaves sideways
SELECT * FROM Orders
WHERE order_date BETWEEN '2026-01-01' AND '2026-01-31'
ORDER BY order_date;Follow-up Questions
- How does a B-tree stay balanced when rows are inserted or deleted?
- Why is a B-tree preferred over a binary search tree for disk-based storage?
- What is the difference between a B-tree and a B+ tree?
- How does node fan-out affect the height of the tree?
MCQ Practice
1. Why do B-tree nodes typically hold many keys instead of just one like a binary tree?
Wide nodes sized to a disk page mean each level read pulls in many keys at once, reducing tree height and disk I/O.
2. What guarantees that a B-tree lookup takes roughly the same number of steps for any key?
A B-tree is balanced so every leaf is at the same depth, giving consistent, predictable lookup cost for any key.
3. What makes B-tree indexes efficient for range queries like BETWEEN?
Once the scan reaches the starting leaf, it follows leaf-to-leaf links to read the rest of the range without re-descending the tree.
Flash Cards
What is a B-tree index? — A balanced, multi-level tree structure where internal nodes route searches and leaves hold keys with row pointers.
Why are all leaves at the same depth? — Because the tree self-balances on insert and delete, guaranteeing consistent lookup cost.
How do B-trees support range scans efficiently? — Leaf nodes are linked together in sorted order, so scans move sideways instead of re-searching the tree.
Why match node size to disk page size? — To read as many keys as possible per disk I/O, minimizing the number of levels traversed.