Expand description
The implementation of a node for a history patricia tree
Structs
- Wraps the label with which to find a node in storage.
- FIXME(@klewi): update this documentation A TreeNode represents a generic node of a Merkle Patricia Trie 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
epochwhich 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 the type of a TreeNode.