Expand description
The implementation of a node for a history patricia tree
Structs
Wraps the label with which to find a node in storage.
A TreeNode represents a generic node of a Merkle Patricia Trei with ordering. The main idea here is that the tree is changing at every epoch and that we do not need to touch the state of a node, unless it changes. The leaves of the tree represented by these nodes is supposed to allow for a user to monitor the state of a key-value pair in the past. We achieve this by including the epoch a leaf was added as part of the hash stored in it. At a later time, we may need to access older sub-trees of the tree built with these nodes. To facilitate this, we require this struct to include the last time a node was updated as well as the oldest descendant it holds.
Represents a TreeNode
with its current state and potential future state.
Depending on the epoch
which the Directory believes is the “most current”
version, we may need to load a slightly older version of the tree node. This is because
we can’t guarantee that a “publish” operation is globally atomic at the storage layer,
however we do assume record-level atomicity. This means that some records may be updated
to “future” values, and therefore we might need to temporarily read their previous values.
Enums
There are three types of nodes: root, leaf and interior. This enum is used to mark nodes using the node_type variable of a TreeNode.
Functions
Create an empty root node.
Create a specific leaf node.