概率 B 树 (Probabilistic B-Tree) —— 结合 B-Tree 的高效查询与 Merkle Tree 的内容寻址,实现「数据版本控制」的核心数据结构
添加和删除键值对,观察 Prolly Tree 如何自动构建和重新组织节点。每个节点显示其包含的键和 Merkle 哈希值。
这是 Prolly Tree 最神奇的特性:相同的数据集,无论以何种顺序插入,总会产生完全相同的树结构。 下面我们用两种不同的插入顺序构建树,然后比较它们的根哈希。
对比两棵包含大量数据的 Prolly Tree 时,从根节点开始逐层比较哈希值。 哈希相同的子树直接跳过(绿色),只需深入检查哈希不同的路径(红色)。 操作:仅将 orange(橙子)修改为 orange(血橙)—— 一个极小的局部改动。
Prolly Tree 的核心机制:对每个已排序的条目计算哈希值,当哈希值的最低若干位满足特定模式时,标记为块边界。 这种内容定义分块 (Content-Defined Chunking) 确保了边界仅取决于数据内容,而非位置或插入顺序。 调整「目标位数」观察不同参数对分块粒度的影响。
点击「开始动画」,观察算法如何逐个处理已排序的条目:计算哈希 → 检查低位 → 判定是否切分。
每个条目下方显示其哈希值的低位。标记 ✂️ 的位置表示命中了边界条件,在此处切分。不同颜色的底边代表不同的块。