fn insert(
        &mut self,
        entry: TreeEntry,
        parent_nibbles: &Nibbles,
    ) -> (TreeLogEntry, NewLeafData) {
        let version = self.patch_set.root_version();
        let key = entry.key;

        let traverse_outcome = self.patch_set.traverse(key, parent_nibbles);
        let (log, leaf_data) = match traverse_outcome {
            TraverseOutcome::LeafMatch(nibbles, mut leaf) => {
                let log = TreeLogEntry::update(leaf.leaf_index, leaf.value_hash);
                leaf.update_from(entry);
                self.patch_set.insert(nibbles, leaf.into());
                self.metrics.updated_leaves += 1;
                (log, NewLeafData::new(nibbles, leaf))
            }

            TraverseOutcome::LeafMismatch(nibbles, leaf) => {
                self.update_moved_leaf_ref(&nibbles);

                let mut nibble_idx = nibbles.nibble_count();
                loop {
                    let moved_leaf_nibble = Nibbles::nibble(&leaf.full_key, nibble_idx);
                    let new_leaf_nibble = Nibbles::nibble(&key, nibble_idx);
                    let mut node = InternalNode::default();
                    if moved_leaf_nibble == new_leaf_nibble {
                        // Insert a path of internal nodes with a single child.
                        node.insert_child_ref(new_leaf_nibble, ChildRef::internal(version));
                    } else {
                        // Insert a diverging internal node with 2 children for the existing
                        // and the new leaf.
                        node.insert_child_ref(new_leaf_nibble, ChildRef::leaf(version));
                        node.insert_child_ref(moved_leaf_nibble, ChildRef::leaf(version));
                    }
                    let node_nibbles = Nibbles::new(&key, nibble_idx);
                    self.insert_node(node_nibbles, node, true);
                    if moved_leaf_nibble != new_leaf_nibble {
                        break;
                    }
                    nibble_idx += 1;
                }

                let new_leaf = LeafNode::new(entry);
                let new_leaf_nibbles = Nibbles::new(&key, nibble_idx + 1);
                let leaf_data = NewLeafData::new(new_leaf_nibbles, new_leaf);
                let moved_leaf_nibbles = Nibbles::new(&leaf.full_key, nibble_idx + 1);
                let leaf_data = leaf_data.with_adjacent_leaf(moved_leaf_nibbles, leaf);
                (TreeLogEntry::Inserted, leaf_data)
            }

            TraverseOutcome::MissingChild(nibbles) if nibbles.nibble_count() == 0 => {
                // The root is currently empty; we replace it with a leaf.
                let root_leaf = LeafNode::new(entry);
                self.set_root_node(root_leaf.into());
                let leaf_data = NewLeafData::new(Nibbles::EMPTY, root_leaf);
                (TreeLogEntry::Inserted, leaf_data)
            }

            TraverseOutcome::MissingChild(nibbles) => {
                let (parent_nibbles, last_nibble) = nibbles.split_last().unwrap();
                let Some(Node::Internal(parent)) = self.get_mut(&parent_nibbles) else {
                    unreachable!("Node parent must be an internal node");
                };
                parent.insert_child_ref(last_nibble, ChildRef::leaf(version));
                let new_leaf = LeafNode::new(entry);
                let leaf_data = NewLeafData::new(nibbles, new_leaf);
                (TreeLogEntry::Inserted, leaf_data)
            }
        };

        if matches!(log, TreeLogEntry::Inserted) {
            self.insert_node(leaf_data.nibbles, leaf_data.leaf, true);
        }
        if let Some((nibbles, leaf)) = leaf_data.adjacent_leaf {
            self.insert_node(nibbles, leaf, false);
        }

        // Traverse nodes up to the root level and update `ChildRef.version`.
        let mut cursor = traverse_outcome.position();
        while let Some((parent_nibbles, last_nibble)) = cursor.split_last() {
            let child_ref = self
                .patch_set
                .child_ref_mut(&parent_nibbles, last_nibble)
                .unwrap();
            child_ref.version = child_ref.version.max(version);
            cursor = parent_nibbles;
        }

        (log, leaf_data)
    }
Inserts or updates a value hash for the specified `key`. This implementation
is almost verbatim the algorithm described in the Jellyfish Merkle tree white paper.
The algorithm from the paper is as follows:

1. Walk from the root of the tree along the inserted `key` while we can.
2. If the node we've stopped at is an internal node, it means it doesn't have
a child at the corresponding nibble from `key`. Create a new leaf node with `key` and
`value_hash` and insert it as a new child of the found internal node.
3. Else the node we've stopped is a leaf. If the full key stored in this leaf is `key`,
we just need to update `value_hash` stored in the leaf.
4. Else (the node we've stopped is a leaf with `other_key != key`) we need to create
one or more internal nodes that would contain the common prefix between `key`
and `other_key` and a "fork" where these keys differ.

We change step 1 by starting not from the root, but rather from the node ancestor
we've found in [`Self::load_ancestors()`] for a (moderate) performance boost. Note that
due to previous `insert`ions, we may still need to perform more than 1 traversal iteration.

We don't update node hashes; this would lead to a significant compute overhead (internal
nodes on upper levels are updated multiple times in a block). Instead, we recompute
hashes for all updated nodes in [`Self::finalize()`].
core/lib/merkle_tree/src/storage/mod.rs