マークル木(DB)
各葉がデータ範囲のハッシュ、各ノードが子のハッシュとなるハッシュ木。ハッシュを上から順に比べることで、2つのレプリカがどこで食い違うかを、全データを送らずに特定できる。
仕組み:根はデータセット全体を1つのハッシュで要約する。2つのレプリカの根ハッシュが等しければ同一であり、そこで終わる。異なれば子のハッシュを比べ、食い違った枝だけを掘り下げる。行ごとの比較ではなく、対数時間で相違範囲を突き止められる。分散データベース(Dynamo、Cassandra、Riak)ではこれがアンチエントロピーと修復の仕組みを支える。同じデータ構造はGit(コミット)、ブロックチェーン(取引の検証)、Certificate Transparency、IPFSなど、大きなデータセットを効率よく検証・比較したい場面で広く使われている。分散システムで最も応用範囲の広いデータ構造の一つである。アンチエントロピーやコンシステントハッシングと関連する。