artsy

文档

ART树的实现工作（ART.pdf）。

特性

终止符自定义

尽管原始的ART论文只考虑ASCII字符串作为键，因此定义 \0 作为字符串终止符，但这个想法可以通过使用 0xff 作为字符串终止符来扩展到UTF-8。当然，如果你插入原始字节，你可以使用任何终止符。

默认情况下，如果你使用 String 键，你应该使用 for_utf8()。

终止符自定义是为什么每个查找/插入/删除方法都返回一个 Result<.., KeyContainsTerminator>；每个方法都有一个等效的非检查版本。

过滤使用的节点类型

尽管原始ART论文使用了4种不同的节点类型（4、16、48和256个子节点），但你可能不希望使用用于稀疏trie或中间节点类型的节点类型（无论什么原因）。除了256个子节点的最终trie节点外，任何节点类型都可以通过构建时不启用其特性标志来禁用。

cargo build --features "node4" # only use the smallest node, fallback to Node256

cargo build --features "node4 node16" # disable Node48

cargo build --features "node16" # only use the intermediate node with SIMD search

禁用Node16的SIMD

默认情况下应该启用SIMD（如果您的系统支持）。要显式禁用SIMD，请使用具有 no-simd 特性的构建。

示例

插入/查找

let mut map = Trie::for_utf8();
map.insert(b"a", 0).unwrap();
map.insert(b"ac", 1).unwrap();

assert_eq!(map.get(b"a").unwrap(), Some(&0));
assert_eq!(map.get(b"ac").unwrap(), Some(&1));
assert_eq!(map.get(b"ab").unwrap(), None);

待办事项列表

• 重构插入/更新子节点，移除插入后的重复和额外查找
• 键/值/项 Iterator
• 删除
• 路径压缩