Bonzai

Rust 的出色性能部分来源于其默认就地存储数据，这提高了空间局部性，从而使得 CPU 缓存性能更佳。然而，树结构往往无法享受到这一好处。树是递归结构，因此需要使用某种间接形式。人们通常默认使用 Box，因为它与普通拥有数据的所有权语义相同。然而，它有可能将数据散布在堆的各个角落，从而破坏空间局部性。

解决此问题的技术之一是将树节点存储在连续的 Vec 中，并用索引连接它们。最直接的方法是以高度耦合于树本身逻辑的方式实现索引逻辑。不幸的是，这种方法在允许的错误和产生的技术复杂性方面与处理原始指针非常相似。

Bonzai 是一个安全的、零成本的树抽象，它将节点存储在连续的 Vec 中。Bonzai 使用不安全代码创建一个安全的抽象，利用借用检查器验证树操作的合法性，同时使用极少的堆分配。

功能

• 完全安全的接口
• 最小的运行时成本
• 改进的指针别名
• 对树不同部分的多个同时可变引用
• 从节点到其父节点遍历
• 分离子树，将其重新连接到其他位置
• 节点压缩和内存足迹重新缩小
• 如果元素是，树则是 Send 和 Sync
• 编译时泛型化分支因子
• 通过 Debug 特性打印树

目前不支持

• 多线程修改
• 在稳定发布频道上使用
• 无界/动态分支因子
• 分离子树的双向遍历

示例，性能测试

GitHub 上的 bonzai-nbst 仓库是一个 Rust 可执行文件，其中包含一个简单的二叉搜索树（无平衡）的实现，一个使用 Bonzai，另一个使用堆分配。 基于 Bonzai 的实现。

我在Windows 10笔记本电脑上，使用1000万次随机树操作测试了两种实现。为了在一个实际使用混沌堆的场景中测试，我将它插入到magogroguelike（我与此无关）的一个分支中，这样它们可以在同一个进程中运行。虽然这个测试非常不科学，但bonzai展示了明显的性能提升。

• bonzai: 15,786 ms
• boxes: 21,338 ms

Tree

Tree，以及从树中借用的大多数组件，对两种类型是通用的：元素类型，以及ChildId的固定大小数组。元素类型T存储在树中的每个节点上。每个节点可以拥有任何组合的子节点，任何子节点索引都是ChildId数组的有效索引。

例如，一个二叉搜索树集合i32可以表示为一个Tree<i32, [ChildId; 2]>。

TreeOperation

TreeOperation是一种类型，它从Tree借用可变引用，并允许修改该树。当存在TreeOperation时，对树的访问只能是单线程的。这允许许多操作通过只对TreeOperation的不可变引用（直接或间接）进行修改来修改树。

NodeOwnedGuard

通常，树中的一个节点归其父节点所有。根节点具有特殊状态，其父节点被视为根。然而，在TreeOperation的生命周期内，一个子树可以与其父节点分离，并且它可以被认为是由NodeOwnedGuard拥有的。在这种情况下，NodeOwnedGuard可以比其父节点的保护器存在时间更长。这个子树可以作为另一个节点的子节点重新附加到主树。在NodeOwnedGuard的生命周期内，可以像它是主树的一部分一样对其进行修改。或者，可以将NodeOwnedGuard转换为它的内部元素，标记节点及其所有子节点为垃圾。

当NodeOwnedGuard被丢弃，并且其子树被标记为垃圾时，元素的析构函数将在NodeOwnedGuard的丢弃和TreeOperation的丢弃之间运行。

NodeWriteGuard

NodeWriteGuard是一种类型，它持有一个子树（一个节点及其所有子节点，递归）的可变访问权。可以将NodeWriteGuard同时借用到一个元素的可变引用（&mut T）和一个ChildWriteGuard。具有改变节点子节点的能力的ChildWriteGuard。此外，可以将NodeWriteGuard转换为NodeOwnedGuard，断开受保护的子树。

NodeWriteGuard不能比父节点保护器（如果节点是根节点，则不能比树）存在时间更长。

ChildWriteGuard

一个 ChildWriteGuard 代表了对节点子节点可变访问。它可以从 NodeWriteGuard 和 NodeOwnedGuard 中借用。ChildWriteGuard 可以将其中的一个 NodeWriteGuard 借给子节点，甚至可以同时借给几个不同的子节点。此外，ChildWriteGuard 可以将一个元素作为特定的子节点（标记任何先前的子节点子树为垃圾），甚至可以将整个已分离的子树（一个 NodeOwnedGuard）作为其子节点之一。

TreeWriteTraverser

当一个 NodeWriteGuard 保持对子树（节点及其子节点，递归地）的可变访问时，一个 TreeWriteTraverser 保持对整个树的可变访问。这允许 TreeWriteTraverser 寻找父节点，这是 NodeWriteGuard 所不能做到的。然而，这也意味着 TreeWriteTraverser 不能与其他任何守卫同时存在。

除了这个差异之外，TreeWriteTraverser 可以像 NodeWriteGuard 一样使用。甚至可以将 TreeWriteTraverser 转换或可变借用为 NodeWriteGuard。

可以使用 traverse_from! 宏将 TreeOperation 和某种类型的节点守卫方便地转换为 TreeWriteTraverser。

NodeReadGuard

NodeReadGuard 是一个类型，它持有一个树子集的不可变访问。由于 NodeReadGuard 不进行可变借用，因此它不需要拆分为 ChildWriteGuard 和 &mut T。相反，NodeReadGuard 以不可变方式解引用到 T，并且其子节点可以直接使用方法访问。

TreeReadTraverser

TreeReadTraverser 对于 NodeReadGuard，就像 TreeWriteTraverser 对于 NodeWriteGuard。当 NodeReadGuard 保持对树子集的不可变访问时，TreeReadTraverser 保持对整个树的不可变访问。这允许 TreeReadTraverser 安全地遍历到其父节点。