quick-patricia-trie

A toy implementation of a patricia tree as used in ethereum.

The implementation is strongly inspired by parity patricia-trie.

Key difference

This is a total reimplementation from scratch so there are numerous differences.

The major ones are:

• much less generic: everything is a &[u8] at some point. The only requirements is for
  the key/value being AsRef[u8]>.
• use of Arena, a struct in charge of allocating all data. As a result, there is
  no need to use elastic-array or some other fixed array based crates. Everything is
  eventually stored in a unique Vec, all references are instead indexes that we can freely
  copy and lookups are thus very fast.
• there is no backend database yet. While it will probably be done in the future, I wanted
  to implement the core idea of the Merkle Patricia Trie as defined in the ethereum doc
  and benchmark it against the parity one based on memory-db.
• it is probably lacking many more features I are so far unecessary (like the iterator seek)

Benchmarks

So far results are promising. There is a criterion crate which tries to run the same
benches as written in the original parity crates.

Trie insertion mirror 1k

Trie insertion random 1k

Trie insertion six high

Trie insertion six mid

Trie insertion random mid

Iterator