巴婆树

自然界中的巴婆树是树冠最宽的树。它们也能长出新根，过一段时间后可能与原根难以区分。

本库中的巴婆树是具有高分支因子（树冠宽）的持久树，可以用来高效存储和查询大量键值对序列。

巴婆树针对 追加 新条目和过滤、流式读取值进行了优化。它们自然支持通过索引访问元素。它们 不支持 元素的任意插入或删除，因此不是通用目的的映射数据结构。

它们不是平衡树，但与 B-树 具有某些属性。

持久性

巴婆树是持久的，使用诸如 ipfs 或键值存储等内容寻址存储系统。数据以 CBOR 编码，并以 zstd 进行压缩，以实现高效持久存储和复制。它还使用 chacha20 流密码进行加密。

索引

每个巴婆树条目由键部分和值部分组成。值部分是一个不透明的值，可以序列化为 cbor。这不能用于查询中的过滤。键部分可以通过定义如何从键计算汇总来高效查询。这些汇总将存储在树的较高位置，以便进行高效查询和过滤流式读取。

除了通过键内容查询外，元素还可以通过偏移量高效访问。

密封和打包

密封

一旦压缩数据超过一定大小，树的一个叶节点就被认为是 密封 的。这取决于配置和压缩率。当一个分支节点拥有一定数量（可配置）的子节点时，它就被认为是 密封 的。

打包

榕树不平衡，因为它们不需要支持任意的插入和删除。有一个与平衡相关的概念，称为填充。如果一个树除了最后一个叶子节点外都进行了填充，并且分支节点尽可能向左填充，那么这个树就被认为是填充过的。这种表示方法通常是键值对序列中最节省空间的，也是最有效的后续追加方式。

未填充的树

在每次追加单个条目或少量条目后填充树会效率低下，因为它需要为每个级别重新创建一个新的分支节点和一个叶子节点。

为了允许快速追加，可以在不进行填充的情况下添加元素。这会创建一个树链表，在添加单个元素的情况下，会形成一个类似链表的退化树。

未填充的树可以在任何时候进行填充，而不会改变内容。