extindex

不可变持久化索引（在磁盘上），可以使用排序迭代器一次性构建，或者可以使用 extsort 对迭代器进行外部排序，然后从中构建索引。

索引允许随机查找和排序扫描。索引条目由键和值组成。键需要实现 Eq 和 Ord，并且键和值都需要实现一个 Serializable 特性以进行序列化和反序列化到磁盘。可以使用 serde 库为大多数类型实现此特性。

索引使用类似于跳表的数据结构构建，但查找从索引的末尾开始，而不是从开头。这允许在排序迭代器上单次遍历构建索引，因为从开头开始需要知道文件中的检查点/节点。

示例

extern crate extindex;
extern crate serde;

use extindex::{Builder, Entry, Reader, SerdeWrapper};

#[derive(Ord, PartialOrd, Eq, PartialEq, Debug, serde::Serialize, serde::Deserialize)]
struct SomeStruct {
    a: u32,
    b: String,
}

fn main() {
    let index_file = tempfile::NamedTempFile::new().unwrap();

    let builder = Builder::new(index_file.path());
    let entries = vec![Entry::new(
        "my_key".to_string(),
        SerdeWrapper(SomeStruct {
            a: 123,
            b: "my value".to_string(),
        }),
    )];
    builder.build(entries.into_iter()).unwrap();

    let reader = Reader::<String, SerdeWrapper<SomeStruct>>::open(index_file).unwrap();
    assert!(reader.find(&"my_key".to_string()).unwrap().is_some());
    assert!(reader.find(&"notfound".to_string()).unwrap().is_none());
}

路线图

• 可以使用Bloom过滤器在索引不包含键时避免磁盘访问。