Module node 

B+tree node encode / decode.

See docs/format.md § B+tree for the on-disk layout. This module is the reference implementation; the tests at the bottom validate round-trip equality and rejection of every documented invariant violation.

Power-of-ten posture

• Rule 2. Every loop iterates over key_count, the slot directory length, or the page-byte range — all bounded by PAGE_SIZE.
• Rule 3. The in-memory DecodedNode uses Vecs, not heapless::Vecs of the worst-case slot count: the worst-case slot count times the worst-case per-key buffer (~1 MiB) would overflow a 2 MiB stack. The B+tree’s traversal stack uses heapless::Vec to satisfy Rule 3 on the hot read path; the decoded representation of a single node is a transient per-page artifact whose heap allocation is unavoidable and is not on a real-time path.
• Rule 5. validate_node is the central invariant check; it is debug_assert!-ed at every mutation site and surfaces as Error::Corruption on decode of a malformed page.
• Rule 7. No unwrap / expect on any error-bearing path; length-prefixed varint reads return Error::Corruption on underflow.

Structs

DecodedNode

Decoded in-memory representation of a B+tree node.

InternalEntry

One internal-node pivot entry in the decoded in-memory representation. The corresponding right child is stored in DecodedNode::children at index i + 1.

LeafEntry

One leaf slot in the decoded in-memory representation.

Enums

NodeKind

Whether a node is an internal node or a leaf.

Constants

INTERNAL_LEFTMOST_CHILD_BYTES

Bytes the leftmost-child page-id occupies in an internal node, immediately after the node header.

INTERNAL_SLOT_BYTES

Bytes per slot in an internal slot directory. The entry is a u32 LE offset followed by a u64 LE right-child page-id.

INTERNAL_SLOT_CAP

Maximum number of slots an internal node can hold at the worst case. Used to size the in-memory slot vector.

LEAF_SLOT_BYTES

Bytes per slot in a leaf slot directory. The entry is a single u32 LE giving the byte offset of the corresponding heap entry.

LEAF_SLOT_CAP

Maximum number of slots a leaf can hold at the worst-case empty key/value sizes. Used to size the in-memory slot vector.

NODE_HEADER_SIZE

Fixed-size B+tree node header. See docs/format.md § Node header.

PAGE_TYPE_BTREE_INTERNAL

Page-type tag for an internal B+tree node. See docs/format.md § Page types.

PAGE_TYPE_BTREE_LEAF

Page-type tag for a leaf B+tree node.

Functions

decode_node

Decode a B+tree page into a DecodedNode.

encode_node

Encode node into page. Stamps the page trailer.

max_inline_value

Maximum value length that still fits inline in a leaf alongside at least one slot. See docs/format.md § Key and value encoding.

max_key_len

Maximum key length the format permits. See docs/format.md § Key and value encoding.

validate_node

Validate node against the format-version-0 invariants.

varint_len

Number of bytes an unsigned LEB128 varint would use for v.

Type Aliases

ChildEntry

Alias for “one of the right-child page-ids in an internal node”. We store children as raw u64s; the on-disk format permits 0 only as the leaf next_sibling sentinel, never as an internal child pointer.