主要观点：

• “Prolly Tree”是“Probabilistic B-tree”的简称，由构建 Noms 的人员创造，DoltHub 对其工作表示尊重。
• Prolly Tree 是与 B-tree 密切相关的数据结构，在版本控制数据库的存储引擎中效果显著，具有 B-tree 类似的性能、快速的差异计算和结构共享等特性。
• 详细介绍了 Prolly Tree 的构建、修改方式，包括更新值、插入键、删除键等操作，以及其历史独立性、快速差异计算、结构共享等属性。
• 还讨论了 Dolt 中 Prolly Tree 的实现细节，如控制块大小、只考虑键、块存储的灵活性降低等，以及其在算法性能上的表现。

关键信息：

• Prolly Tree 构建步骤：排序、确定块边界、哈希每个块、判断是否完成、构建新映射并返回。
• 修改 Prolly Tree 时，更新值直接修改现有块，插入和删除键根据规则修改树并重新计算内容地址。
• Prolly Tree 的特性包括历史独立性（插入、更新、删除顺序不影响树结构）、快速差异计算（差异计算与树大小无关）、结构共享（相同内容只存储一次）。
• Dolt 中所有数据库数据都存储在 Prolly Tree 中，用于表数据、二级索引和模式存储等。

重要细节：

• 在构建 Prolly Tree 时，通过种子、当前块大小、键值和强哈希函数计算块边界，平均块大小为 4 千字节，单个字节的修改可能触发块边界的概率为 0.02%。
• 对于更新值，若值长度固定则直接修改现有块，否则需重新分块；插入键在不同位置修改树的方式不同；删除键与插入键规则相同。
• Dolt 为解决 Noms 中 Prolly Tree 的块大小问题，在决定块边界时考虑块大小，使块大小呈正态分布；只考虑键来计算内容哈希，提高更新性能。
• Dolt 的块存储为 SQL 数据库设计，类型信息存储在带外，提高读写性能；在算法性能上，Prolly Tree 读写性能与 B-tree 相似，写操作有小的性能开销，但差异计算更高效。
• 在实践中，Dolt 在标准性能测试中比 MySQL 慢约 2 倍，性能差异主要来自语言实现、SQL 分析器和数据转换等方面，但 Dolt 能计算差异并结构共享数据。