radixmap

这个crate是一个基于Rust的Radix树实现。Radix树，也称为Trie，是一种空间优化的树形数据结构，用于高效的信息检索。它的主要优点是空间优化、快速基于前缀的搜索和高效的内存使用。Radix树被广泛使用，尤其是在HTTP路由器中。

特性

• 快速基于前缀的查找
• 支持RadixMap和RadixSet
• 与标准集合兼容的接口
• 支持命名参数、glob和正则表达式
• 前序、后序、层序遍历
• 全面的单元测试确保正确性

示例

use bytes::Bytes;
use radixmap::{RadixMap, RadixResult};

fn main() -> RadixResult<()> {
    let mut map = RadixMap::new();
    map.insert("/api", "api")?;
    map.insert("/api/v1", "v1")?;
    map.insert("/api/v1/user", "user1")?;
    map.insert("/api/v2", "v2")?;
    map.insert("/api/v2/user", "user2")?;

    assert_eq!(map.get(b"/api/v1/user"), Some(&"user1"));
    assert_eq!(map.get(b"/api/v2/user"), Some(&"user2"));

    let mut iter = map.iter(); // pre-order by default

    assert_eq!(iter.next(), Some((&Bytes::from("/api"), &"api")));
    assert_eq!(iter.next(), Some((&Bytes::from("/api/v1"), &"v1")));
    assert_eq!(iter.next(), Some((&Bytes::from("/api/v1/user"), &"user1")));
    assert_eq!(iter.next(), Some((&Bytes::from("/api/v2"), &"v2")));
    assert_eq!(iter.next(), Some((&Bytes::from("/api/v2/user"), &"user2")));
    assert_eq!(iter.next(), None);

    Ok(())
}

基准测试

• MacBook Air, Apple M2 24G, Sonoma 14.4, Rust 1.78.0

• AWS c5.2xlarge, 8C 16G, Ubuntu 22.04, Rust 1.78.0