03 — Indexing

Code: src/Typhon.Engine/Indexing/

Indexing in Typhon is one mechanism: a B+Tree specialised at compile time for the key width. There is no separate "primary key index", "secondary index" or "uniqueness constraint" implementation — the same BTree<TKey, TStore> powers all three. The variants (L16BTree, L32BTree, L64BTree, String64BTree) exist purely to size the node layout to the key width so that every numeric node is exactly 256 bytes (String64BTree is the exception at 356 bytes — see §2), keying capacity off the key size rather than off some configured fan-out.

The tree is concurrent by design: readers descend lock-free via Optimistic Lock Coupling (OlcLatch), writers use a two-phase spin-then-yield lock that never pays the Windows 15 ms timer-tick penalty, and obsolete nodes are reclaimed via epoch deferral (01-foundation §4). It's also a B-link tree — every node carries a HighKey upper bound and a NextChunk pointer so a writer can split a node without coordinating with traversing readers; the readers follow the right-link to find the key that's now on the new sibling.

If you've used the engine before, you've used this code path. Every PK lookup, every secondary-index probe, every range scan in the query planner goes through it.

1. Overview — one tree, many uses

BTree<TKey, TStore> is the universal index. The same class instance backs:

Primary key indexes on ComponentTable (one per component type).
Secondary indexes declared by [Indexed] on schema fields.
Uniqueness constraints ([Unique] is a unique secondary index — AllowMultiple = false).
Multi-value indexes (AllowMultiple = true) — values per key are stored in a VariableSizedBufferSegment whose buffer head ID lives in the BTree's value slot.

The TStore generic threads through to IPageStore — concretely PersistentStore (WAL-backed, durable) or TransientStore (in-memory only, no WAL). The BTree code is identical for both; the store dictates whether mutations get journalled.

The user-facing handle is IndexRef — opaque, reusable, with a captured IndexLayoutVersion for O(1) staleness detection after schema evolution. Resolve once via DatabaseEngine.GetPKIndexRef<T>() / GetIndexRef<T, TKey>(), then reuse on the hot path.

2. Node layout — 256 B = 4 cache lines (numeric variants)

Every node is one segment chunk, and the segment's stride is exactly the node struct size. Nodes are 256 bytes for all numeric-keyed variants (filling four cache lines), asserted at Initialize time in each of L16BTree.cs, L32BTree.cs and L64BTree.cs.

String64BTree is the exception: IndexString64Chunk is 356 bytes — 4×5 header ints + a 64 B HighKey + 4×4 values + 4×64 keys. It carries no size assertion, only segment.Stride == sizeof(IndexString64Chunk), so the stride follows the struct. The struct's own "we want to keep this struct 64 bytes" comment is a stale design aspiration: a 64-byte node cannot hold even one 64-byte key, and the B-link HighKey added in #297 put the question beyond doubt.

The 256 B size isn't arbitrary: modern CPUs (Zen 4+, recent Intel) have an Adjacent Line Prefetcher that pulls the paired 64 B cache line within a 128 B region. Two ALP triggers therefore cover the full node — a node descent fetches one entry's data with at most two cache-line latencies, not four.

Every node carries the same header fields at the same offsets (so a generic BaseNodeStorage can address them uniformly):

Field	Type	Purpose
`Control`	int (4 B)	Packed: `StateFlags` (lo 16 b) ∣ `ContentionHint` (b16-23) ∣ `Start` (b24-31, ring-buffer head) ∣ `Count` (b32-39) — wait, `Count` is byte 3 of the int. The packing is byte-3=Count, byte-2=Start, byte-1=ContentionHint, low 16 b = StateFlags.
`OlcVersion`	int (4 B)	OLC latch state — bit 0 locked, bit 1 obsolete, bits 2-31 monotonic version counter
`PrevChunk`	int (4 B)	Left sibling at leaf level (doubly-linked leaf chain)
`NextChunk`	int (4 B)	Right sibling — the B-link
`LeftValue`	int (4 B)	Leftmost child pointer (internal nodes); reused as buffer head field at leaves of multi-value trees
`HighKey`	TKey-shaped	B-link upper bound — exclusive separator. `node.HighKey <= node.GetNext().GetFirst().Key` is the invariant (one-sided: a HighKey left below the right sibling's first key is normal after a removal and is tolerated; only a HighKey that exceeds the next leaf's first key is a violation).
`Keys[Capacity]`	TKey × N	Key array, contiguous
`Values[Capacity]`	int × N	Value array — child chunk IDs (internal) or record IDs / buffer heads (leaves)

Start and Count together describe a rotated ring buffer within the key/value arrays: PushFirst/PushLast/Spill-Left/Spill-Right amortize key shuffling by rotating the head rather than memmoving the whole array. IsRotated is true iff Start + Count > Capacity. The Adjust(i) helper folds an index back into [0, Capacity).

`BTree<TKey, TStore> : BTreeBase<TStore>`

BTree.cs, BTreeBase.cs

BTreeBase<TStore> is the non-generic surface used by ComponentTable, the query planner, and IndexedFieldInfo — it doesn't know TKey. BTree<TKey, TStore> is the typed implementation; concrete instantiations (e.g. IntSingleBTree<TStore>, LongMultipleBTree<TStore>) bind both type parameters and pick a node-storage strategy.

Key invariants and constants:

Constant	Value	Meaning
`MaxTreeDepth`	32	Maximum descent depth — bounds stack-allocated path buffers
`MaxOptimisticRestarts`	3	OLC reader restart budget before falling back to pessimistic
`ContentionSplitThreshold`	3	`ContentionHint` value at which a hot leaf gets proactively split
`DirectoryChunkCount`	4	Reserved chunks at the start of the segment for the BTree directory
`MaxDirectoryEntriesFor(stride)`	84 at stride 256	Hard cap on B+Trees per shared segment. Stride-dependent, not a constant — see §7

3. Variants & per-node capacities

Each numeric variant is a 256 B struct sized so the key/value arrays plus the fixed 28 B of metadata + HighKey fit exactly. Capacities follow directly from key width:

Variant	Key types	Key size	Capacity	Node size	Source
`L16BTree`	`sbyte`, `byte`, `short`, `ushort`, `char`	2 B (slot-wise)	38	256 B	`L16BTree.cs` — `Index16Chunk.Capacity = 38`
`L32BTree`	`int`, `uint`, `float`	4 B	29	256 B	`L32BTree.cs` — `Index32Chunk.Capacity = 29`
`L64BTree`	`long`, `ulong`, `double`	8 B	19	256 B	`L64BTree.cs` — `Index64Chunk.Capacity = 19`
`String64BTree`	`String64`	64 B	4	356 B	`String64BTree.cs` — `IndexString64Chunk.Capacity = 4`

The L16 storage is slightly subtle: keys are stored as 2 B regardless of whether TKey is 1 B (sbyte/byte) or 2 B (short/ushort/char). The variant exists per key type to give the JIT a monomorphised search routine.

Why these capacities and not "the obvious" ones

L16 could fit a few more 2 B keys than 38 if you packed harder, and L64 only fits 19 because the 8 B HighKey plus the 8 B keys (×19 = 152) plus the 4 B values (×19 = 76) plus 24 B of header = 260 B — the storage authors keep HighKey co-located with OlcVersion in the first 128 B region (so OLC readers and B-link gap checks touch one ALP-paired cache line) and let that constrain capacity. The trade is honest: lower fan-out per node but every concurrent-read fast path takes one cache miss, not two.

Per-key concrete classes

Each variant gives two final classes per key type: XSingleBTree (AllowMultiple = false) and XMultipleBTree (AllowMultiple = true). The multi-value classes store values in a side VariableSizedBufferSegment<int, TStore> and put the buffer-head ID in the BTree's value slot.

SIMD search

All variants implement BinarySearch with a SIMD-accelerated CountLessThan over the key array — Vector256 (8 × int / 16 × short / 4 × long), falling back to Vector128 and then scalar. At leaf capacities of 19–38, the SIMD path resolves a search in 1–3 vector ops. The B-link HighKey lookups use the same path.

4. Concurrency

Two primitives, two regimes.

Readers — `OlcLatch` (optimistic, lock-free)

OlcLatch.cs

OlcLatch is a 32-bit field embedded in every node's OlcVersion slot:

Bits	Field
0	Locked (writer holds the latch)
1	Obsolete (node was merged away — readers must restart)
2–31	Version counter (30 bits, ~1.07 B versions before wrap)

The reader API performs zero writes to shared state. ReadVersion() returns the version or 0 if the node is locked or obsolete (signalling restart). The reader threads the version through its work and calls ValidateVersion(expected) afterwards — if the version changed, the read might have been torn and the reader restarts. On x64 (TSO), no memory barriers are needed — loads aren't reordered with other loads, and the write-lock CAS provides the acquire/release on the writer side.

On arm64 that is not sufficient, and ValidateVersion issues an explicit Interlocked.MemoryBarrier() before the validating re-read. The reader's plain data loads (node scan, value copy) sit between ReadVersion() and that re-read, and an acquire load only stops later accesses from hoisting above it — it does not stop those earlier plain loads from sinking below it on a weakly-ordered CPU, which would void the validation. The barrier is emitted under if (!X86Base.IsSupported), a JIT-time constant: it folds to nothing on x64 and becomes dmb ish on arm64. See OlcLatch.ValidateVersion and the memory-ordering discipline in the root CLAUDE.md.

This is plain Optimistic Lock Coupling (Leis et al., 2016) — see 01-foundation for how it composes with the broader synchronization story.

A failed validation emits a Concurrency:OlcLatch:ValidationFail event (12-observability). Lookup retries up to MaxOptimisticRestarts = 3 times before falling back to a pessimistic loop that retries indefinitely.

Writers — `SpinWriteLock` (two-phase, yield-capped)

BTree.cs SpinWriteLock

Acquiring a writer latch is via OlcLatch.TryWriteLock() which CAS-sets bit 0. If that fails, SpinWriteLock walks two phases — deliberately avoiding Thread.Sleep(1), which on Windows stalls for ~15 ms (one timer-tick), an eternity at the latch hold times this code targets.

// Phase 1: tight PAUSE loop — 64 iterations of Thread.SpinWait(1).
// On Zen 4 a PAUSE is ~50 cycles → ~100 ns total. On Skylake+ closer to ~2 µs.
// Covers the common case of a leaf insert/delete on another core completing.
for (int i = 0; i < 64; i++) {
    Interlocked.Increment(ref _writeLockFailures);
    Thread.SpinWait(1);
    if (latch.TryWriteLock()) return false; // got it, with contention
}

// Phase 2: SpinWait with sleep1Threshold = -1 (Sleep(1) DISABLED).
// Escalates to Thread.Yield / Thread.Sleep(0) only — never Sleep(1).
// Holder is likely doing a split/merge or sharing our SMT core.
SpinWait spin = default;
do {
    Interlocked.Increment(ref _writeLockFailures);
    spin.SpinOnce(-1);
} while (!latch.TryWriteLock());

Phase 1 is calibrated for typical OLC latch hold times (~100–500 ns — a single key compare + array shift). Phase 2 is for the rare cases where the holder is doing a node split/merge (which takes microseconds, not nanoseconds), or where threads share an SMT core. The -1 threshold on SpinWait.SpinOnce is the magic that disables Sleep(1) while still permitting Yield() / Sleep(0).

_writeLockFailures is a diagnostic counter, surfaced via the WriteLockFailures property.

Obsolete-node reclamation

When a merge removes a node, its chunk can't be freed immediately — concurrent readers may still hold the chunk ID. The BTree maintains a per-instance DeferredNodeList (inline buffer of 8 + overflow List); the merged-out chunk is recorded with RetireEpoch = EpochManager.GlobalEpoch, and reclamation happens when EpochManager.MinActiveEpoch > RetireEpoch. Reclamation runs every 64 mutations (the _deferredReclaimSkip counter) and on UoW dispose.

This is the same epoch model as the page cache (01-foundation §4) — reused, not reinvented.

5. Operations

All operations live on BTree<TKey, TStore>. Public entry points work in two passes: a fast OLC path that does no writes to shared state, then a pessimistic fallback that takes write locks.

`Add(key, value, ref accessor, out bufferRootId)` — Insert

BTree.Insert.cs

OLC fast path: descend optimistically, validate the leaf version, TryWriteLock the leaf, retry-on-CAS-failure or fall through. The slow path InsertIterative descends with full path recording, handles overflow by spill-left → spill-right → split, and propagates separator-key updates back up the path.

Key behaviours:

Spill before split: when a leaf is full, it tries to push items to a neighbour first (spillLeft / spillRight) — a half-full target threshold reduces follow-up LeafFull frequency for sequential-append workloads (else every subsequent insert would trigger another full→spill cycle).
Contention split: a leaf with ContentionHint >= ContentionSplitThreshold = 3 and >= Capacity/2 items is proactively split even when not full — breaks up hotspots before they cause OLC restart storms. Counted via ContentionSplitCount.
Multi-value indexes: AllowMultiple = true allocates a VariableSizedBufferSegment buffer per key on first insert, returns the buffer's HEAD chunk ID via out bufferRootId; subsequent inserts append to the buffer (_storage.Append).
Cached last-key fast path: _cachedLastKey is checked for sequential-append workloads (PK indexes during bulk load); a hit skips the BTree descent.

Returns the ElementId (slot index within the buffer for multi-value; record ID for single).

`Remove(key, out value, ref accessor)` — Delete

BTree.Remove.cs

OLC fast path: descend optimistically, find the leaf, TryWriteLock and remove if no SMO is required. Pessimistic fallback RemoveCorePessimistic is full path recording, with borrow-left → borrow-right → merge-left → merge-right for underflow.

For multi-value indexes, Remove(key, ...) removes the whole key (and its buffer). To remove a single value from a multi-value key, use RemoveValue below.

`TryGet(key, ref accessor)` — Lookup

BTree.cs TryGet

Pure OLC: descent reads versions only, never writes. Returns Result<int, BTreeLookupStatus> (Found/NotFound). After MaxOptimisticRestarts = 3 failed restarts, falls through to TryGetPessimistic which loops on OLC indefinitely (still no writes — pessimistic here means "no retry budget", not "take a lock").

For multi-value indexes, use TryGetMultiple which returns a VariableSizedBufferAccessor<int, TStore> over the value list.

`EnumerateRange(min, max)` / `EnumerateRangeDescending` / `EnumerateRangeMultiple` — RangeScan

BTree.RangeEnumerator.cs

A ref struct enumerator that seeks the start leaf and walks the leaf-chain forward (via NextChunk) or backward (via PrevChunk). Per-leaf OLC validation: read the leaf version before reading the items, validate after; on validation failure, re-read just that leaf from the beginning/end.

Variants:

EnumerateRange(min, max) — bounded forward, unique-only (throws on AllowMultiple)
EnumerateRangeDescending(min, max) — bounded reverse
EnumerateRangeMultiple(min, max) — bounded forward, multi-value only, expands buffers
EnumerateRangeMultipleDescending(min, max) — bounded reverse, multi-value
EnumerateLeaves() — unbounded forward, walks the entire leaf chain

The caller must be inside an epoch scope (01-foundation §4) — without that, pages backing leaves could be evicted mid-scan.

`RemoveValue(key, elementId, value, ref accessor)` — multi-value removal

BTree.cs RemoveValue

This is not "remove by key" — RemoveValue removes one value from a multi-value key's buffer. Important: a multi-value index entry holds many values per key (e.g., "all entities with Status = Active"), and the engine often needs to remove one element while leaving the rest of the buffer intact.

Flow:

FindLeaf(key) — under OLC, then WriteLock the leaf for an authoritative read.
Re-find the key under lock (OLC concurrent removes may have shifted indices).
Read the buffer ID from the leaf value slot.
_storage.RemoveFromBuffer(bufferId, elementId, value) — variable-sized-buffer-segment delete.
WriteUnlock the leaf (version bump now visible to OLC readers).
If the buffer is now empty, remove the BTree key entry too (via RemoveCorePessimistic) and delete the buffer.

(preserveEmptyBuffer — a fifth parameter that kept the key alive for the HEAD→TAIL temporal-index link — was removed in #666 along with the TAIL architecture. TemporalIndexQuery.cs and VersionedIndexEntry.cs were deleted at the same time.)

`Move(oldKey, newKey, value)` / `MoveValue(...)` — compound move

BTree.Move.cs

Atomically removes from one key and inserts under another — used when an indexed field changes value on update. Same-leaf fast path takes one write lock; different-leaf path locks the two leaves in ChunkId order to avoid deadlock. Falls back to a fully pessimistic remove+insert pair under contention.

6. Structural mutations

Two SMOs (Structure Modification Operations) extend or shrink the tree's shape.

NodeSplit

BTree.NodeWrapper.cs SplitRight, per-variant SplitRight in L16BTree.cs et al.

Triggered when a leaf is full and neither neighbour can absorb a spill (or under contention with a hot leaf at ≥ half capacity). Allocates a new right sibling, moves the upper half of the items to it, and:

Updates the leaf chain: left.Next → right, right.Next → oldNext, mirror for Prev.
B-link HighKey update: right.HighKey = left.oldHighKey (right inherits the upper bound); left.HighKey = right.GetFirst().Key (left's new upper bound is the new separator).
Returns the new right node + a separator key to be promoted to the parent.

The parent-side promotion happens iteratively in InsertIterative — if the parent overflows, it splits too; if the root splits, a new root is allocated (under the root's write lock, to serialize concurrent root creators).

Counted via SplitCount and (for contention-triggered splits) ContentionSplitCount.

NodeMerge

BTree.NodeWrapper.cs MergeLeft, per-variant MergeLeft in L16BTree.cs et al.

Triggered when a node falls below half capacity and neighbours can't borrow more (borrow-left/borrow-right are tried first). Merges the right node into the left, marks the right as obsolete (via OlcLatch.MarkObsolete), and adds it to the DeferredNodeList for epoch-deferred reclamation. The left's HighKey inherits the right's, preserving the B-link invariant.

Cascading merges propagate upward iteratively. If the root collapses to one child, the child becomes the new root and the old root is deferred-freed.

Counted via MergeCount.

7. Multi-tree segments — the BTree directory

A single ChunkBasedSegment<TStore> can host multiple B+Trees — most commonly all secondary indexes for an archetype's components share one segment (ArchetypeClusterState.IndexSegment), which keeps page-cache locality high. (The pre-#629 pattern of a per-component PK B+Tree plus secondary indexes sharing one ComponentTable-owned segment no longer applies: secondary indexes are per-archetype, and the PK B+Tree was removed.) The directory mechanism makes this work.

Layout

The first 4 chunks of every BTree-bearing segment (DirectoryChunkCount = 4) are reserved for the directory. How many entries fit depends on the segment's node stride, so it is computed rather than hardcoded — BTreeBase.MaxDirectoryEntriesFor(stride): chunk 0 loses BTreeDirectoryHeader (2 B) to its header and chunks 1-3 are pure entry storage, at BTreeDirectoryEntry = 12 B each. That gives 84 at the 256-byte numeric stride and 116 at String64BTree's 356-byte stride. (A hardcoded MaxDirectoryEntries = 20 — the figure for a 64-byte stride — was removed in #657; the cap must stay exactly what the reserved chunks hold, since entry n+1 would land in the first node chunk.)

Chunk 0:  [ BTreeDirectoryHeader (2 B EntryCount) ] [ entry₀ ][ entry₁ ]...
Chunk 1:  [ entry_n ][ entry_n+1 ] ...
Chunk 2:  [ ... ]
Chunk 3:  [ ... ]

`BTreeDirectoryHeader`

[StructLayout(LayoutKind.Sequential, Pack = 2)]
internal struct BTreeDirectoryHeader {
    public ushort EntryCount;   // how many BTrees registered in this segment
}

`BTreeDirectoryEntry` — 12 bytes per BTree

[StructLayout(LayoutKind.Sequential, Pack = 2)]
internal struct BTreeDirectoryEntry {
    public short StableId;      // -1 = PK, FieldId = secondary, 0 = standalone/test
    public short Reserved;
    public int   RootChunkId;
    public int   Count;
}

StableId is the lookup key: -1 is the convention for the PK index, positive values are FieldInfo.FieldId for secondary indexes, 0 is for standalone/test trees. Each BTree instance caches its directory location in _dirChunkId + _dirEntryOffset at construction (RegisterInDirectory for create, FindInDirectory for load) so SyncHeader is an O(1) write — no scan.

Importantly: each BTree on a shared segment has its own root and count in the directory entry. Without this, multiple BTrees sharing a segment would corrupt each other's bookkeeping.

8. Telemetry spans

B+Tree mutation paths emit typed events (12-observability) — the events are JIT-eliminated when their gates are off. Definitions live in BTreeEvents.cs:

Span event	Where emitted	Payload
`BTreeInsert`	`BTree.Add` entry	none — operation identity carried by the kind
`BTreeDelete`	`BTree.Remove`, `BTree.RemoveValue` entries	none
`BTreeNodeSplit`	`NodeWrapper.SplitRight` (wraps the storage call)	none
`BTreeNodeMerge`	`NodeWrapper.MergeLeft` (wraps the storage call)	none

These are payload-less spans — 37 B header, 53 B with trace context. The event kind alone identifies the operation; finer-grained labelling would balloon ring-buffer cost on inserts that can fire at ~1 M/s in bulk-load workloads.

What's not instrumented (and why)

TryGet / TryGetMultiple (lookup) — deliberately uninstrumented. A primary-key lookup is the engine's tightest hot path (multiple millions per second under load); the cost of a span begin/end pair is observable in microbenchmarks. Lookups are inferred from caller-level spans (Entity.Read, query planner) instead.
OLC restarts — counted via OptimisticRestarts / PessimisticFallbacks properties on the BTree, not per-event. Validation failures do emit a Concurrency:OlcLatch:ValidationFail event from OlcLatch.ValidateVersion.

What's instrumented but gated

EnumerateRange* (range scans) — Data:Index:BTree:RangeScan is a Tier-2-gated span. Off by default (TelemetryConfig.DataIndexBTreeRangeScanActive); when enabled, it records ResultCount and RestartCount per scan. Costs ~10 ns per scan when off (a single static bool check).
Latch operations — OlcLatch emits Concurrency:OlcLatch:WriteLockAttempt, WriteUnlock, MarkObsolete, ValidationFail — all Tier-2-gated, all off in normal operation. Useful for diagnosing OLC contention storms.

Table of Contents

03 — Indexing

1. Overview — one tree, many uses

2. Node layout — 256 B = 4 cache lines (numeric variants)

`BTree<TKey, TStore> : BTreeBase<TStore>`

3. Variants & per-node capacities

Why these capacities and not "the obvious" ones

Per-key concrete classes

SIMD search

4. Concurrency

Readers — `OlcLatch` (optimistic, lock-free)

Writers — `SpinWriteLock` (two-phase, yield-capped)

Obsolete-node reclamation

5. Operations

`Add(key, value, ref accessor, out bufferRootId)` — Insert

`Remove(key, out value, ref accessor)` — Delete

`TryGet(key, ref accessor)` — Lookup

`EnumerateRange(min, max)` / `EnumerateRangeDescending` / `EnumerateRangeMultiple` — RangeScan

`RemoveValue(key, elementId, value, ref accessor)` — multi-value removal

`Move(oldKey, newKey, value)` / `MoveValue(...)` — compound move

6. Structural mutations

NodeSplit

NodeMerge

7. Multi-tree segments — the BTree directory

Layout

`BTreeDirectoryHeader`

`BTreeDirectoryEntry` — 12 bytes per BTree

8. Telemetry spans

What's not instrumented (and why)

What's instrumented but gated

See also

Table of Contents

03 — Indexing

1. Overview — one tree, many uses

2. Node layout — 256 B = 4 cache lines (numeric variants)

BTree<TKey, TStore> : BTreeBase<TStore>

3. Variants & per-node capacities

Why these capacities and not "the obvious" ones

Per-key concrete classes

SIMD search

4. Concurrency

Readers — OlcLatch (optimistic, lock-free)

Writers — SpinWriteLock (two-phase, yield-capped)

Obsolete-node reclamation

5. Operations

Add(key, value, ref accessor, out bufferRootId) — Insert

Remove(key, out value, ref accessor) — Delete

TryGet(key, ref accessor) — Lookup

EnumerateRange(min, max) / EnumerateRangeDescending / EnumerateRangeMultiple — RangeScan

RemoveValue(key, elementId, value, ref accessor) — multi-value removal

Move(oldKey, newKey, value) / MoveValue(...) — compound move

6. Structural mutations

NodeSplit

NodeMerge

7. Multi-tree segments — the BTree directory

Layout

BTreeDirectoryHeader

BTreeDirectoryEntry — 12 bytes per BTree

8. Telemetry spans

What's not instrumented (and why)

What's instrumented but gated

See also

`BTree<TKey, TStore> : BTreeBase<TStore>`

Readers — `OlcLatch` (optimistic, lock-free)

Writers — `SpinWriteLock` (two-phase, yield-capped)

`Add(key, value, ref accessor, out bufferRootId)` — Insert

`Remove(key, out value, ref accessor)` — Delete

`TryGet(key, ref accessor)` — Lookup

`EnumerateRange(min, max)` / `EnumerateRangeDescending` / `EnumerateRangeMultiple` — RangeScan

`RemoveValue(key, elementId, value, ref accessor)` — multi-value removal

`Move(oldKey, newKey, value)` / `MoveValue(...)` — compound move

`BTreeDirectoryHeader`

`BTreeDirectoryEntry` — 12 bytes per BTree