RadixDB —

一个高效的基数树，可以用作像 BTreeMap 这样的内存集合，或者用作具有自定义存储后端的原始数据库。

详细文档请见 https://docs.rs/radixdb/。

lib.rs:

基数树数据结构

基数树是一种数据结构，它能够高效且节省内存地存储具有共同前缀的键。它可以像使用单位值一样用作集合。

此基数树使用 blob 作为键和值。一个常见的用例是使用 UTF-8 字符串作为键。

此基数树的查找性能与 std::collections::BTreeMap 大致相同。

它在处理具有频繁共同前缀的长键时表现出色，例如命名空间标识符。在这种情况下，它将比存储整个键使用更少的内存。

它还会在根据前缀选择子树时非常快速，例如用于自动完成。

基数树中的元素按字典顺序排序。

基本用法

基本用法与使用 std 集合（如 BTreeMap）没有太大区别。

示例

let mut dict = RadixTree::default();
dict.insert("dog", "Hund");
dict.insert("cat", "Katze");
assert!(dict.contains_key("dog"));
for (k, v) in dict.iter() {
  println!("{:?} {:?}", k, v);
}

批量操作

RadixTree 支持批量操作。这些操作在某种程度上模仿了数据库关系操作。批量操作需要一个组合函数来指定如何处理冲突。

批量操作比逐个添加元素要快得多，特别是如果两个基数树不相交。

示例

// use the radixtree macro to create a set of strings. This works because &str implements AsRef<[u8]>.
let mut collections = radixtree! {
  "std::collections::BTreeMap",
  "std::collections::BTreeSet",
  "std::collections::HashMap",
  "std::collections::HashSet",
};
// create another set that is disjoint
let formatting = radixtree! {
  "std::fmt::Debug",
  "std::fmt::Display",
};
// in place union of the two sets
let mut all = collections;
all.outer_combine_with(&formatting, |a, b| {});
// find identifiers, e.g. for autocompletion
for (k, _) in all.scan_prefix("std::c") {
  println!("{:?}", k);
}

使用自定义 blob 存储

您可以为基数树提供一个自定义存储，这可以是内存中连续的切片，磁盘上的文件，或自定义存储后端。自定义存储后端是通过使用 custom-storage 功能启用的。

存储通常是不可靠的，例如从磁盘或网络读取时。当使用不可靠的存储时，与基数树的每次交互都可能失败。因此，所有方法都有一个不可靠版本。

示例

// build a small tree as above
let mut dict = RadixTree::default();
dict.insert("dog", "Hund");
dict.insert("cat", "Katze");
// attach it to a store - here we use a memstore, but typically you would use a file store
let store = store::MemStore::default();
let mut dict = dict.try_attached(store.clone())?;
// the store is fallible, so we have to use the try_... variants for interacting with it
assert!(dict.try_contains_key("cat")?);
for r in dict.try_iter() {
  if let Ok((k, v)) = r {
    println!("{:?} {:?}", k, v);
  }
}
// add another entry. This is now in memory
dict.try_insert("rabbit", "Hase")?;
// persist all changes to the store
dict.try_reattach()?;
// sync the store to disk
store.sync()?;

数据格式

基数树可以非常快速地进行序列化和反序列化。使用自定义存储，它们也可以在不进行反序列化的情况下进行遍历和查询。这对于查询不适合内存的非常大的树非常有用。

序列化格式

每个树节点由前缀、可选值和可选子节点组成。对于有效的节点，必须定义值或子节点。根节点允许空前缀。前缀和值可以直接或通过id间接存储。子节点目前只能通过id存储。

前缀、值和子节点分别以一个头部字节开头，后面跟着最多127个值字节。

头部字节格式

头部字节最高位用于区分内联值（0）和id值（1）。低7位是长度。

长度为0的id用作None的特殊值。这仅适用于值和子节点。同样，长度为0的数据用于存储空数组。

由于最长可能的长度为127，超过127字节的必须始终间接存储。

前缀值

当前缀间接存储时，使用额外的字节来存储前缀的第一个字节。

示例

最简单的节点

{ "" => "" }

000080
00    | prefix: 0 byte long literal ""
  00  | value: 0 byte long literal ""
    80| children: None

小型叶子节点

小型值存储在内联

{ "hello" => "world" }

0568656c6c6f06776f726c642180
0568656c6c6f                | prefix: 5 byte long literal "hello"
            06776f726c6421  | value: 6 byte long literal "world!"
                          80| children: None

大型叶子节点

超过127字节的值必须间接存储。前缀的第一个字节被附加到id上以简化搜索。对于值，只存储id。

在这种情况下，id长度为8字节，但具体细节取决于存储。例如，使用内容寻址的存储可能使用32字节的加密哈希。

{ [b'a'; 256] => [b'b'; 256] }

8961000000000000000188000000000000000280
89610000000000000001                    | prefix: first char b"a", 8 byte long id
                    880000000000000002  | value: 8 byte long id
                                      80| no children

分支节点

对于分支节点，子节点总是间接存储。添加一个记录大小字节以简化索引。记录大小设置为

{ "aa" => "", "ab" => "" }

01618089040000000000000001
8161                      | prefix: 1 byte long literal "a"
    80                    | value: None
      89040000000000000001| children: constant record size 4u8, 8 byte long id

子id指向包含2个子节点的数据块。两个子节点的大小都是4字节。

0161008001620080
0161            | prefix: 1 byte long literal "a"
    00          | value: 0 byte long literal ""
      80        | children: None
        0162    | prefix: 1 byte long literal "b"
            00  | value: 0 byte long literal ""
              80| children: None