メルクルツリー#
問題：配列のハッシュを求める（n 個の要素）
従来の方法：各データを連結してハッシュを計算し、時間と空間の複雑度は $O (n)$
メルクルツリーを使用：経路上のハッシュのみを計算すればよく、時間と空間の複雑度は $O (logn)$；代償は総ストレージスペースが増加する（ハッシュツリーを保存する必要がある）が、依然として $O (n)$
トライ木#
接頭辞に基づいてインデックスを作成し、接頭辞が類似したデータストレージに適しています
最悪の深さは最長文字列の長さ（すなわち時間の複雑度）ですが、必ずしも二分木ではありません
接頭辞辞書の検索に適しています
メルクルパトリシアツリー#
メルクルツリーの二分木を 16 分木に変換します
親ノードは 16 個の枝のポインタを記録し、さらに自分の値を示す value フィールドを追加します
ここでのポインタは、子ノードのハッシュ値であり、逆引き検索を支援するためにkey-value DBに存在します
同時にハッシュとインデックスの 2 つの機能を担当します
16 分木は深さを減少させ -> データベースのリクエスト回数を減少させます
ロールアップの状態ツリー#
map と value を分離します
ヴァークルツリー#
KZG に基づいています
これに基づいて 16 分木を構築します