nomt_core/
page.rs

1//! Pages: efficient node storage.
2//!
3//! Because each node in the trie is exactly 32 bytes, we can easily pack groups of nodes into
4//! a predictable paged representation regardless of the information in the trie.
5//!
6//! Each page is 4096 bytes and stores up to 126 nodes plus a unique 32-byte page identifier,
7//! with 32 bytes left over.
8//!
9//! A page stores a rootless sub-tree with depth 6: that is, it stores up to
10//! 2 + 4 + 8 + 16 + 32 + 64 nodes at known positions.
11//! Semantically, all nodes within the page should descend from the layer above, and the
12//! top two nodes are expected to be siblings. Each page logically has up to 64 child pages, which
13//! correspond to the rootless sub-tree descending from each of the 64 child nodes on the bottom
14//! layer.
15//!
16//! Every page is referred to by a unique ID, given by `parent_id * 2^6 + child_index + 1`, where
17//! the root page has ID `0x00..00`. The child index ranges from 0 to 63 and therefore can be
18//! represented as a 6 bit string. This module exposes functions for manipulating page IDs.
19//!
20//! The [`RawPage`] structure wraps a borrowed slice of 32-byte data and treats it as a page.
21
22/// Depth of the rootless sub-binary tree stored in a page
23pub const DEPTH: usize = 6;
24
25// Total number of nodes stored in one Page. It depends on the `DEPTH`
26// of the rootless sub-binary tree stored in a page following this formula:
27// (2^(DEPTH + 1)) - 2
28pub const NODES_PER_PAGE: usize = (1 << DEPTH + 1) - 2;
29
30/// A raw, unsized page data slice.
31pub type RawPage = [[u8; 32]];
nomt_core/page.rs

nomt_core/
page.rs
