cassandra - マークル木は完全な二分木でなければなりませんか?

Question

もしそうなら、その理由は何ですか？バランスを保つためだと思いますか？しかし、それはマークル木にとってそれほど重要なのでしょうか?

Answer 1

必須ではありませんが、バランスが悪いと効率が悪くなります。発生する可能性のある問題がいくつかあります。

想定されるマークル ツリーの範囲が大きすぎて、たとえばツリーがあった場合

 a
/ \
b c
\ /
d e

次に、必要以上のハッシュを送信しています (b と c は冗長です)。

または、範囲を間違えてエンド バケットにキー範囲の大部分が含まれる場合は、次のようなツリーになります。

a
 \
 b
 /\
c  d
\  /\
 e f g

ここでは、g を作成するためにハッシュされるキーが他のバケットよりも多いため、異なる可能性が高くなります。不整合を修正するには、他のバケットよりも多くのデータをコピーする必要があります。