Struct BTree 

pub struct BTree<'p> { /* private fields */ }

Implementations

impl<'p> BTree<'p>

pub fn create( pool: &'p BufferPool, tree_id: u16, last_leaf: &'p Cell<Option<u32>>, fast_path_hits: &'p Cell<u64>, fast_path_attempts: &'p Cell<u64>, ) -> Result<Self>

pub fn open( pool: &'p BufferPool, tree_id: u16, root: u32, last_leaf: &'p Cell<Option<u32>>, fast_path_hits: &'p Cell<u64>, fast_path_attempts: &'p Cell<u64>, ) -> Self

pub fn with_tags(self, tags: &'p TagHints) -> Self

Attach the owning handle’s per-keyspace append hints. A handle must do this on EVERY tree it opens, not only the ones it means to speed up: the clearing a split or a delete performs happens through this borrow, so a mutation that arrives on an unattached BTree would leave a hint standing over a tree whose shape it no longer describes.

pub fn root(&self) -> u32

pub fn graft_sorted_range<I>( &mut self, sorted: I, expected_rows: u64, min: &[u8], max: &[u8], scratch_dir: &Path, ) -> Result<Vec<u32>>

where I: Iterator<Item = Result<(Vec<u8>, Vec<u8>, bool)>>,

Pack a sorted run into full pages and splice it into an EMPTY key interval of this tree, instead of inserting its keys one at a time.

This is the shape a CREATE INDEX has: every key of a new index shares one contiguous keyspace ([tag][index id]...) that holds nothing yet, so the run has no existing neighbours to interleave with. SQLite builds the same run into a separate, empty index B-tree with a sorter and OP_IdxInsert; E4 has one tree per database (D1), so the equivalent is to pack the pages and graft them in.

The four steps:

1. Refuse a non-empty interval. One seek to min and one key comparison. A key in [min, max] means the caller’s assumption is wrong, and the graft is refused with RangeNotEmpty before anything is allocated or written.
2. Plan the boundary. plan_graft descends to the leaf whose interval owns min and splits it at the insertion point: records below min become the copied left fragment, records above it the copied right fragment. Both are fresh pages; the standing leaf is read only.
3. Pack. pack_range_pooled fills leaves to 90% and builds the run’s OWN interior levels bottom-up, allocating every page through the ordinary buffer pool. The right continuation is known before the last leaf is written, so the leaf chain is correct on the first and only write of each page.
4. Verify, then splice. The packed subtree is walked (verify_range_pool) before any standing page is touched. Then one two-or-three-child wrapper joins {left fragment, packed root, right fragment} and install_graft copies the O(height) parent path, replacing exactly one child pointer. The retired page numbers are returned for the caller to free.

Interior strategy. The run brings its own interior levels and enters the standing tree as ONE separator. Inserting one separator per packed leaf was the alternative, and it is O(leaves) interior inserts with their own splits – the cost this call exists to remove – so the subtree is grafted whole. The cost is that the grafted subtree’s height is independent of the standing tree’s, so the tree is no longer uniformly deep; descend_with_path already reserves for that.

Page LAYOUT is not preserved, the ENTRY SET is. Which key sits on which page differs from the one-at-a-time insert path (packed leaves are 90% full; split-built leaves are not), and so do page numbers and tree height. Every persisted key and value is identical, which is what tests/index_build_equivalence.rs digests.

Nothing here bypasses the log or swaps a root: every page is an ordinary pooled page, so a page-WAL store logs each one as a normal frame and publishes the whole graft with the caller’s commit. A crash before that commit leaves the standing tree exactly as it was.

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

pub fn insert(&mut self, key: &[u8], val: &[u8]) -> Result<()>

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

Delete one record and maintain sparsely occupied siblings locally. Scratch is bounded by two children plus their parent; published pages remain protected by the ordinary copy-on-write retirement protocol.

pub fn delete_prefix(&mut self, prefix: &[u8]) -> Result<u64>

Scan from from forward, in key order.

SINGLE WRITER. The iterator borrows the pool, not self, so the borrow checker will happily let you insert into this tree while a scan is live. Do not: the iterator re-reads its leaf on every next, so an insert that shifts entries in the leaf it is standing on makes it skip or repeat a row, with no compiler or runtime signal. The engine is single-writer by design, and this is where that assumption is cashed. Remove every key with prefix. Walks matching leaves via the parent path (a cleared leaf still receives the same descent – the separators do not change – so re-descending with the prefix would loop on the first emptied page forever; the advance must go THROUGH the parents, the RangeIter lesson). Each matching leaf is either CLEARED in one page write (every entry matches) or slot-trimmed. Cost: O(matching leaves) page writes + one read-descent each, not O(matching rows) tree operations. Emptied leaves stay allocated (the documented delete posture).

pub fn range(&self, from: &[u8]) -> Result<RangeIter<'p>>

pub fn range_reverse(&self, to: &[u8]) -> Result<ReverseRangeIter<'p>>

Scan keys strictly below to in descending order.