Rust中的B𝛆树库

这是对Dan Hulme的b𝛆-tree实现的移植。由于他在GitHub上似乎不活跃且没有继续维护该库，所以我进行了移植。

以下介绍来自原始版本。感谢Dan！

这是目标。这个项目最初是在Rust meetups上的“集体编程”实验中开始的。在聚会上，我们没有实现普通的B-tree，但这是一个起点，自从聚会以来，我做了一些进一步的修改。

想法是实现这篇2015年的论文中的B𝛆树数据结构。这是对B-tree的改进，以提高写入速度（以查询速度的某些损失为代价）。不是立即将更改推送到相关的叶节点，而是每个分支节点包含一个（持久）命令队列来缓冲更改。因此，从磁盘加载子节点的成本在多个操作中分摊。

不幸的是，查询没有更快（并且稍微慢一些，因为它们需要读取命令队列）。需要读取现有值然后更新它的操作仍然会很慢。作者添加了一个额外的操作upsert，它读取值（如果有），对其应用操作，然后写入修改后的值。upsert可以像插入一样存储到命令队列中，因此它们可以获得与插入相同的表现优势。

替代方案

• 相同数据结构的C++实现，2-clause BSD许可证

贡献者

聚会中“集体”的每个成员都应该列入贡献者名单。如果你是其中之一，请发送一个拉取请求，将你的名字添加到列表中。

• Dan Hulme [email protected]

联系

Chojan Shang - @PsiACE - [email protected]

项目链接：https://github.com/psiace/be-tree

许可证

以下任一许可证下授权

• Apache许可证2.0版本 (LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
• MIT许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)