Expand description
Pages: efficient node storage.
Because each node in the trie is exactly 32 bytes, we can easily pack groups of nodes into a predictable paged representation regardless of the information in the trie.
Each page is 4096 bytes and stores up to 126 nodes plus a unique 32-byte page identifier, with 32 bytes left over.
A page stores a rootless sub-tree with depth 6: that is, it stores up to 2 + 4 + 8 + 16 + 32 + 64 nodes at known positions. Semantically, all nodes within the page should descend from the layer above, and the top two nodes are expected to be siblings. Each page logically has up to 64 child pages, which correspond to the rootless sub-tree descending from each of the 64 child nodes on the bottom layer.
Every page is referred to by a unique ID, given by parent_id * 2^6 + child_index + 1, where
the root page has ID 0x00..00. The child index ranges from 0 to 63 and therefore can be
represented as a 6 bit string. This module exposes functions for manipulating page IDs.
The RawPage structure wraps a borrowed slice of 32-byte data and treats it as a page.
Constants§
- DEPTH
- Depth of the rootless sub-binary tree stored in a page
- NODES_
PER_ PAGE
Type Aliases§
- RawPage
- A raw, unsized page data slice.