Question: Why is the key stored during insertion?

[mattgathu]

I was going over the insert method of the Trie struct and subsequently the implementation of iterative_insert. Finally I ended up on the with_key_value associated method of the TrieNode

It looks like this:

rust_radix_trie/src/trie_node.rs

Lines 52 to 63 in 0e295e8

	/// Create a TrieNode with no children.
	pub fn with_key_value(key_fragments: NibbleVec, key: K, value: V) -> TrieNode<K, V> {
	TrieNode {
	key: key_fragments,
	key_value: Some(Box::new(KeyValue {
	key: key,
	value: value,
	})),
	children: no_children![],
	child_count: 0,
	}
	}

and the TrieNode struct itself:

rust_radix_trie/src/trie_node.rs

Lines 6 to 21 in 0e295e8

	#[derive(Debug)]
	pub struct TrieNode<K, V> {
	/// Key fragments/bits associated with this node, such that joining the keys from all
	/// parent nodes and this node is equal to the bit-encoding of this node's key.
	pub key: NibbleVec,
	/// The key and value stored at this node.
	pub key_value: Option<Box<KeyValue<K, V>>>,
	/// The number of children which are Some rather than None.
	pub child_count: usize,
	/// The children of this node stored such that the first nibble of each child key
	/// dictates the child's bucket.
	pub children: [Option<Box<TrieNode<K, V>>>; BRANCH_FACTOR],
	}

Question

Why does the TrieNode store the KeyValue pair and not just the value? I would imagined the key fragments in the NibbleVec represent the key. Doesn't storing the full key defeat the purpose of the trie?

I could be missing something, hence this question 🙂

[michaelsproul]

Hey @mattgathu, you raise a very good point, and I don't believe you're missing anything. I would be interested to try the optimisation you suggest, which would likely require adding functions to deserialise the bytes of the NibbleVec back into the key type

trait TrieKey {
  fn decode_bytes(b: &[u8]) -> Self;
  fn decode_nibble_vec(nv: &NibbleVec) -> Self;
  // .. existing methods
}

Similar to the encode methods, we could make one of these methods optional.

You've shown you have a pretty great understanding of the code, so if you'd like to try implementing this I'd be willing to provide tips here and there

Thanks for dropping by!

[mattgathu]

Thanks for getting back! I will try implementing this and push a pull request. 👍