search

michaelsproul / rust_radix_trie

Fast generic radix trie implemented in Rust
https://docs.rs/radix_trie/
MIT License
184 stars 32 forks source link

Question: Why is the key stored during insertion? #45

Closed mattgathu closed 5 years ago

mattgathu commented 5 years ago

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:

https://github.com/michaelsproul/rust_radix_trie/blob/0e295e8b3928f7ddfe3860d7450b3a3483b4bd8e/src/trie_node.rs#L52-L63

and the TrieNode struct itself:

https://github.com/michaelsproul/rust_radix_trie/blob/0e295e8b3928f7ddfe3860d7450b3a3483b4bd8e/src/trie_node.rs#L6-L21

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 commented 5 years ago

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 commented 5 years ago

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