rust mem_btree

使用 Rust 实现的 BTree 数据结构，支持快照功能。不使用任何不安全库。

https://crates.io/crates/mem_btree

设计

尽管 Rust 官方提供了 BTreeMap 库。但这个库不能实现写时复制/读操作，也不能实现快照，尽管你可以用 clone 代替，但 clone 的成本太高，所以这个项目通过一个非常简单的方式实现了 BTree 结构的快照。主要思路是使用 Arc 进行自由分配，然后在写的过程中，复制所有路径节点，尽管这会导致插入速度变慢。但与内存操作的慢速相比，也是有限的慢。

未来

• 快照 ✅
• 分割 ✅
• 插入 ✅
• 删除 ✅
• 获取 ✅
• 搜索 ✅
• 前一个搜索 ✅
• 前一个迭代器 ✅
• 下一个迭代器 ✅
• 批量写入 ✅
• ttl ✅

基准测试

5k kv 插入

btree insert 120.064954ms
btreemap insert 73.882981ms
btreemap_arc insert 79.869725ms

btree get 102.721024ms
btreemap get 100.939223ms
btreemap_arc get 100.255662ms

btree clone 759ns
btreemap clone 453.955778ms
btreemap_arc clone 24.776548ms