btree

一个 持久化按写复制 B+Tree 实现，设计为键值存储的索引，灵感来自 SQLite。

设计

每个 BTree 结构与一个文件关联，该文件包含其节点在预定义结构中的信息。 BTree API 以按写复制的方式实现，即在每次写入或删除时都会创建新节点的副本，而不会修改树的前一个版本。为了跟踪树的最新版本，我们维护一个写前日志来记录当前根节点。

单元测试作为API使用的有用示例。

磁盘节点结构

有两种 NodeType 变体 - Internal 和 Leaf；每种变体在磁盘上都有自己的预定义结构。一个叶子节点的结构如下

| IS-ROOT 1-byte| NODE-TYPE 1-byte | PARENT OFFSET - 8 bytes | Number of pairs - 8 bytes |
| Key #0 - 10 bytes | Value #0 - 10 bytes | ...
| Key #N - 10 bytes | Value #N - 10 bytes |

而磁盘内部节点的结构如下

| IS-ROOT 1-byte | NODE-TYPE 1-byte | PARENT OFFSET - 8 bytes | Number of children - 8 bytes |
| Key #0 - 10 bytes | Key #2 - 10 bytes | ...
| Child Offset #0 - 8 bytes | Child offset #1 - 8 bytes | ...

特性

• 支持所有 CRUD 操作（读取、写入、删除）。
• 支持从磁盘崩溃恢复。
• 支持可变长度的键值对。
• 键压缩。
• 垃圾收集。

API

从磁盘到内存和返回

节点通过 TryFrom 方法映射到磁盘上的页面，以简化节点到页面和返回的序列化/反序列化。

let some_leaf = Node::new(
   NodeType::Leaf(vec![
         KeyValuePair::new("foo".to_string(), "bar".to_string()),
         KeyValuePair::new("lebron".to_string(), "james".to_string()),
         KeyValuePair::new("ariana".to_string(), "grande".to_string()),
   ]),
   true,
   None,
);

// Serialize data.
let page = Page::try_from(&some_leaf)?;
// Deserialize back the page.
let res = Node::try_from(page)?;

请参阅 src/page.rs 和 src/node.rs 中的测试以获取更多信息。

写入和读取键值对。

// Initialize a new BTree;
// The BTree nodes are stored in file '/tmp/db' (created if does not exist)
// with parameter b=2.
 let mut btree = BTreeBuilder::new()
            .path(Path::new("/tmp/db"))
            .b_parameter(2)
            .build()?;

// Write some data.
btree.insert(KeyValuePair::new("a".to_string(), "shalom".to_string()))?;
btree.insert(KeyValuePair::new("b".to_string(), "hello".to_string()))?;
btree.insert(KeyValuePair::new("c".to_string(), "marhaba".to_string()))?;

// Read it back.
let mut kv = btree.search("b".to_string())?;
assert_eq!(kv.key, "b");
assert_eq!(kv.value, "hello");

kv = btree.search("c".to_string())?;
assert_eq!(kv.key, "c");
assert_eq!(kv.value, "marhaba");

删除键值对。

// Initialize a new BTree.
let mut btree = BTreeBuilder::new()
      .path(Path::new("/tmp/db"))
      .b_parameter(2)
      .build()?;

// Write some data.
btree.insert(KeyValuePair::new("d".to_string(), "olah".to_string()))?;
btree.insert(KeyValuePair::new("e".to_string(), "salam".to_string()))?;
btree.insert(KeyValuePair::new("f".to_string(), "hallo".to_string()))?;
btree.insert(KeyValuePair::new("a".to_string(), "shalom".to_string()))?;
btree.insert(KeyValuePair::new("b".to_string(), "hello".to_string()))?;
btree.insert(KeyValuePair::new("c".to_string(), "marhaba".to_string()))?;

// Find the key.
let kv = btree.search("c".to_string())?;
assert_eq!(kv.key, "c");
assert_eq!(kv.value, "marhaba");

// Delete the key.
btree.delete(Key("c".to_string()))?;

// Sanity check.
let res = btree.search("c".to_string());
assert!(matches!(
      res,
      Err(Error::KeyNotFound)
));

许可证

MIT。