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