Riak，merkle树，实现

Question

有人能给我解释一下在riak-core中merkle树的实现是如何工作的吗？

https://github.com/basho/riak_core/blob/develop/src/merkerl.erl

例如，我不明白它是什么偏移量。

谢谢!

Answer 1

该树或多或少是一棵K/V查找树和Merkle树。该树是通过查看160位sha1散列来定义的。160位表示20个字节。在树的第一层，我们根据散列的第0个字节存储最多256个子树。在下一级，它是第一个字节，然后是第二个字节，依此类推。

这是一种称为数字树方案，其中散列中的数字编码要在树中采用的路径。这允许我们替换树中的数据。或者，查找concept trie。同时，我们用sha1标记每个节点的孩子，以跟踪给定子树中的变化。当运行查找diff时，我们可以忽略具有相同签名的子树，因为它们必须通过构造等价。

值offset编码了我们当前在160位密钥中的距离。offset_key/1函数将偏移到要查看的键中的右侧字节。