Interview question. A database uses a B-tree index for lookups and ordered scans. An insert targets a leaf page that is already full. Walk through how the tree makes space, what changes in the parent, and how this affects concurrent readers and writers. Then explain how mostly increasing keys differ from random keys.
Assume a conventional disk-oriented B-tree family, with a page-based index and crash-safe structural changes provided by the database. Details vary by engine. Our primary example is PostgreSQL's B-tree index, where leaves contain entries referencing table rows. 1
Think first
A B-tree index has several hundred million keys. New rows are inserted into a leaf page with no free space while other sessions are reading the same key range. Explain exactly what changes in the tree and what must remain safe for concurrent searches. Then compare increasing IDs with random IDs.
Take a few minutes to form an approach, then compare it with the worked explanation.
Reveal the worked explanation
First understand why the tree stays shallow
With a hash map, we found the latest offset through an in-memory directory. A B-tree does something different. It stores keys in sorted pages and lets a reader descend through a small number of index levels without keeping an entry for every key in memory.
Picture a root that identifies several key ranges. Each child internal page narrows the range further. A leaf holds sorted entries for actual indexed keys. In PostgreSQL, leaf entries normally identify heap tuples rather than storing the entire row. That distinction matters. Reaching the leaf may be followed by a separate table-page fetch. 1
A useful numerical thought experiment is a tree with average fanout 200 and four routing steps. 200^4 is 1.6 billion. Actual page occupancy, separator sizes, roots, duplicates, and leaf layouts change that calculation, but it explains why a tree storing an enormous number of entries need not have hundreds of levels. Most upper pages are also likely to stay cached.
Now insert a key in a leaf with no free space.
A leaf split is a structural change
The engine cannot simply append a new unsorted record to that leaf and still use the same ordered search procedure. It allocates another page and divides the relevant key range between the two leaves. It adds a separator or downlink in the parent so future searches can choose the correct leaf. If the parent has no room for the new downlink, the change can propagate upward. When the root itself splits, the tree gains a level. PostgreSQL documents this recursive structure. 1
A full B-tree leaf splitting into two leaves and adding a parent separator
This is not a full rewrite of the index. The engine changes a bounded set of pages along the affected path, although a cascading split can touch more than the original leaf. Correctness depends on carefully publishing these structural changes. Another session may be navigating the tree while the split happens.
For interview reasoning, distinguish two kinds of coordination. An index-page latch protects an in-memory structural operation so a reader does not observe an impossible page layout. A transactional row lock coordinates logical modifications made by concurrent transactions. Those have different lifetimes and purposes. Treating every index latch as a long-lived business lock gives the wrong performance model.
An implementation may also maintain sibling links, high keys, and recovery records so searches can navigate safely during a concurrent split. PostgreSQL's implementation is in the Lehman and Yao family of high-concurrency B-tree designs, but the exact algorithm depends on the engine. 2
Why key order changes the workload
Now consider two workloads. The first inserts monotonically increasing order IDs. The second inserts independent random IDs.
Increasing keys repeatedly target the right edge of a B-tree. That can give good locality and a predictable insertion pattern, but also concentrate concurrent writers on rightmost pages. Random keys spread inserts across more leaves. They can reduce that particular hotspot while increasing random page touches, cache misses, and split pressure across the tree.
It would be inaccurate to declare that random keys always make a B-tree slow or that sequential keys always scale better. The answer depends on insertion concurrency, page cache size, index width, free space, batching, and the implementation's behavior for rightmost splits. PostgreSQL's index code, for example, has separate fill-factor behavior for rightmost and other leaf splits. 3
A wider primary key also changes more than the index's byte count. In engines where secondary indexes carry the primary key as the row locator, wider keys enlarge those secondary entries too. That is one reason a key-generation decision belongs in a storage discussion rather than only in an API-design discussion.
An index is not the table
Suppose SELECT name FROM users WHERE email = ? uses a B-tree on email. If the index carries the required output and the engine's visibility rules permit an index-only result, it may avoid some heap access. Otherwise a lookup through the index is followed by a table read. An index that appears efficient by itself can still cause many random row fetches when the predicate matches a large fraction of the table.
That observation leads to a useful rule for answering indexing questions. First identify the query pattern, then the index search, then what data must still be fetched, and finally the write cost of maintaining the structure. An index is another structure that every relevant write may need to update. We should not recommend one without estimating that maintenance cost.
A full leaf is therefore not a catastrophe. It is a planned maintenance event inside a data structure built for changing data. The important costs are page work, concurrency on the affected path, additional log and disk traffic, and possible fragmentation under the workload.
At very high update rates, a different family of engine delays sorting and reorganizing its data rather than maintaining the same tree structure on every write.
How can a database accept random key updates in memory and later produce ordered files on disk?
Go deeper
Think in pages, not just asymptotic notation
A B-tree search is often described as O(log N), but in practice the number of cache misses and page reads may matter more than the logarithm. Internal pages can remain memory-resident while leaf or heap pages require I/O. For an index with an illustrative fanout 200, four routing decisions could cover over a billion positions, but the calculation is not a universal page-count guarantee.
An index page split also has a persistence dimension. A crash between allocating a new page and making the parent link visible must not leave a permanently disconnected subtree. A mature engine logs or otherwise atomically protects the structural transition. The local WAL discussion in the previous lesson is relevant here, but this lesson's distinct question is which pages and references change.
Under MVCC, multiple physical index entries may represent versions of one logical row. Cleanup, deduplication, and reuse of space can postpone splits. PostgreSQL documents bottom-up index deletion and other techniques used to control version churn. 1
A B-tree index and an LSM tree are not the only alternatives. Hash indexing can help point reads, and an append-only log plus memory directory can be very efficient for a bounded live key set. But that directory does not naturally support ordered range scans. The workload determines what organization work should occur on the foreground write path and what can safely happen later.
Check your reasoning
Explain internal separators, leaf entries, and why the tree stays shallow through high fanout.
Describe splitting a full leaf and adding a new parent downlink, including a possible cascading split.
Distinguish short-lived page latches from application transaction row locks.
Discuss rightmost-page concentration versus random-page touches without universal claims.
Remember that a PostgreSQL index leaf usually points to a heap tuple and reads can still fetch table pages.
Common mistake: Calling an insert O(log N) without discussing which pages change or assuming the index leaf stores the entire table row.
Read the answer explanation
The parent can split too, potentially propagating to the root. — The new child downlink must be represented in the parent structure. A full parent may split, and a root split can increase tree height.
Apply it elsewhere
Your table has a highly selective index, yet the indexed query is slow when it returns 300,000 rows. What does the B-tree not solve?
Compare your approach
It can locate matching index entries efficiently while still requiring many heap page fetches, potentially scattered across storage. Compare a sequential scan, covering index, and query selectivity.
One more constraint
Would a larger B-tree page always make inserts faster? What new costs appear?
Quick revision
A B-tree organizes sorted index entries into fixed-size pages. A lookup descends through internal separator pages to a leaf, and in a heap-based engine may then fetch the table row. When an insert finds a full leaf, the engine allocates another leaf, redistributes entries, and adds a downlink in the parent. A full parent may split too, and a root split increases the height. Concurrent structural updates need short-lived page latches and crash-safe publication. Increasing keys tend to concentrate inserts at the right edge, while random keys touch more leaves and can cause scattered page work. Which is better depends on the workload and engine. The key interview insight is the actual page and I/O work behind “logarithmic lookup.”
