Skip to content

Disk persisted immutable index built using a single pass iterator

Notifications You must be signed in to change notification settings

appaquet/extindex-rs

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

53 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

extindex

crates.io

Immutable persisted index (on disk) that can be built in one pass using a sorted iterator, or can use extsort to externally sort the iterator first, and then build the index from it.

The index allows random lookups and sorted scans. An indexed entry consists of a key and a value. The key needs to implement Eq and Ord, and both the key and values need to implement a Serializable trait for serialization to and from disk. It is possible to rely on the serde library to implement this trait for most types.

The index is built using a skip list-like data structure, but lookups start from the end of the index instead of the beginning. This allows building the index in a single pass on a sorted iterator, as starting from the beginning would require knowing checkpoints/nodes ahead in the file.

Example

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());
}

Roadmap

  • Possibility to use a Bloom filter to avoid disk access when the index does not contain a key.

About

Disk persisted immutable index built using a single pass iterator

Resources

Stars

Watchers

Forks

Packages

No packages published

Languages