Markle Partricia Tree

key, valueの帳簿を保存するのに使用できる

全く同じKVの帳簿を持ったPatricia treeは最後のバイトに至るまで正確に同じ

roothash

O(log n)での計算での挿入、検索、削除

radix tree

(value, i0, i1 ... in)

i0...inはアルファベットの記号列

アルファベット単体がノードへのパスとなる値

iのはNull/別ノードへのポインタ

valueはその値

例：dog

dog -> 0x646f67

root -> 6 -> 4 -> 6 -> f -> 6 -> 7というパスをたどり、ノードの値を参照する

trieにおけるroot hashが公

あるvalueが与えられたときに、あるkeyが特定される

valueからのパスをたどっていくことで、rootにたどり着いたときkeyが何であるかを提供できる