bisect_right is the correct choice here and how it interacts with the split strategy (separator = first key of right sibling)Date: 2026-05-29
Time: 10:37
Now I have the full picture from the search and insert entries. Here's the explanation:
b-tree-storage-engine/btree.py:insert — See the leaf vs. internal split logic side-by-side; leaf splits copy the key up while internal splits promote it out, and this asymmetry is why bisectright works uniformly for internal routingb-tree-storage-engine/btree.py:findleaf — Range scan traversal that also uses bisect_right on internal nodes; confirms the invariant holds across all read paths, not just point lookupsb-tree-storage-engine/btree.py:delete — Deletion must also route through internals with bisectright; worth checking whether separator keys in the parent are updated when the first key of a right child is deletedleaf-copy-vs-internal-promote — The dual split strategy (copy-up for leaves, promote-out for internals) is a standard B+-tree design; understanding why they differ clarifies the entire routing modelb-tree-storage-engine/btree.py:rangescan — Uses the leaf sibling chain (nextsib) that splits maintain; the correctness of this chain depends on the same split conventions that drive the bisect_right choicebtree-bisect-right-matches-copy-up-split — Internal nodes use bisectright because leaf splits copy the separator into the right child as its first key; bisectright routes equal keys to the right child where the data livesbtree-bisect-left-for-leaf-exact-match — Leaf lookups use bisectleft to find the leftmost insertion point, then check keys[idx] == key for exact match; bisectright would overshootbtree-split-asymmetry-leaf-vs-internal — Leaf splits copy the midpoint key (it appears in both parent and right child), while internal splits promote it (it appears only in the parent); this asymmetry is why a single bisect_right rule works for all internal routingbtree-bisect-left-internal-would-misroute — Using bisectleft instead of bisectright at internal nodes would route separator-equal keys to the left child, producing false negatives on lookup and duplicate insertions in the wrong leaf