Struct BTree 

pub struct BTree<P: PageStore> { /* private fields */ }

B+ Tree implementation

Implementations

impl<P: PageStore> BTree<P>

pub fn new(pager: Arc<P>) -> Self

Create a new B+ tree using the given pager

pub fn with_root(pager: Arc<P>, root_page_id: u32) -> Self

Create a B+ tree with an existing root

pub fn root_page_id(&self) -> u32

Get the root page ID

pub fn is_empty(&self) -> bool

Check if tree is empty

pub fn get(&self, key: &[u8]) -> BTreeResult<Option<Vec<u8>>>

Get value for a key

pub fn get_with_budget( &self, key: &[u8], limit_bytes: usize, ) -> BTreeResult<Option<Vec<u8>>>

Bound value materialization before allocating overflow or decode buffers.

pub fn insert(&self, key: &[u8], value: &[u8]) -> BTreeResult<()>

Insert a key-value pair.

Applies the value-layout spill ladder before touching the tree: the 256 MB ceiling rejects here without any allocation; values at or below COMPRESSION_THRESHOLD go inline raw; larger values select raw/compressed bytes and spill beyond OVERFLOW_THRESHOLD into an crate::storage::overflow::OverflowChain. The encoded bytes are then committed through Self::insert_encoded.

pub fn upsert(&self, key: &[u8], value: &[u8]) -> BTreeResult<()>

Insert or update a key. If the key already exists and the new value has the same length as the old, the value bytes are overwritten in place — no structural changes, no rebalance, one leaf page write.

Falls back to delete + insert when the key is missing or the new value has a different length. Callers like persist_entities_to_pager that re-serialize a mutated entity with a fixed-width schema almost always hit the fast path, eliminating the BTree::delete + rebalance cost that previously dominated UPDATE workloads (~50% of bulk_update CPU).

pub fn try_upsert_inline_without_splits( &self, items: &[(Vec<u8>, Vec<u8>)], ) -> BTreeResult<bool>

Upsert inline values without allocating, freeing or changing tree links. The caller must make every value durable in its WAL before calling this method. Returns false without writing if any item needs a structural update or an overflow chain.

pub fn upsert_batch_sorted( &self, items: &[(Vec<u8>, Vec<u8>)], ) -> BTreeResult<()>

Batch upsert for sorted keys landing in a small set of leaves.

Walks to each leaf once, applies every same-or-shrink in-place overwrite that belongs there, writes the page once, then moves on. Keys that miss or whose new value grows fall back to the generic single-key upsert path — correctness identical, structural re-layout handled there.

Callers pass lex-sorted (key, value) pairs. For the entity UPDATE path, IDs are big-endian so u64 ordering = lex ordering.

pub fn bulk_insert_sorted( &self, items: &[(Vec<u8>, Vec<u8>)], ) -> BTreeResult<()>

Bulk insert for sorted key-value pairs.

Optimized for monotonically increasing keys (e.g. entity IDs):

• Walks to the target leaf ONCE, then appends many entries before re-walking.
• Writes each leaf only once per batch (amortized over many inserts).

Falls back to per-entity insert on splits.

pub fn delete(&self, key: &[u8]) -> BTreeResult<bool>

Delete a key

pub fn cursor_first(&self) -> BTreeResult<BTreeCursor<P>>

Create a cursor starting at the first entry

pub fn cursor_seek(&self, key: &[u8]) -> BTreeResult<BTreeCursor<P>>

Create a cursor starting at or after the given key

pub fn range( &self, start_key: &[u8], end_key: &[u8], ) -> BTreeResult<Vec<(Vec<u8>, Vec<u8>)>>

Range scan from start_key to end_key (inclusive)

pub fn count(&self) -> BTreeResult<usize>

Count entries in the tree

impl<P: PageStore> BTree<P>

pub fn has_retirement_readers(&self) -> bool

pub fn retired_pages(&self) -> BTreeResult<Vec<u32>>

Enumerate a retired generation before changing the allocator. Never follow leaf sibling links as additional ownership edges: interior children already own every leaf. Validate overflow chains as well.

pub fn visit_recoverable_leaves<C, R>( &self, claim: C, record: R, ) -> BTreeResult<Vec<u32>>

where C: FnMut(u32) -> BTreeResult<()>, R: FnMut(Vec<u8>, Vec<u8>) -> BTreeResult<()>,

Stream the verified leaves of a damaged tree. Only checksum failures at the proven leaf depth may be skipped. The caller must separately prove that no allocated pages remain unowned before publishing any output.