Put
The Put operation in the Merkle Patricia Trie is designed to insert a [key, value] pair into the trie. This seemingly straightforward operation consists of several steps to ensure the trie's structure and properties are maintained. Here's a breakdown:
🪜Steps to Insert a New Node:
Convert Key to Nibble Sequence: Before any operations on the trie, convert the byte key into a sequence of nibbles for easier traversal and node handling.
Fetch the Current Root: Start the insertion process by fetching the current root hash of the trie if not exist.
Locate the Position: Traverse the trie using the nibble sequence to find the appropriate position for the new
[key, value]pair.Handle Existing Node:
If you encounter a node with the same key:
Update its value with the new provided value.
Leaf Node Insertion:
If the nibble sequence leads to a position without an existing node:
Insert a new leaf node using the remaining nibbles and value.
Branch Node Handling:
If the nibble sequence intersects with an existing path:
Insert a branch node at the point of intersection.
Adjust the existing nodes to maintain the trie's structure.
Extension Node Insertion:
If a segment of the nibble sequence is shared among multiple keys:
Insert an extension node to represent the shared nibble segment.
Handle HashNodes:
If during traversal you encounter a HashNode, load the actual node using its hash.
Continue the insertion process as you would with the loaded node.
Last updated