Binstore

Binstore 是用 Rust 编写的简单键值存储。这意味着 binstore 不处理序列化/反序列化。它所做的只是以缓存友好和紧凑的文件格式存储键值元素。目前，这个项目主要是为了娱乐，但希望将来能够演变成可以使用的工具。

文件格式

头部

稀疏索引

密集索引

数据

说明

binstore 文件分为四个部分

1. 头部。头部帮助我们识别 binstore 文件（通过魔数），它们允许我们知道当前 binstore 引擎是否可以读取给定的 binstore 文件（版本号），以及 binstore 文件是在何时创建的。我们还存储其他部分的偏移量和存储在此数据文件中的条目数。
2. 稀疏索引。不超过 1-2 MB 的索引；稀疏索引用于在密集索引中跳转到我们正在查找的键大致所在的位置。稀疏索引对于避免全扫描至关重要。
3. 密集索引。在密集索引中，存在一个从键（以下将解释键）到存储与该键相关联的Value集合的文件偏移量的映射。密集索引条目大小固定且按其键排序；这允许二分查找。
4. 数据。这是实际存储Value的地方。为了节省空间，我们使用LZ4压缩算法。

示例

查询

use std::iter::FromIterator;
use std::collections::{BTreeMap, BTreeSet};
use tempfile::NamedTempFile;
use binstore::bucket::*;

fn main() {
    let mut bmap = BTreeMap::new();
    for key in 0 .. 100 {
        bmap.insert(key as u64, BTreeSet::from_iter(0 .. (key as u128)));
    }

    let tmp = NamedTempFile::new().unwrap();
    create(tmp.path(), &bmap).expect("create");

    {
        let bucket = Bucket::open(tmp.path()).expect("open");
        let mut bucket = bucket.check_headers().expect("check_headers");
        let si = bucket.read_sparse_index().expect("sparse index");

        for (key, actual_values) in &bmap {
            let (offset_1, offset_2) = si.try_get(*key).expect("try_get");
            let values = bucket.try_get(*key, offset_1, offset_2)
                .expect("try_get (1)")
                .expect("try_get (2)");
            assert_eq!(actual_values, &values);
        }
    }
}

合并

use std::iter::FromIterator;
use std::collections::{BTreeMap, BTreeSet};
use tempfile::NamedTempFile;
use binstore::bucket::*;

fn main() {
    let mut bmap1 = BTreeMap::new();
    for key in 0 .. 100 {
        bmap1.insert(key as u64, BTreeSet::from_iter(0 .. (key as u128)));
    }

    let mut bmap2 = BTreeMap::new();
    for key in 0 .. 200 {
        bmap2.insert(key as u64, BTreeSet::from_iter(0 .. (key as u128)));
    }

    let tmp1 = NamedTempFile::new().unwrap();
    let tmp2 = NamedTempFile::new().unwrap();
    let merged_file = NamedTempFile::new().unwrap();

    create(tmp1.path(), &bmap1).unwrap();
    create(tmp2.path(), &bmap2).unwrap();
    merge(tmp1.path(), tmp2.path(), merged_file.path()).unwrap();
}

将来将在examples/中添加更多示例。