Walk through what a B+tree index does when a new entry must be placed into a leaf page that is already full. What is a page split, and what does it cost?

## Setting the scene A B+tree index is a balanced tree of fixed-size pages. **Leaf pages** hold the actual index entries — key value plus a pointer to the row — in ascending key order, and are chained to their neighbours so the whole key range can be walked in order. **Internal pages** hold separator keys and child pointers, and exist only to route a search to the correct leaf. Every leaf sits at the same depth; that invariant is what makes lookup cost predictable. ## Why a split is needed at all Pages are a fixed size. An entry must go into the one leaf whose key range covers it — you cannot put it "somewhere else with room", because then range scans and searches would not find it. So when the correct leaf is full, the structure itself has to change. ## The split, step by step 1. **Locate.** Descend from the root using separator keys to find the target leaf. 2. **Detect the overflow.** The new entry does not fit in the remaining free space of that page. 3. **Allocate.** Take a fresh page from the index's free space or extend the file. 4. **Redistribute.** Choose a split point and move the entries above it into the new page. The textbook choice is the midpoint, giving two roughly half-full pages. 5. **Insert.** Place the new entry into whichever of the two pages its key now belongs to. 6. **Relink.** The leaf level is a linked chain in key order. The original page's next-pointer now points at the new page, and the new page points at what the original used to point at (and, in doubly linked implementations, backwards as well). Getting this right is what keeps ordered range scans correct. 7. **Post to the parent.** The parent must learn that a new child exists and which key range it covers, so a separator key and a child pointer are inserted into it. ## Cascading and tree growth Step 7 is an insert into a page, and that page may itself be full — in which case it splits by the same procedure and posts to *its* parent. In the worst case the split propagates all the way to the root. When the root splits, there is no parent to post to, so a **new root** is created containing one separator and two children. This is the only mechanism by which a B+tree grows taller, and because it happens at the top, every leaf gains a level simultaneously. That is why B+trees are always perfectly height-balanced without any rebalancing algorithm of the kind binary search trees need. Height grows very slowly: with a fanout of several hundred children per internal page, three or four levels index hundreds of millions to billions of rows. ## What a split actually costs - **Write amplification.** One logical insert becomes: the original page rewritten, a new page written, the parent modified — and each of those changes is written to the write-ahead log, shipped to replicas, and captured by backups. On engines that log full page images after a checkpoint, the multiplier is larger still. - **Concurrency.** The split must appear atomic to concurrent readers and writers, so it takes short-lived exclusive latches on the leaf, its new sibling and the parent. Under heavy concurrent insert traffic on the same region of the key space, that becomes a contention point. - **Density.** Two roughly half-full pages replace one full page. The freed space is genuinely reusable — but only for keys that fall in those pages' ranges. If the workload never inserts there again, that space stays unused. - **Ordering.** The new page is allocated wherever free space happens to be, which is usually not physically adjacent to its logical neighbour. Repeated splits therefore erode the correspondence between key order and physical layout. ## Splits are not a defect Splitting is the normal, correct growth mechanism of a B+tree; an index that has never split has never grown. The engineering question is not how to avoid splits but how to avoid *paying for them repeatedly* — which is a question about key ordering and about how much free space pages are built with, not about the split algorithm itself. ## Concurrency implementations, briefly Naively, a split appears to require holding locks all the way down the descent path in case the split cascades. Real implementations avoid that. A widely used family of techniques adds a right-link from each page to its right sibling plus a high key marking the page's upper bound: a reader that arrives at a page which has since split and no longer covers its search key simply follows the right-link to the sibling. That lets a split be performed as a sequence of locally-locked steps while concurrent readers proceed without blocking, and it is the reason B+trees scale to high concurrency at all. ## The signature to remember Half the entries move, a separator goes up, the chain is relinked, and the tree only ever grows at the root.