DAT (double array trie) POC

[aion-jin]

DAT detail:

https://linux.thai.net/~thep/datrie/datrie.html

C :

https://github.com/omeid/libdatrie
Java:

https://github.com/digitalstain/DoubleArrayTrie
JS:

https://github.com/bramstein/datrie

compare with
BTC merkle tree:
https://bitcoin.org/en/developer-guide#term-merkle-tree

Eth patricia-tree:
https://github.com/ethereum/wiki/wiki/Patricia-Tree

benchmark:

Insert | update | fetch | construct

Thanks for Robert, we find 3rd candidate here
the hat-trie
http://crpit.com/confpapers/CRPITV62Askitis.pdf

[aion-jin]

I just post the benchmark from Robert and Sergiu here:

TrieImpl (default) implementation:

Insert duration: 9667ms
Update duration: 10050ms
Read duration: 761ms
Delete duration: 7612ms

DAT implementation:

Insert duration: 6111ms
Update duration: 1862ms
Read duration: 555ms
Delete duration: 1547ms*