Database B-Tree Page Splits and Separator Keys
A B-tree page split divides a full index page into two pages and adds a separator key to their parent so searches can still find the right branch. It is the B-tree’s way to grow while keeping its pages bounded and its lookup path short.
The problem a split solves
A database index is usually stored in fixed-size blocks called pages. A page might hold many sorted index entries, but not infinitely many. An entry commonly contains an indexed key and a pointer to the matching table row, or to another index page.
Without page splits, inserting a key into a full page would require one of three bad choices:
- Reject the insert.
- Put an overflow page somewhere, making the search structure irregular.
- Rebuild or move a large part of the index.
A B-tree instead keeps pages within their capacity by dividing a full page. The resulting tree remains balanced: all searches still travel through roughly the same number of levels, and the number of pages examined grows logarithmically with the number of entries.
Many database indexes are specifically B+ trees, a common B-tree variant. In a B+ tree, complete row pointers normally live in leaf pages, while internal pages contain keys used for routing. The split process below describes that usual arrangement; exact details vary between database engines.
Finding the page to split
Suppose an index contains these sorted keys in one leaf page:
[10, 20, 30, 40, 50, 60]
An insert for 35 first follows the tree from its root to this leaf, then places 35 in sorted order. If the page has room, the operation is ordinary:
[10, 20, 30, 35, 40, 50, 60]
If the page is full, the database allocates another page and divides the entries, often aiming for roughly equal space on each side. With the new key included, the result might be:
left page: [10, 20, 30, 35]
right page: [40, 50, 60]
The exact split point is an implementation choice. Records have different sizes, and databases may leave extra free space on one or both pages to reduce immediate future splits. The important property is that every entry remains in one of the two sorted pages.
The new right page must also be connected to the tree. The parent needs a separator key: a key that tells a search which child page to choose. For the example, the parent might receive 40, with a routing rule such as:
- keys less than
40go to the left page; - keys greater than or equal to
40go to the right page.
A separator is not necessarily a second copy of a row’s data. It is routing information. In a leaf split, many B+ tree implementations copy the first key of the right page into the parent while retaining that key in the right leaf. This lets the parent describe the boundary without removing the searchable entry from the leaf.
Propagating the split upward
Adding a separator and a child pointer can itself fill the parent. If the parent has room, the operation ends there:
parent: [10, 40, 80]
| | |
left new ...
If the parent is full, it is split too. Its separator keys and child pointers are divided between two internal pages. One boundary key is then promoted to the parent above them. “Promoted” means that the key is removed from the pair of internal pages and inserted into their parent as the boundary between those pages.
This distinction matters:
- A leaf split usually leaves the boundary key in a leaf and copies it upward as routing information.
- An internal-page split usually promotes a boundary key upward, so it becomes a separator at the next level rather than remaining as an ordinary entry in either resulting internal page.
The process can repeat through several levels. An insertion may therefore split a leaf, then its parent, then its parent’s parent. Most inserts do not do this; they touch a full page only when the relevant level has no available space.
The special case: splitting the root
The root has no parent to receive a separator. If it fills and splits, the database creates a new root containing a separator and pointers to the two resulting pages:
new root: [40]
/ \
[10,20,30] [40,50,60]
The tree gains one level, but it remains balanced because the two new children are at the same depth. This is the only normal operation that increases the tree’s height. Since a root split is relatively rare, the height stays small even for a very large index.
Why lookups stay fast
A search uses the separators at each internal page to choose exactly one child. At a leaf, it scans or searches the sorted entries for the requested key. Splitting changes the boundaries and adds a page, but it does not make the search inspect every page:
- Compare the target with the root’s separators.
- Follow the matching child pointer.
- Repeat until reaching a leaf.
- Search that leaf for the key.
Because pages hold many entries, a tree with millions of indexed rows usually has only a few levels. Splits preserve that high branching factor instead of allowing pages to overflow or forcing a broad reorganization. They also preserve key order, which supports range scans: after finding the first matching leaf, the database can visit neighboring leaf pages in order.
A split is not free. It allocates a page, writes two pages instead of one, updates the parent, and may cause several more writes if the split propagates. It can also leave pages less full or scatter related pages on storage. Consequently, database logs and performance reports may mention page splits, index fill settings, or split-related write amplification. Those messages describe the maintenance cost of keeping the lookup structure valid—not a change from logarithmic lookup to a linear scan.
The central idea is simple: when a page fills, divide its sorted contents, publish the boundary between the new pages to the parent, and repeat upward only as necessary. The separators keep navigation precise; the balanced shape keeps the number of pages visited small.