rax - 基数树

基数树的特点是它与哈希表类似，但也可以像B树一样排序。这个特定的实现实现了一些高级功能，比如前缀压缩，这使得这个结构比哈希表和通常的B树都要节省内存。

它在压力下，特别是在有许多常见用例条目的情况下，显著优于std::collections::HashMap / BTreeMap / HashSet / BTreeSet。效果可能会有所不同，所以请自行测试并报告结果。

完整规范可以在下面的使用示例下方找到。

查看另一个Redis工程宝石

listpack "Packed List Structure" 用于Redis，已引入Rust

用法

extern crate libc;
extern crate rax;

use libc;
use rax;
use rax::{RaxMap, RaxSet};

fn main() {
    // Optionally use different memory allocator
    // Internally defaults to malloc in libc.
    patch_allocator();
    
    let mut r = RaxMap::<&str, &str>::new();
    
    // Also have a "Set" version with no memory
    // cost with storing value pointers.
    //let mut set = RaxSet::<&str>::new();

    // Values must be boxed since the internal Rax
    // stores data pointers. However, keys are
    // fully represented in a compressed format
    // within the Rax so those can be stack allocated.
    r.insert(
        "romane",
        Box::new("romane it!"),
    ).expect("whoops!");
    r.insert(
        "romanus",
        Box::new("romanus it!"),
    ).expect("whoops!");
    r.insert(
        "romulus",
        Box::new("romulus it!"),
    ).expect("whoops!");
    r.insert(
        "rubens",
        Box::new("rubens it!"),
    ).expect("whoops!");
    r.insert(
        "ruber",
        Box::new("ruber it!"),
    ).expect("whoops!");
    r.insert(
        "rubicon",
        Box::new("rubicon it!"),
    ).expect("whoops!");
    r.insert(
        "rubicundus",
        Box::new("rubicundus it!"),
    ).expect("whoops!");

    match r.get("rubens") {
        Some(v) => println!("Found {}", v),
        None => println!("Not Found")
    }

    // Full featured iterator / cursor with seek
    // and going forwards or backwards.
    r.iter(|_, iter| {
        if !iter.seek_min() {
            return;
        }
        while iter.forward() {
            println!("{}", iter.key());
        }
        if !iter.seek_max() {
            return;
        }
        while iter.back() {
            println!("{}", iter.key());
        }
    });
    
    // Print the tree as ASCII art
    r.show();
}

fn patch_allocator() {
    // Can hook memory allocator to control the internal heap allocations.
    // All memory is reclaimed when rax leaves scope automatically
    // through the Drop trait.
    unsafe {
        rax::set_allocator(
            rax_malloc_hook,
            rax_realloc_hook,
            rax_free_hook,
        );
    }
}

extern "C" fn rax_malloc_hook(size: libc::size_t) -> *mut u8 {
    unsafe {
        println!("malloc");
        libc::malloc(size) as *mut u8
    }
}

extern "C" fn rax_realloc_hook(ptr: *mut libc::c_void, size: libc::size_t) -> *mut u8 {
    unsafe {
        println!("realloc");
        libc::realloc(ptr, size) as *mut u8
    }
}

extern "C" fn rax_free_hook(ptr: *mut libc::c_void) {
    unsafe {
        println!("free");
        libc::free(ptr)
    }
}

Rax，ANSI C基数树实现

Rax最初是为了解决Redis中特定位置的性能问题而编写的基数树实现，但很快就将其转换为独立项目，以便在Redis本身之外，以及在其他项目中重用。

主要目标是找到性能和内存使用之间的适当平衡，同时提供一个功能齐全的基数树实现，可以满足许多不同的要求。

在开发这个库的过程中，当我越来越兴奋地看到基数树的实际应用性和适用性时，我非常惊讶地看到编写健壮的实现有多难，特别是对于具有灵活迭代器的完整功能的基数树。在节点分割、合并和各种边缘情况中可能出错的地方很多。因此，项目的重大目标是提供一个稳定且经过实战考验的实现，供人们使用并分享错误修复。该项目大量依赖模糊测试技术，以探索项目所包含的所有代码行，以及大量可能的状况。

Rax是一个开源项目，在BSD双条款许可证下发布。

主要功能

• 内存感知
  • 打包节点表示。
  • 如果键设置为NULL，则可以避免在节点中存储NULL指针（节点标题中有isnull位）。
  • 没有父节点引用。在需要时使用堆栈。
• 快速查找
  • 边在父节点中以字节数组的形式直接存储，在尝试查找匹配项时无需访问无用的子节点。这与其他实现相比意味着缓存未命中更少。
  • 通过将边存储为两个分离的数组（一个边字符数组和一个边指针数组）来对正确的子节点进行缓存行友好的扫描。
• 完整实现
  • 根据需要重新压缩节点的删除。
  • 迭代器（包括在树修改时使用迭代器的方法）。
  • 随机游走迭代。
  • 能够报告并抵抗内存不足：如果malloc()返回NULL，API可以报告内存不足错误，并始终使树保持一致状态。
• 可读且可修复的实现
  • 所有复杂部分都带有算法细节的注释。
  • 可以启用调试消息来理解在调用给定函数时实现正在做什么。
  • 可以打印基数树节点表示的ASCII艺术。
• 可移植实现
  • 从不执行内存未对齐的访问。
  • 使用ANSI C99编写，不使用扩展。
• 使用模糊测试进行广泛的代码和可能状态测试覆盖率。
  • 测试在很大程度上依赖于模糊测试，以探索非平凡状态。
  • 与简单的哈希表和排序数组的等效行为实现相比，实现了字典和迭代器的实现，生成随机数据并检查两种实现的结果是否匹配。
  • 内存不足条件测试。实现使用一个特殊的分配器模糊测试，该分配器在随机时返回NULL。对生成的基数树进行一致性测试。Redis，这是该实现的主要目标，不使用此功能，但处理OOM的能力可以使此实现适用于需要生存OOM的场景。
  • Redis的一部分：该实现在实际应用中承受了显著的压力。

节点布局如下。在示例中，表示键的节点（因此有一个相关联的数据指针）有三个子节点 x、y、z。图中的每个空间代表一个字节。

+----+---+--------+--------+--------+--------+
|HDR |xyz| x-ptr  | y-ptr  | z-ptr  |dataptr |
+----+---+--------+--------+--------+--------+

头 HDR 实际上是一个位字段，具有以下字段

uint32_t iskey:1;     /* Does this node contain a key? */
uint32_t isnull:1;    /* Associated value is NULL (don't store it). */
uint32_t iscompr:1;   /* Node is compressed. */
uint32_t size:29;     /* Number of children, or compressed string len. */

压缩节点代表不是键且恰好有一个子节点的节点链，因此而不是存储

A -> B -> C -> [some other node]

我们以以下形式存储压缩节点

"ABC" -> [some other node]

压缩节点的布局是

+----+---+--------+
|HDR |ABC|chld-ptr|
+----+---+--------+

基本API

基本API是一个平凡的字典，你可以添加或删除元素。唯一的显著区别是，插入和删除API还接受一个可选参数，以便在更新（在插入时）或删除时通过引用返回存储在键中的旧值。

创建基数树并添加键

使用以下方法创建新的基数树

rax *rt = raxNew();

为了插入新键，使用以下函数

int raxInsert(rax *rax, unsigned char *s, size_t len, void *data,
              void **old);

示例用法

raxInsert(rt,(unsigned char*)"mykey",5,some_void_value,NULL);

如果键正确插入，函数返回1，或者如果键已在基数树中，返回0：在这种情况下，值被更新。在内存不足的情况下也返回0，但是在这种情况下，将 errno 设置为 ENOMEM。

如果相关联的值 data 为NULL，则存储键的节点不使用额外的内存来存储NULL值，因此如果使用NULL作为关联值，仅由键组成的字典在内存使用上是高效的。

请注意，键是无符号字符数组，您需要指定其长度：Rax是二进制安全的，因此键可以是任何内容。

还有一个不覆盖现有键值的插入函数变体

int raxTryInsert(rax *rax, unsigned char *s, size_t len, void *data,
                 void **old);

该函数与raxInsert()完全相同，但是如果在键存在的情况下函数返回0（与raxInsert相同），则不修改旧值。旧值仍然可以通过通过引用返回的'old'指针返回。

键查找

查找函数如下

void *raxFind(rax *rax, unsigned char *s, size_t len);

此函数在要访问的键不存在时返回特殊值 raxNotFound，因此示例用法如下：

void *data = raxFind(rax,mykey,mykey_len);
if (data == raxNotFound) return;
printf("Key value is %p\n", data);

raxFind() 是只读函数，因此不可能发生内存不足的情况，该函数永远不会失败。

删除键

删除键正如您所想象的那样，但具有通过引用返回即将删除的键的关联值的权限

int raxRemove(rax *rax, unsigned char *s, size_t len, void **old);

如果成功找到并删除键，该函数返回 1，如果键不存在，则返回 0。此函数也不会因内存不足而失败。然而，如果在删除键时发生内存不足的情况，则即使可能，结果树节点也可能不会重新压缩：在这种情况下，基数树可能不太高效地编码。

old 参数是可选的，如果提供，将在函数成功找到并删除键时设置为关联键的值。

迭代器

Rax 键空间按字典顺序排序，使用组成键的字节值来决定两个键之间哪个键更大。如果前缀相同，则较长的键被视为更大。

Rax 迭代器允许根据不同的运算符查找给定元素，然后通过调用 raxNext() 和 raxPrev() 来导航键空间。

基本迭代器使用

迭代器通常作为在栈上分配的局部变量声明，然后使用 raxStart 函数初始化

raxIterator iter;
raxStart(&iter, rt); // Note that 'rt' is the radix tree pointer.

raxStart 函数永远不会失败且不返回任何值。一旦初始化迭代器，就可以将其定位（定位是过去的“seek”，而不是“seeked”，以防您想知道）以从指定位置开始迭代。为此目的，使用 raxSeek 函数

int raxSeek(raxIterator *it, unsigned char *ele, size_t len, const char *op);

例如，可能想要定位第一个大于或等于键 "foo" 的元素

raxSeek(&iter,">=",(unsigned char*)"foo",3);

raxSeek() 函数在成功时返回 1，在失败时返回 0。可能的失败包括：

1. 传递了无效的运算符作为最后一个参数。
2. 在定位迭代器时发生内存不足的情况。

一旦定位迭代器，就可以使用 raxNext 和 raxPrev 函数进行迭代，如下例所示

while(raxNext(&iter)) {
    printf("Key: %.*s\n", (int)iter.key_len, (char*)iter.key);
}

raxNext 函数从 raxSeek 定位的元素开始返回元素，直到树的最后一个元素。如果没有更多元素，则返回 0，否则函数返回 1。然而，当发生内存不足的情况时，函数也可能返回 0：虽然它试图始终使用栈，但如果树深度很大或键很大，则迭代器开始使用堆分配的内存。

raxPrev 函数以完全相同的方式工作，但会移动到基数树的第一元素而不是移动到最后一个元素。

释放迭代器

迭代器可以多次使用，并且可以使用 raxSeek 重新定位，而无需再次调用 raxStart。然而，当迭代器不再使用时，必须使用以下调用回收其内存：

raxStop(&iter);

请注意，即使您没有调用 raxStop，大多数情况下您也不会检测到任何内存泄漏，但这只是 Rax 实现工作方式的副作用：大多数情况下它会尝试使用栈分配的数据结构。然而，对于深层树或大型键，将分配堆内存，而未能调用 raxStop 将导致内存泄漏。

查找操作符

raxSeek 函数可以根据操作符查找不同的元素。例如，在上面的示例中，我们使用了以下调用：

raxSeek(&iter,">=",(unsigned char*)"foo",3);

为了查找第一个元素 >= 到字符串 "foo"。然而，其他操作符也是可用的。第一组操作符相当明显：

• == 查找与给定元素完全相同的元素。
• > 查找大于给定元素的最小元素。
• >= 查找等于或大于给定元素的最小元素。
• < 查找小于给定元素的最小元素。
• <= 查找等于或小于给定元素的最小元素。
• ^ 查找基数树的第一个元素。
• $ 查找基数树的最后一个元素。

当使用最后两个操作符 ^ 或 $ 时，传递的键和键长度参数完全被忽略，因为它们与这些操作符无关。

请注意，在某些情况下查找是不可能的，例如当基数树不包含元素或当请求的查找不可能时，如下所示：

raxSeek(&iter,">",(unsigned char*)"zzzzz",5);

我们可能没有任何大于 "zzzzz" 的元素。在这种情况下，当第一次调用 raxNext 或 raxPrev 时，将简单地返回零，因此不会遍历任何元素。

迭代器停止条件

有时我们想要迭代特定的范围，例如从 AAA 到 BBB。为了做到这一点，我们可以查找并获取下一个元素。然而，一旦返回的键大于 BBB，我们则需要停止。Rax 库提供了 raxCompare 函数，以避免您需要根据精确的迭代重复编写相同的字符串比较函数。

raxIterator iter;
raxStart(&iter);
raxSeek(&iter,">=",(unsigned char*)"AAA",3); // Seek the first element
while(raxNext(&iter)) {
    if (raxCompare(&iter,">",(unsigned char*)"BBB",3)) break;
    printf("Current key: %.*s\n", (int)iter.key_len,(char*)iter.key);
}
raxStop(&iter);

上面的代码显示了完整的范围迭代器，它只是打印通过迭代遍历的键。

raxCompare 函数的原型如下：

int raxCompare(raxIterator *iter, const char *op, unsigned char *key, size_t key_len);

支持的操作符是 >、>=、<、<=、==。如果当前迭代器键满足与提供的键比较的操作符，则函数返回 1，否则返回 0。

检查迭代器 EOF 条件

有时在调用 raxNext() 或 raxPrev() 之前，我们想知道迭代器是否处于 EOF 状态。迭代器 EOF 条件发生在没有更多元素可以通过 raxNext() 或 raxPrev() 调用来返回时，这可能是因为 raxSeek() 未能查找请求的元素，或者因为在使用 raxPrev() 和 raxNext() 调用导航树时到达了 EOF。

可以使用以下函数测试此条件，该函数在到达 EOF 时返回 1：

int raxEOF(raxIterator *it);

在迭代过程中修改基数树

为了提高效率，Rax 迭代器缓存了当前位置的确切节点，这样在下次迭代步骤中，它可以从上次停止的地方继续。然而，迭代器具有足够的状态，以便在缓存节点指针不再有效时重新定位。这个问题发生在我们希望在迭代过程中修改基数树时。一个常见的模式是，例如，删除所有匹配给定条件的元素。

幸运的是，有一个非常简单的方法来做这件事，并且效率成本只在需要时支付，也就是说，只有在树实际被修改时才支付。解决方案包括在树被修改后，使用当前键重新定位迭代器，如下例所示：

while(raxNext(&iter,...)) {
    if (raxRemove(rax,...)) {
        raxSeek(&iter,">",iter.key,iter.key_size);
    }
}

在上面的例子中，我们使用 raxNext 进行迭代，因此我们正在向字典序更大的元素前进。每次我们删除一个元素，我们需要做的就是使用当前元素和 > 查找操作符再次查找它：这样我们就会移动到具有表示当前基数树（在更改之后）的新状态的新元素。

这个想法可以在不同的上下文中使用，考虑到以下：

• 在迭代过程中，每次添加或删除键时，都需要使用 raxSeek 重新定位迭代器。
• 当前的迭代器键始终可以通过 iter.key_size 和 iter.key 访问，即使在它从基数树中被删除后也是如此。

在 EOF 后重新定位迭代器

当迭代达到 EOF 条件时，因为没有更多元素可以返回，因为我们到达了基数树的任一端，EOF 条件是永久的，即使在反向迭代中也不会产生任何结果。

继续迭代的简单方法，简单地从迭代器返回的最后一个元素开始，就是重新定位它自己。

raxSeek(&iter,iter.key,iter.key_len,"==");

因此，例如，要编写一个命令，该命令从第一个到最后一个打印基数树的所有元素，然后再次从最后到第一个重新使用相同的迭代器，可以使用以下方法：

raxSeek(&iter,"^",NULL,0);
while(raxNext(&iter,NULL,0,NULL))
    printf("%.*s\n", (int)iter.key_len, (char*)iter.key);

raxSeek(&iter,"==",iter.key,iter.key_len);
while(raxPrev(&iter,NULL,0,NULL))
    printf("%.*s\n", (int)iter.key_len, (char*)iter.key);

随机元素选择

要从基数树中提取一个公平的元素，使得每个元素都有相同的概率被返回，如果要求以下条件，这是不可能的：

1. 基数树不大于预期（例如，通过允许元素排序的信息进行增强）。
2. 我们希望操作快速，最坏情况下是对数时间（因此，像蓄水池抽样这样的方法就不适用，因为它是 O(N)）。

然而，足够长的随机游走，在几乎平衡的树中，会产生可接受的结果，这是快速的，并且最终返回每个可能元素，即使不是以正确的概率。

要执行随机游走，只需在任何地方定位一个迭代器并调用以下函数：

int raxRandomWalk(raxIterator *it, size_t steps);

如果将步数设置为 0，该函数将在 1 和树中元素数量的两倍以 2 为底的对数之间执行随机游走步数，这通常足以得到一个不错的结果。否则，您可以指定要采取的确切步数。

打印树

出于调试或教育目的，可以使用以下调用来获取基数树及其组成的节点的 ASCII 艺术表示：

raxShow(mytree);

然而请注意，这对于具有少量元素的树来说效果很好，但对于非常大的树来说就很难阅读了。

以下是在添加指定的键和值后，raxShow() 生成的输出示例：

• alligator = (nil)
• alien = 0x1
• 气球 = 0x2
• 动力学 = 0x3
• 罗马 = 0x4
• 罗马努斯 = 0x5
• 罗穆卢斯 = 0x6
• 鲁本 = 0x7
• 鲁伯 = 0x8
• 鲁比孔河 = 0x9
• 鲁比库德努斯 = 0xa
• 所有 = 0xb
• 鲁伯 = 0xc
• 巴 = 0xd

[abcr]
 `-(a) [l] -> [il]
               `-(i) "en" -> []=0x1
               `-(l) "igator"=0xb -> []=(nil)
 `-(b) [a] -> "loon"=0xd -> []=0x2
 `-(c) "hromodynamic" -> []=0x3
 `-(r) [ou]
        `-(o) [m] -> [au]
                      `-(a) [n] -> [eu]
                                    `-(e) []=0x4
                                    `-(u) [s] -> []=0x5
                      `-(u) "lus" -> []=0x6
        `-(u) [b] -> [ei]=0xc
                      `-(e) [nr]
                             `-(n) [s] -> []=0x7
                             `-(r) []=0x8
                      `-(i) [c] -> [ou]
                                    `-(o) [n] -> []=0x9
                                    `-(u) "ndus" -> []=0xa

运行 Rax 测试

要运行测试，尝试

$ make
$ ./rax-test

运行基准测试

$ make
$ ./rax-test --bench

在 OOM 条件下测试 Rax

$ make
$ ./rax-oom-test

最后一个目前非常冗长。

为了使用 Valgrind 进行测试，只需使用它运行测试即可，但如果您想要准确检测内存泄漏，请让 Valgrind 运行整个测试，因为如果您提前停止它，它会检测到大量的假阳性内存泄漏。这是由于 Rax 在未对齐地址上使用 memcpy 放置指针，因此 Valgrind 检测泄漏的位置并不明显。然而，在测试结束时，Valgrind 将检测到所有分配都在稍后释放了，并将报告没有泄漏。