Separator Keys and Search Routing in Internal Nodes

A B+-tree’s internal pages contain keys that appear nowhere else: they are not copies of row data, they are not the maximum key of the child they precede, and in many formats they are not even complete keys. They exist to answer one question at each level, which child contains the key being sought, and any value that answers that question correctly is admissible. Understanding how implementations choose those values explains several behaviours that otherwise look arbitrary, including why an index can report an entry for a key that does not exist and why descending a tree with many duplicate keys does not degenerate.

The routing predicate, stated precisely

An internal page with $n$ entries and $n+1$ children stores $n$ separators $s_1 < s_2 < \dots < s_n$. The routing rule in a B+-tree is uniform: the search key $k$ goes to the child whose subtree is delimited by the separators around it. Written as an index computation, with children numbered $c_0 \dots c_n$:

$$c_i \text{ where } i = |{ j : s_j \le k }|$$

That is, the child index is the number of separators less than or equal to the key. Child $c_0$ holds keys below $s_1$, child $c_i$ holds keys in $[s_i, s_{i+1})$, and the rightmost child holds everything at or above $s_n$. The convention that the separator belongs to the right child is what makes this rule total: every key falls in exactly one interval, including keys equal to a separator.

The alternative convention, where the separator belongs to the left child and the predicate uses a strict inequality, is equally correct and is what a classic B-tree of the original 1972 formulation does. What is not correct is mixing the two. A page format that stores a separator and routes with < in one code path and <= in another will misroute keys equal to a separator, and the resulting bug appears only for keys that happen to land exactly on a page boundary, so it survives any test whose data does not happen to produce such a key.

/* Child index is the count of separators <= key, using the page's own
 * comparison so that collation and encoding are honoured. */
static int child_for(const page *p, const key *k)
{
    int lo = 0, hi = p->nkeys;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (page_compare(p, mid, k) <= 0)
            lo = mid + 1;      /* separator <= key: go right */
        else
            hi = mid;
    }
    return lo;                 /* 0..nkeys, one past the last separator */
}

The loop returns a child index in $[0, n]$, and the two boundary cases fall out without a special path: a key below every separator yields 0, and a key at or above the last separator yields $n$. The only place this goes wrong is when page_compare is a byte comparison and the index’s collation is not, which is the next problem.

Separators need not be keys

The separators of an internal page need only satisfy the invariant that everything in the left subtree compares below everything in the right. The minimum key of the right child satisfies it, and so does the maximum key of the left child, and so does anything in between. This slack is what permits suffix truncation: when a leaf splits, the separator can be shortened to the shortest prefix that still separates the two halves.

Take a leaf holding keys invoice-2024-000981 and invoice-2024-001004 at the split point. The separator must satisfy invoice-2024-000981 < s <= invoice-2024-001004. The two keys share their first fifteen bytes and diverge at the sixteenth, where 9 meets 1, so a separator of sixteen bytes — the shared prefix plus 1 — is admissible, and it is three bytes shorter than the right key rather than nineteen. The saving is the length of the right key’s tail past the divergence point, so it is largest for long keys that differ near their beginning and smallest for keys that differ only at the end. Where the saving is large, it compounds across every level, raising the fanout of the internal pages described earlier.

Truncation has a cost in diagnostics: an index scan that reports “key not found” may name a separator that no row contains. Tools that display the separator of a page therefore show something that looks like corrupt data to anyone expecting row values, and the fix is to understand that the internal page is a routing table, not a copy of the data.

Some formats go further and store no key at all in the first entry of a page, treating the first child as “everything below the first stored separator”. That is a space optimization worth one entry per page and it complicates the boundary case: the leftmost child of the root has no lower bound, so a search for a key below every key in the index still descends through it correctly, but a reverse scan needs the symmetric rightmost handling.

Comparison is not byte comparison

The routing predicate is defined in terms of the index’s sort order, and that order is not necessarily the byte order of the stored values. A collation may be case-insensitive, accent-insensitive, or locale-dependent, and a numeric type may be stored in a byte-comparable encoding that differs from the arithmetic order of its printed form.

Two consequences follow. First, the comparison used to route must be the same comparison used to sort the leaves; an index built with one collation and queried with a predicate routed by another will produce wrong results with no error. Second, the separator range that truncation may exploit is a range in the collation’s order, so a byte-level truncation is only safe if the encoding is order-preserving.

The standard technique for making types order-preserving is an encoding in which the byte comparison of the encoded form equals the logical comparison of the value. Integers do this by flipping the sign bit for signed types and using big-endian byte order, so that a shorter encoded integer compares below a longer one only when it genuinely is smaller. Floating point needs a sign-aware transformation of the exponent and mantissa, and strings need the terminator or length prefix handled so that a prefix does not compare above its extensions. Without such an encoding, a composite key containing an integer column cannot be compared bytewise, and the index either decodes on every comparison or refuses the optimization.

This is the reason a change of collation on an indexed column requires a rebuild, and the reason the collation of a column is part of the index definition rather than a query-time property.

Duplicate keys and the tie-breaker

A non-unique secondary index has many entries with the same key, and the routing predicate as stated sends all of them to one child. That is fine for a lookup but breaks the leaf chain’s ordering guarantee if duplicates are allowed to spread across leaves in arbitrary order, because a range scan that follows the chain would then see the duplicates in whatever order they were inserted, and deletion would need to search multiple leaves for one key.

The standard resolution is to append a unique tie-breaker to every index key. For a secondary index on a non-unique column, the tie-breaker is the primary key or the row identifier, and the stored index key becomes the pair (column value, row id). Now every entry in the index is unique, the leaf chain is totally ordered, and a lookup for a duplicated value finds all its entries in one contiguous run that can be scanned and then filtered.

The cost is space: the row identifier is stored once per index entry. In a narrow index on a small integer column, the tie-breaker can dominate the entry size, and that reduces the fanout of both leaves and internal pages. This is the concrete reason covering indexes that avoid touching the table are attractive for wide tables: the cost of the tie-breaker is paid either way, and paying it for fewer index entries is cheaper than paying it for a table lookup per row.

InnoDB makes the choice explicit in the opposite direction: every secondary index entry carries the clustered primary key as its tie-breaker, which is why a long primary key inflates every secondary index in the table. The clustered and secondary access paths differ in more than which pages they read; they differ in what the key itself contains.

Descending, negation, and the sentinel problem

A scan in descending order cannot simply walk the leaf chain backwards, because the chain is forward-only in most formats. The usual implementation descends to the highest key satisfying the predicate and then walks backward within each leaf page, using the page’s slot directory to iterate entries in reverse, and moves to the previous page via a backward link or by re-descending from the parent when the format stores only a forward link. Formats that store both links pay two pointers per leaf for the convenience; formats that store one pay an extra descent per page boundary crossed.

A predicate such as NOT (x < 10) or a negation of a range does not have a single contiguous interval in the index, and the optimizer cannot generally turn it into one range scan. It either scans the whole index and filters, or splits the predicate into the complement intervals, which for a simple negated range is two intervals and for a negated IN list is many. The number of intervals is a planning cost, not an execution one, and the executor’s ability to scan multiple ranges in one pass determines whether the plan is usable.

Finally, the sentinel keys. A B-tree that must handle unbounded key spaces needs a value below all keys and one above all keys, or explicit null handling at the extremes, so that the leftmost and rightmost children have well-defined bounds. Formats that use a fixed-size all-zero and all-ones sentinel must ensure no real key encodes to those values, and a nullable column whose encoding maps null to all-zero bytes violates that. This is a narrow case that produces a wrong answer rather than a crash, and it is why nullable indexed columns are commonly given a distinct encoding rather than sharing the value space with real data.