Struct BTree 

pub struct BTree<F: FileBackend = FileHandle> { /* private fields */ }

A B+tree handle.

Construct via BTree::empty (fresh tree allocating a new root leaf) or BTree::open (attach to an existing root page-id). The handle does not own the pager; the caller passes a &mut reference into mutating methods.

Generic over F: FileBackend so the same code works against the production FileHandle and the fault-injection harness. M4 only uses the type parameter as a marker — it appears in the Pager<F> signature of every method.

Single-writer: every mutating method takes &mut self. The pager already enforces single-writer at the file level (M3); the B+tree inherits the same property.

Implementations

impl<F: FileBackend> BTree<F>

pub fn delete(&mut self, pager: &mut Pager<F>, key: &[u8]) -> Result<bool>

Remove key from the tree. Returns Ok(true) if it was present (and removed), Ok(false) if the key was absent.

Errors

Propagates pager / decode errors. Surfaces Error::BTreeDepthExceeded if the tree height exceeds MAX_BTREE_DEPTH. No panics.

impl<F: FileBackend> BTree<F>

pub fn insert( &mut self, pager: &mut Pager<F>, key: &[u8], value: &[u8], ) -> Result<()>

Insert key → value into the tree. Returns Error::BTreeKeyExists if key is already present.

Copy-on-write: every node touched on the path is allocated as a fresh page through the pager. The pre-insert pages enter the freelist before this function returns, but only after every new page has been staged in the WAL transaction. The caller must call Pager::commit to make the insert durable.

Errors

• Error::BTreeKeyTooLarge if the key exceeds PAGE_SIZE / 4.
• Error::BTreeValueTooLarge if the (key, value) pair will not fit inline in a leaf.
• Error::BTreeKeyExists if key is already present.
• Error::BTreeDepthExceeded if the tree height would exceed MAX_BTREE_DEPTH.
• Error::Corruption / Error::Io propagated from the pager.

impl<F: FileBackend> BTree<F>

pub fn range<'a, R>( &self, pager: &'a mut Pager<F>, range: R, ) -> Result<RangeIter<'a, F>>

where R: RangeBounds<Vec<u8>>,

Construct a forward iterator over the half-open range range. Bounds are inclusive on start (per RangeBounds) and exclusive on end. An unbounded start/end is permitted (yielding ..end, start.., or ..).

Bounds are taken as RangeBounds<Vec<u8>> so the four idiomatic Rust range syntaxes — .., start.., ..end, start..end, start..=end — and the (Bound<Vec<u8>>, Bound<Vec<u8>>) tuple all compose naturally.

Errors

Returns Error::BTreeDepthExceeded, Error::Corruption, or Error::Io propagated from the descent to the first leaf. Per-step errors during iteration are surfaced via Some(Err(...)) from next.

pub fn iter<'a>(&self, pager: &'a mut Pager<F>) -> Result<RangeIter<'a, F>>

Iterate over every (key, value) pair in the tree. Sugar for range(..).

The Clippy iter_not_returning_iterator warning would normally fire here because the return type is wrapped in a Result (construction can fail). We accept the deviation because the alternative — making iter infallible and returning errors on the first next() — surprises the caller more.

Errors

As for BTree::range.

pub fn range_via_snapshot<'a, R>( pager: &'a Pager<F>, snapshot: &'a ReaderSnapshot<F>, root: PageId, range: R, ) -> Result<SnapshotRangeIter<'a, F>>

where R: RangeBounds<Vec<u8>>,

Snapshot-consistent variant of BTree::range — every page read during descent and leaf-scan is resolved as-of snapshot via crate::pager::ReaderSnapshot::read_page rather than the live Pager::read_page (which consults the WAL overlay, including a concurrent writer’s post-snapshot commits).

This is the range/count analogue of BTree::get_via_snapshot (M12 #12): a read transaction documented as snapshot-isolated must enumerate range and count results consistently with its pinned LSN. Walking the live pager would let a concurrent writer’s post-snapshot index entries leak into the read txn’s range/count.

root is the B+tree root captured at the reader’s snapshot-time view of the catalog (the descriptor read via crate::Catalog::lookup_via_snapshot); the caller is responsible for handing in the snapshot-time root.

Errors

As BTree::range, plus snapshot read errors propagated from crate::pager::ReaderSnapshot::read_page.

impl<F: FileBackend> BTree<F>

pub fn open(_pager: &Pager<F>, root: PageId) -> Result<Self>

Attach a B+tree handle to an existing root page-id.

The root page is NOT read here — BTree::open is a pure constructor that records the root id. The first mutating or reading call will fault the root in via Pager::read_page.

Errors

Returns Error::InvalidArgument if root is zero. (Zero is the sentinel “no tree”; the caller should use BTree::empty to bootstrap.)

pub fn empty(pager: &mut Pager<F>) -> Result<Self>

Allocate a fresh empty B+tree.

Allocates one new page through the pager, encodes an empty leaf node into it, and writes it through the WAL transaction buffer. The caller is responsible for calling Pager::commit before relying on the tree being durable.

Errors

Propagates pager errors from Pager::alloc_page and Pager::write_page.

pub fn root(&self) -> PageId

The current root page-id of this tree.

Mutating methods update this in place after a successful write. The caller can persist this id externally so that a subsequent BTree::open reattaches to the same tree.

pub fn get(&self, pager: &mut Pager<F>, key: &[u8]) -> Result<Option<Vec<u8>>>

Look up key in the tree. Returns None if absent.

The traversal walks root → leaf using an explicit stack of page-ids (no recursion, no heap allocation — the stack is a heapless::Vec).

Errors

• Error::Corruption if any page along the path fails to decode.
• Error::BTreeDepthExceeded if the depth bound trips (would require a tree height ≥ 32).
• Error::Io / Error::InvalidArgument propagated from the pager on a cache-miss read.

pub fn get_via_snapshot( pager: &Pager<F>, snapshot: &ReaderSnapshot<F>, root: PageId, key: &[u8], ) -> Result<Option<Vec<u8>>>

Snapshot-consistent variant of BTree::get — descends the tree using crate::pager::ReaderSnapshot::read_page rather than the live Pager::read_page (which consults the WAL overlay — including a concurrent writer’s post-snapshot commits).

Used by the M6 #53 fix: a reader’s Collection<T>::get must walk the primary B+tree consistently with the snapshot’s pinned LSN. Without this, a writer that COW-frees a page and reallocates the same page-id can serve the reader a page whose state.view content is no longer a valid B+tree node, surfacing as Error::Corruption { page_id: 0 } from crate::btree::node::decode_node.

root is the B+tree root captured at the reader’s relevant snapshot-time view of the catalog (i.e. the descriptor’s primary_root read via crate::Catalog::lookup_via_snapshot). Walking from the writer’s live root would defeat the snapshot read; the caller is responsible for handing in the snapshot-time root.

Errors

• Error::BTreeDepthExceeded if the tree height exceeds MAX_BTREE_DEPTH.
• Error::Corruption / Error::BTreeInvariantViolated propagated from the descent.
• Snapshot read errors propagated from crate::pager::ReaderSnapshot::read_page.

Trait Implementations

impl<F: Debug + FileBackend> Debug for BTree<F>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.