Lib.rs

DART (磁盘自适应Radix树)

A Rust实现带有乐观锁修改的自适应Radix树，以实现线程安全的并发。

DART的独特之处在于它从可配置的LRU缓存中提供操作，如果条目已被逐出，将回退到磁盘。这种修改允许您以几乎恒定的内存占用来提供操作，以换取性能。这是考虑到全文搜索而开发的，在这种情况下，无疑将通过树中的某些常见或热点路径。热点路径将来自LRU，而其他一切都将从磁盘获取。

这个想法是从Julien Lemoine的一系列博客文章中获得的灵感，他在这些文章中讨论了知名搜索即服务公司Algolia的原索引结构。

此外，我还编写了这个库作为我在postgresql全文搜索扩展中原始倒排索引实现的替代品，该扩展仍然是早期且实验性的，我还没有完成替换。

示例

use dart::tree::{Dart, NodeCacheConfig};

//LRU Size, LRU Segments, Path for Disk Writes
let cache_config = NodeCacheConfig::new(100, 1, path.clone() + "/tree")
let tree = Dart::<u64>::new(cache_config);

tree.upsert(&[1, 2, 3, 4], 64)
let res = tree.get(&[1, 2, 3, 4]);

assert_eq!(res, Some(64));
tree.upsert(&[1, 2, 3, 4], 65)

let res = tree.get(&[1, 2, 3, 4]);
assert_eq!(res, Some(65));
let res = tree.get(&[1, 2, 3, 5]);
assert_eq!(res, None);

let res = tree.remove(&[1, 2, 3, 4]);
assert_eq!(res, Some(65))
let res = tree.remove(&[1, 2, 3, 4]);
assert_eq!(res, None)

GDART

如果以上还不够，我创建了一个DART的代数版本GDART，它将上述所有优点结合起来，并在其上实现代数[0]。这使得您能够保持树的大小，使最近搜索和更新保持快速。操作也并行化在代数上，以便可以快速找到旧内容。

代际数据结构基本上是一种版本化的数据结构，即当达到某个大小阈值后，会创建一个新的版本，并将旧的数据结构附加到历史记录中。更新操作（upserts）指向最新一代，搜索/删除操作首先在最新一代进行，如果没有在当前代找到，再并行处理历史代。这种结构的优点是，通过保持较小的树的大小，可以加快单代操作的速度，以及多代操作的并行性。

示例

use dart::generational::GDart;

//Max generation size, LRU Size for a generation, LRU Segments, Path for all writes
let mut tree = GDart::<u64>::new(5000, 1000, 5, Some(path));

tree.upsert(&[1, 2, 3, 4], 64)
let res = tree.get(&[1, 2, 3, 4]);

assert_eq!(res, Some(64));
tree.upsert(&[1, 2, 3, 4], 65)

let res = tree.get(&[1, 2, 3, 4]);
assert_eq!(res, Some(65));
let res = tree.get(&[1, 2, 3, 5]);
assert_eq!(res, None);

let res = tree.remove(&[1, 2, 3, 4]);
assert_eq!(res, Some(65))
let res = tree.remove(&[1, 2, 3, 4]);
assert_eq!(res, None)

Dart和GDart的接口基本上相同，值得注意的是，在更新和删除操作中，树必须是可变的（mut）。