Struct BTree 

pub struct BTree { /* private fields */ }

A copy-on-write B+tree set of OwnedRows, ordered by a Sort comparator passed per call (no stored closure — foundations §11.6). Replaces BTreeSet<Row> (btree-set.ts:7) with Rc<BNode> + Rc::make_mut. The comparator lives with the enclosing Index in the real source; the spike threads &Sort.

Preconditions (schema invariants the builder/source guarantee; a violation is a programming error and panics, mirroring the JS oracle’s compareValues throw — data.ts):

• every Row is at least as wide as max(ColId in sort/bound) + 1 (so column indexing never goes out of bounds);
• within any one sort column, all rows carry the same Value variant (so compare_values never hits a cross-type pair — risk-register R10; the builder coerces literals to the column type at build time).

Implementations

impl BTree

pub fn new() -> BTree

Empty tree. O(1).

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn fork(&self) -> BTree

The headline: O(1) structural clone — one Arc bump + a usize copy. JS clone() (btree-set.ts:28-34) sets root.isShared = true and shares the root; Rust just clones the Arc. fork() and #getOrCreateIndex’s data.clone() both become this. NO flag mutation, NO node allocation. (Not impl Clone so the O(1)-ness is named at every call site.)

pub fn has(&self, key: &OwnedRow, sort: &Sort) -> bool

has (btree-set.ts:56-58). O(log n), read-only — never calls make_mut, never bumps a refcount (descends by reference).

pub fn get(&self, key: &OwnedRow, sort: &Sort) -> Option<&OwnedRow>

get (btree-set.ts:36-38): the stored row equal to key under the comparator (rows may carry payload beyond the sort columns), borrowed out of the tree. O(log n), read-only, zero allocation/refcount traffic — the caller Arc::clones only if it needs to own (one bump, OQ-2).

pub fn add(&mut self, key: OwnedRow, sort: &Sort) -> bool

add (btree-set.ts:40-47). Inserts key; returns true iff newly inserted (false overwrites the equal slot, like the JS). Path-copying COW: make_mut the root, then each child as the insert descends — only the root→leaf path is copied, and only nodes that are actually shared.

pub fn add_replacing(&mut self, key: OwnedRow, sort: &Sort) -> Option<OwnedRow>

add, returning the row it displaced (None iff newly inserted). Same cost — the overwrite is a mem::replace either way; add is this with the payload dropped. Exists for callers that track the bytes their tree holds (BatchDelta’s byte budget, design 306 D4): rows are variable-length Arc<[u8]>, so “did it overwrite” is not enough to stay net — the accounting needs the outgoing row’s size.

pub fn delete(&mut self, key: &OwnedRow, sort: &Sort) -> bool

delete (btree-set.ts:66-89). Removes key; returns true iff present. Path-copying COW (same make_mut descent as add) + the JS opportunistic rebalancing: after removing from a child, an emptied child is dropped and an underfull child (<= MAX/2) is tryMerged with its right neighbour when the combined size fits (btree-set.ts:639-721). Each merged-into sibling is make_mut’d before mutation (the isShared→Arc substitution, §4.4.5). Then the root-collapse loop runs. This matches the JS BTreeSet occupancy behaviour exactly (it too tolerates underfull nodes that can’t merge — it is not a strict B-tree).

pub fn from_sorted(iter: impl Iterator<Item = OwnedRow>, sort: &Sort) -> BTree

fromSorted (btree-set.ts:140-188): O(N) bottom-up bulk load from a PRE-SORTED iterator (caller guarantees order under sort). Build leaves of MAX_NODE_SIZE, then internal levels bottom-up until one root. NO per-key descent — this is the O(N)-vs-O(N log n) win the lazy index build needs (04 §5.4).

pub fn check_invariants(&self, sort: &Sort) -> Result<(), String>

Validate structural invariants — a test/debug helper (cheap to keep pub; it walks the whole tree, so call it in tests/property checks, not the hot path). Returns Err(reason) on the first violation. Checks: balanced (every leaf at the same depth), per-node strict sortedness, the cached-max invariant (keys[i] == children[i].max_key()), keys.len() == children.len() for internal nodes, node occupancy <= MAX_NODE_SIZE, no empty non-root node, and size equals the actual key count.

pub fn values_from( &self, bound: Option<&RowBound>, inclusive: bool, sort: &Sort, ) -> BTreeCursor

Forward ordered iteration from an optional lower bound (valuesFrom, btree-set.ts:99-101). bound = None ⇒ from the start. inclusive selects >= bound (true) vs > bound (false). Returns the LENDING BTreeCursor — zero per-row alloc to vend.

pub fn values_from_reversed( &self, bound: Option<&RowBound>, inclusive: bool, sort: &Sort, ) -> BTreeCursor

Reverse ordered (descending) iteration from an optional upper bound (valuesFromReversed, btree-set.ts:113-124). bound = None ⇒ from the maximum. inclusive selects <= bound (true) vs < bound (false). The first row yielded is the largest qualifying row; iteration then descends.

impl BTree

pub fn diff_visit( &self, other: &BTree, sort: &Sort, use_identity: bool, stats: &mut DiffStats, sink: &mut dyn DiffSink, )

Visit the row-level differences that turn self into other, in descending sort order. Both trees MUST be ordered by sort (the diff is meaningless otherwise).

use_identity enables the ptr_eq short-circuits; production callers pass true (see BTree::structural_diff). Passing false forces the full value walk — used by the differential test to prove the skips are a pure optimization (design §2.2.1). stats accumulates the work counters (§2.2.2); pass &mut DiffStats::default() if you don’t care.

pub fn structural_diff(&self, other: &BTree, sort: &Sort) -> Vec<SourceChange>

The optimistic-writes “rewind” primitive: the SourceChanges that turn self into other (apply them to a source holding self and it becomes other). only_this → Remove, only_other → Add, edit → Edit. Both trees must be ordered by sort. Identity short-circuits are on.

Trait Implementations

impl Default for BTree

fn default() -> Self

Returns the “default value” for a type.