Module btree 

B+tree (L3) — copy-on-write B+tree over the pager.

The B+tree is the data structure both the primary store (M5) and every secondary index (M7) will compose over. M4 introduces the data structure itself; M5+ wire it into typed catalog and index layers.

See docs/format.md § B+tree for the authoritative on-disk layout this module is the reference implementation of.

Power-of-ten posture

• Rule 1. Every tree traversal uses an explicit heapless::Vec <PageId, MAX_BTREE_DEPTH> stack; no recursive descent. Exceeding the depth bound returns Error::BTreeDepthExceeded rather than exhausting the call stack.
• Rule 2. Per-node loops iterate over key_count, which is bounded by the slot directory capacity (a function of PAGE_SIZE known at compile time). Range scans carry an explicit MAX_RANGE_NODES budget.
• Rule 5. Node invariants (sorted keys, level monotonicity, slot-count bounds) are encoded as debug_assert!s in validate_node; release builds surface a tripped invariant as Error::BTreeInvariantViolated.
• Rule 7. No unwrap / expect in the production code path. Decode errors surface as Error::Corruption; semantic errors surface as one of the BTree* variants on Error.

Re-exports

pub use crate::btree::range::RangeIter;

pub use crate::btree::node::decode_node;

pub use crate::btree::node::encode_node;

pub use crate::btree::node::max_inline_value;

pub use crate::btree::node::max_key_len;

pub use crate::btree::node::validate_node;

pub use crate::btree::node::ChildEntry;

pub use crate::btree::node::DecodedNode;

pub use crate::btree::node::InternalEntry;

pub use crate::btree::node::LeafEntry;

pub use crate::btree::node::NodeKind;

pub use crate::btree::node::NODE_HEADER_SIZE;

Modules

delete

B+tree delete path with merge / borrow rebalancing.

insert

B+tree insert path with copy-on-write splits.

node

B+tree node encode / decode.

range

Forward range scan iterator.

Structs

BTree

A B+tree handle.

Constants

MAX_BTREE_DEPTH

Maximum B+tree depth.

MAX_RANGE_NODES

Maximum number of B+tree nodes visited in a single range scan.