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 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 OVERFLOW_THRESHOLD go inline raw; larger values may inline compressed or spill 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 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.