Code weight: vendored BTree trim and range-scan law

Reviewed executable revision: 067fbd94 (base ae2eb3fb, the fetched origin/main at review time). This record follows in a documentation-only commit. The reviewed revision changes packages/db/src/utils/btree.ts and packages/db/tests/btree-map-oracle.test.ts.

Change

BTreeIndex uses these B+ tree operations: get, set, delete, clear, minKey, maxKey, forRange, nextHigherPair, and nextLowerPair. The trim removes vendored sorted-btree features that nothing calls: editRange, early-break callbacks, callback counters, in-place value edits, the overwrite flag, and reused result arrays. It also removes the right-sibling shift in BNodeInternal.set, which cannot run (see "Unreachable shift" below). has() and the get() fallback stay because the Map oracle observes membership through them.

The change is intended to preserve behavior. It does not change the behavior of a comparator that returns NaN. That existing defect is tracked in #1945.

Full @tanstack/db entry, esbuild minified, db-ivm inlined:

Revision	min	gzip	brotli
ae2eb3fb	376,495	106,289	90,043
067fbd94	375,072	105,834	89,692
Δ	−1,423	−455	−351

Contract, path, and limits

The owner is packages/db/tests/btree-map-oracle.test.ts. Its contract: for numeric keys, the B+ tree is a Map whose traversal and neighbor operations use numeric key order. The model is an independent Map plus a sort. It does not use the tree's nodes, search, or traversal code.

Before this change, law 2 checked only a full scan with includeHigh: true. BTreeIndex.rangeQuery calls forRange(from, to, toInclusive, …) with arbitrary bounds and both toInclusive modes. This change extends law 2. After each checked cut, the refinement check scans five bound pairs, each with includeHigh true and false:

a window around the probe that starts and ends between keys;
the point range [probe, probe];
a reversed pair (low > high), which must be empty;
the second and second-to-last model keys, which exercise the inclusive and exclusive edges on existing keys;
the first model key as a point range.

Each scan must return exactly the model keys in [low, high], or in [low, high) when includeHigh is false, once each, in order, with the modeled payloads. The observation records every visited key. Duplicates, omissions, and order changes are therefore visible.

Limits:

Keys are integers from 0 to 199, and node sizes are 4 to 8. The oracle does not cover custom collation. The ordered-acquisition and index refinement owners cover that.
The oracle does not check balance, depth, or space. Node merging is not observable through the Map contract. See N4 below.
Comparators are consistent. Inconsistent comparators, including ones that return NaN, are outside this law (#1945).

Unreachable shift

BNodeInternal.set chooses i = min(indexOf(key, 0), children.length - 1). That is the first child whose max key is at least key. An internal node keeps keys[j] === children[j].maxKey(). The removed right-sibling shift required cmp(child.maxKey(), key) < 0. With a consistent comparator, that is true only when i was clamped to the last child, and the last child has no right sibling. Upstream sorted-btree@1.8.1 has the same selection line and the same unreachable branch. A non-transitive comparator can reach the branch. Without the branch, the insert splits the full child instead of shifting an entry. The tree stays valid, and Map observations are unchanged.

Grammar controls and calibration

The change adds observations to the existing refinement check. It adds no new generator. The existing histories reach the new checks at every cut in the fixed long campaign (every 97 steps and at the end), in every cut of the fast-check property, and in the dense growth, retirement, and reuse cases.

Reconstruction: each named wrong design below is reached by the existing histories and rejected at a range cut.
Range: empty trees use probe-derived bounds, because sorted[1] and sorted.at(-2) are undefined there. One-key trees make the edge pairs coincide.
Exclusion: the reversed pair checks that low > high yields no keys.

Source mutants on unchanged production (ae2eb3fb BTree)

Each mutant ran against the original oracle and the extended oracle. The source was restored after each run.

Mutant	Original oracle	Extended oracle
M1: public forRange passes includeHigh: true	survived (9/9 passed)	assertion failure (8 tests)
M2: leaf ignores includeHigh	survived	assertion failure (7 tests)
M3: leaf scan starts at the leaf's first key, ignoring low	survived	assertion failure (7 tests)
M4: a low === high leaf scan also includes the next key	assertion failure (8 tests)	assertion failure (8 tests)

Source mutants on the trimmed tree

These ran against the extended oracle plus btree-index-work.test.ts and btree-index-undefined-values.test.ts. They ran on the trimmed tree before the point-range shortcut was restored and before the right-sibling shift was removed. Neither later change touches the mutated lines.

Mutant	Outcome
N1: leaf delete splices keys but not values	assertion failure (1 test)
N2: leaf delete does not update the size	assertion failure (7 tests)
N3: leaf scan ignores includeHigh	assertion failure (8 tests)
N4: internal delete skips tryMerge	survived: equivalent within the Map domain
N5: internal delete keeps empty children	assertion failure (6 tests)
N6: no root collapse after delete	assertion failure (5 tests)

N4 changes balance, not the Map relation. It belongs to performance evidence, not to this law.

Executable controls

rejects a range scan that ignores includeHigh and rejects a range scan that ignores the low bound wrap the real forRange. Each wrapper keeps the full scan correct, so only the new range checks can reject it. The expected error must name a forRange(low, high, includeHigh) cut. As a sanity check, replacing the includeHigh wrapper with an honest pass-through made that control fail, because the refinement check no longer threw.

Performance

An A/B harness ran the base and trimmed trees on identical deterministic workloads: bulk insert, get, overwrite, delete, range scans in both includeHigh modes, full scans, neighbor walks, and churn. It used 1k, 20k, and 200k keys, 15 to 41 interleaved rounds, and median times. An A/A run of the base tree against a copy of itself measured a noise band of about ±2% to ±4.5%.

The first trim was 5% to 9% slower on delete and churn at 20k to 200k keys. The cause was the removed single-search path for point ranges. The trim now keeps that path in the leaf and internal forRange.
After that, raw point operations remained 3% to 5% slower in both slot orders, although their code is logically unchanged. Small range scans were faster.
At the BTreeIndex level (add, update churn, remove, eq lookup, rangeQuery, take/takeReversed, at 20k and 100k rows), every workload was within ±4%. The sign changed when the slots were swapped. No index-level regression was measurable.

The harness is not checked in.

ORC-001 through ORC-012

Requirement	Result
ORC-001	The oracle's opening comment states the Map contract, the four laws, and the extended law 2. This record states the limits above.
ORC-002	Expected range results come from filtering the sorted model keys. The model does not import tree search or traversal.
ORC-003	The contract, model (stepModel), histories, production driver (stepTree and the public BTree API), and refinement check (expectRefinement, expectRange) are visible in the oracle file.
ORC-004	No generator changes. Reconstruction, range, and exclusion for the new observations appear above. Ablation: each bound pair targets a distinct edge, and M1 to M3 show that the partial and edge pairs are necessary.
ORC-005	Every check calls the public BTree methods that BTreeIndex calls, and compares exact ordered keys and payloads at each cut.
ORC-006	Source mutants and executable controls, with outcome classes, appear above.
ORC-007	Existing gap, not changed here. The fixed LCG campaign and the fast-check property are different properties, so they do not form the fixed-and-random parity pair. The fast-check lane has no documented seed and path replay interface. This change only adds checks to the shared refinement check.
ORC-008	The model state does not change.
ORC-009	Model terms (put, delete, read, clear, range) map directly to BTree methods.
ORC-010	The fixed campaign wraps failures with the law name, seed, round, node size, and history, and keeps the original cause. Range failures name the failing bounds. No external resources are acquired.
ORC-011	No shared semantic fault calls for a second formulation. The Map model is already structurally independent.
ORC-012	This record ties the reviewed revision, outcome classes, controls, limits, and performance evidence to the coverage map.

Verification

On 067fbd94, the following passed:

packages/db Vitest, typecheck off: 191 files, 6,821 tests.
pnpm test:oracles: 48 files, 2,831 tests.
pnpm test:minified-db: 98 error names, index metadata, query rows, and live updates.
packages/db-sqlite-persistence-core: 340 passed, 1 todo.
tsc --noEmit -p packages/db: no errors in src or in the changed test. The existing tests/conformance errors also occur on ae2eb3fb.

The environment was Node v24.19.0 and Vitest 3.2.4 on Darwin arm64.