Skip to main content

Module range

obj_core::btree

Module range 

Source
Expand description

Forward range scan iterator.

See docs/format.md § B+tree write semantics for the snapshot contract this iterator implements. In summary: the iterator captures the tree’s root page-id at construction; subsequent writes (which COW the touched pages) cannot disturb the iterator’s traversal because every page the iterator references remains intact on disk for the lifetime of the iterator. Real MVCC reader snapshots across concurrent writers arrive in M6.

The iterator advances from one leaf to the next by descending from the snapshot root with the search key set to “the smallest key strictly greater than the last emitted key”. It does NOT follow leaf next_sibling pointers.

Why not sibling pointers? In a copy-on-write B+tree the page-id of a leaf changes every time the leaf is rewritten. A left- neighbour leaf that was NOT touched by the rewrite still carries the OLD next_sibling page-id, which now points at a freed page (or, post-recycling, at a completely different node). Updating every potentially-affected sibling on every COW would cascade the rewrite up arbitrarily; descending from the snapshot root is O(log n) per leaf-step but always correct.

next_sibling is still part of the on-disk node header (per docs/format.md § Node header) and is set correctly by every split, but M4 readers do not use it. M6 MVCC reader snapshots may revisit the trade-off when the storage engine can identify a snapshot under which sibling pointers are stable.

§Power-of-ten posture

  • Rule 1. Descent uses the same explicit stack as BTree::get; the iterator’s per-step transition is a bounded-depth descent.
  • Rule 2. Each iterator carries a nodes_visited counter and surfaces Error::BTreeScanLimitExceeded past MAX_RANGE_NODES = 1_000_000.
  • Rule 7. Per-step errors (decode failures, depth-bound trips, scan-limit trips, I/O failures from the pager) are surfaced in-band as Some(Err(...)); the iterator latches itself shut after the first error so subsequent calls return None.

Structs§

RangeIter
A forward iterator over (key, value) pairs in a B+tree.
SnapshotRangeIter
Snapshot-consistent forward iterator over (key, value) pairs.