B and B+ trees: capacity, updates and range search
Goals and conventions first
Calculate node capacity from bytes, distinguish B trees from B+ trees, reason about height and occupancy, and trace splits, borrowing and merging. “Order” is not standardized: it may mean maximum children, minimum degree or maximum keys in different questions. This lesson defines m as the maximum number of children in an internal node, and L as the maximum number of data entries in a B+ leaf. Read the question's convention before using a formula. The examples assume unique search keys unless stated otherwise.
1. B tree versus B+ tree
Both are balanced multiway search trees: every leaf has the same depth. In a B tree, searchable data entries or record references may be stored in internal nodes as well as leaves. A successful search can therefore stop in an internal node. In a B+ tree, internal keys guide navigation; all data entries or record references are in leaves. Internal separators can repeat leaf key values. Leaves are commonly linked for ordered scanning, so a range search descends once and then follows leaf links.
For a B+ internal node with children P0,...,Pk and sorted separators K1,...,Kk, use the convention that Ki is the smallest key in child Pi's subtree. The first child holds values below K1; middle children hold ranges [Ki,K(i+1)); the last holds values at least Kk. Equality follows the right side of a separator under this convention. Other separator conventions are valid, but mixing them inside a trace is not.
For maximum internal children m, a nonroot internal node has between ceil(m/2) and m children, hence between ceil(m/2)−1 and m−1 separators under our occupancy convention. A nonleaf root has at least two children and at most m. The root can instead be the single leaf, with fewer than the usual minimum entries. B+ leaves have between ceil(L/2) and L entries except that root-leaf exception. Internal and leaf capacities need not be equal.
2. Derive capacities from byte budgets
Suppose a page has B bytes, an internal header consumes H bytes, child pointers use P bytes and separator keys use K bytes. An internal node with p children has p−1 keys, so pP+(p−1)K+H≤B. Thus maximum fanout is floor((B−H+K)/(P+K)). Do not count p keys with p pointers: the one-extra-child structure matters.
For leaves, suppose each entry stores a key of K bytes plus a record identifier of R bytes, the leaf header is H_l and one next-leaf pointer uses P bytes. Then L=floor((B−H_l−P)/(K+R)). If the question gives two sibling pointers, extra metadata, variable keys or full records in leaves, adjust the budget. These formulas assume no compression, no additional hidden overhead and fixed sizes.
Worked page budget: B=512, H=16, K=8, P=8. Internal p satisfies 8p+8(p−1)+16≤512, or 16p+8≤512; hence m=31. For a leaf with H_l=16, one 8-byte sibling pointer and R=8, L=floor((512−16−8)/16)=30. A 31st entry would need 520 bytes, so it does not fit. The minimum nonroot internal fanout is ceil(31/2)=16; minimum nonroot leaf occupancy is ceil(30/2)=15 entries.
3. Height and I/O assumptions
Define height h as the number of edges from root to a leaf. A root-leaf tree has h=0 and one node level. With every node page uncached, an equality lookup visits h+1 index pages; fetching a separate heap record adds a data-page I/O. If the root is cached, subtract that physical root I/O. A covering index can avoid the separate data fetch for a query whose required values are already in the index.
For h≥1, let d=ceil(m/2) and ell=ceil(L/2). A minimally occupied B+ tree of height h has at least 2d^(h−1) leaves and at least 2d^(h−1)ell entries. A completely full tree has at most m^h leaves and m^hL entries. The root's minimum two children is a special case; using d for the root would overstate the minimum.
Worked capacity with m=4,L=3: d=2,ell=2. Height 1 can hold at most 43=12 entries. Height 2 can hold at most 4²3=48 and at least 222=8 entries. Thus 40 entries require at least height 2, but entry count alone does not uniquely determine actual height: a sparsely occupied taller tree may also fit 40. Use an explicit fullness assumption for exact height or page-count claims.
Range I/O: if height h=2 and a range spans four consecutive leaf pages, the uncached index cost is (h+1)+(4−1)=6 page reads. The first leaf was already counted in the descent. Separate data fetches depend on clustering, caching and how many distinct table pages hold the qualifying records; four leaf pages do not necessarily mean four table pages.
4. B+ insertion: copy at a leaf, promote internally
Search the target leaf, insert in key order, and stop if it fits. On overflow, split the leaf into valid-occupancy leaves, repair sibling links and copy the smallest key of the new right leaf into the parent. That data key remains in the leaf. If the parent overflows, split its child-pointer sequence and promote a separator to the next level. The promoted internal separator is removed from that internal level, while the underlying data entry remains somewhere in the leaves. A root split creates a new root and raises height by one.
Worked trace with m=4,L=3, no preemptive splits: insert 10,20,30 into the root leaf. Inserting 40 overflows it; split as [10,20] and [30,40], creating root separator [30]. Insert 50 into the right leaf, obtaining [30,40,50]. Insert 60: split that leaf into [30,40] and [50,60], and copy 50 to the root, now [30,50]. Leaves are [10,20]→[30,40]→[50,60]. All leaves remain at the same depth.
Continue with 70,80,90,100. Splitting on 80 makes the root [30,50,70]. Splitting on 100 gives five child leaves [10,20],[30,40],[50,60],[70,80],[90,100] and temporary separators [30,50,70,90]. Five children exceed m=4. Split the internal node into two-child left and three-child right nodes, promoting 50. The new root is [50]; its left internal node has [30], its right internal node has [70,90]. All data entries, including 50, remain in leaves. Other valid split distributions are possible when conventions allow them; the trace specifies this one.
5. Deletion: redistribute, merge, and adjust separators
Remove the entry from its leaf. If minimum occupancy still holds, repair any separator whose represented minimum changed. On underflow, a sibling with more than its minimum can lend an entry; update the parent separator after redistribution. Otherwise merge with a compatible sibling, remove the redundant child pointer/separator from the parent, and repair the leaf links. A parent underflow may propagate upward. If a nonleaf root is left with one child, replace it by that child, reducing height by one. Deletion never requires unbalancing leaf depths.
Borrow example with m=4,L=3: root [30], leaves [10,20] and [30,40,50]. Delete 10, leaving [20], below the leaf minimum 2. Borrow 30 from the right sibling: leaves become [20,30] and [40,50], and root becomes [40]. Forgetting the separator update can route future searches incorrectly.
Merge example: root [30], leaves [10,20] and [30,40]. Delete 10; the right sibling is at minimum and cannot lend. Merge [20] and [30,40] into [20,30,40]. The old root loses its separator and only one child remains, so that leaf becomes the root. Height drops from 1 to 0. A B tree deletion has additional cases because the target data key may be internal; replacement by predecessor/successor and node rebalancing must preserve its own occupancy rules.
6. A small B-tree update trace
For comparison, take a B tree with minimum degree t=2: nonroot nodes have 1–3 keys and internal nodes have 2–4 children. Using top-down insertion, a full root [10,20,30] is split before inserting 40. Promote the median 20, giving root [20] and children [10],[30]; insert 40 in the right child to obtain [30,40]. Unlike the B+ leaf split, the data entry 20 now resides only in the internal root, not duplicated in a leaf.
To delete internal key 20 in that tree, its right child has at least t keys, so replace 20 with its successor 30 and remove 30 from the right child. The result is root [30] with leaves [10] and [40]. If deleting the root key 30 now, both children have the minimum t−1 keys: merge [10], separator/data key 30, and [40] into [10,30,40], then remove 30. The root contracts to leaf [10,40]. General B-tree deletion prepares a child with enough keys before descending, borrowing through the parent or merging as needed. Do not reuse a B+ leaf merge rule that omits the parent data key.
Pitfalls
- A B+ tree's internal match is a routing separator, not the final data entry.
- Key count and pointer count differ by one in internal nodes.
- Root exceptions, leaf capacity and internal capacity must be explicit.
- Leaf split copies its separator upward; internal split promotes/removes its separator at that level.
- Height measured in edges differs by one from number of node levels.
- Big-O logarithmic lookup does not replace a question's cache and data-fetch assumptions.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. An internal B+ node has p children. How many separators does it have under the stated convention?
A. p−1 B. p C. p+1 D. 2p
Answer: A
A: The separators divide p child ranges.
B: This overcounts by one.
C: This overcounts by two.
D: There is no two-keys-per-child rule.
P02. B=512,H=16,K=P=8 for an internal node. Maximum children?
A. 30 B. 31 C. 32 D. 63
Answer: B
A: 30 fits, but 31 also fits.
B: 16p+8≤512 gives p≤31.5, hence 31.
C: 32 needs 520 bytes.
D: This ignores key storage.
P03. A B+ tree has height 2 edges; an uncached range scan touches 4 leaves. Index-page reads, excluding table data?
A. 4 B. 5 C. 6 D. 7
Answer: C
A: This omits internal descent pages.
B: There are two internal pages plus four leaves.
C: Three-page descent plus three additional leaves equals six.
D: This counts the first leaf twice.
P04. On a B+ leaf split, the new right leaf minimum is:
A. Deleted from all leaves B. Copied into the parent while remaining in the leaf C. Always promoted out of the leaf D. Used to make leaves have unequal depths
Answer: B
A: The data entry must remain searchable in leaves.
B: Leaf split duplicates a routing value upward.
C: Internal promotion and leaf copying differ.
D: Balance preserves equal leaf depth.
P05. m=4,L=3. Root [30], leaves [10,20] and [30,40]. Delete 10 using minimum occupancy 2. Correct result?
A. Borrow 30 and leave the right leaf [40] B. Merge into root leaf [20,30,40] C. Keep underfull leaf [20] permanently D. Create a new root above the old root
Answer: B
A: The right sibling would become underfull.
B: The sibling cannot lend, so merge and contract the root.
C: The nonroot leaf violates minimum occupancy.
D: Deletion here reduces rather than increases height.
P06. Which distinction is correct?
A. B+ stores all data entries in leaves; B trees may store them internally B. B trees are always binary C. B+ internal matches always finish data lookup D. B+ leaves may have arbitrary depths
Answer: A
A: This is the stated structural distinction.
B: B trees are multiway trees.
C: Internal B+ keys guide the search to leaves.
D: All leaves have equal depth.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Databases syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in