mindb 0.1.2

Lightweight embedded key–value store with write-ahead log and zstd compression.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

//! Sparse segment index for quickly narrowing down on-disk lookups.
#![allow(dead_code)]

use super::{SequenceNumber, VersionPointer};

/// Entry that maps a high-order key to the pointer of the closest record.
#[derive(Clone, Debug)]
pub struct SparseEntry {
    pub key: Vec<u8>,
    pub pointer: VersionPointer,
}

/// Segment-local sparse index organised as an ordered array.
#[derive(Clone, Debug, Default)]
pub struct SparseIndex {
    entries: Vec<SparseEntry>,
}

impl SparseIndex {
    /// Constructs a sparse index from the provided entries. The entries will be sorted
    /// by key to allow binary searches during lookups.
    pub fn new(mut entries: Vec<SparseEntry>) -> Self {
        entries.sort_by(|a, b| a.key.cmp(&b.key));
        Self { entries }
    }

    /// Returns the number of entries stored in the sparse index.
    pub fn len(&self) -> usize {
        self.entries.len()
    }

    /// Attempts to locate a pointer for the provided key that is visible to the snapshot.
    pub fn locate(&self, key: &[u8], snapshot: SequenceNumber) -> Option<VersionPointer> {
        let idx = self
            .entries
            .binary_search_by(|entry| entry.key.as_slice().cmp(key))
            .unwrap_or_else(|idx| idx.saturating_sub(1));

        self.entries.get(idx).and_then(|entry| {
            if entry.key.as_slice() <= key && entry.pointer.is_visible_at(snapshot) {
                Some(entry.pointer.clone())
            } else {
                None
            }
        })
    }

    /// Returns a vector with the entries that fall within the provided key range.
    pub fn range(
        &self,
        start: &[u8],
        end: &[u8],
        snapshot: SequenceNumber,
    ) -> Vec<(Vec<u8>, VersionPointer)> {
        self.entries
            .iter()
            .filter(|entry| {
                entry.key.as_slice() >= start
                    && entry.key.as_slice() <= end
                    && entry.pointer.is_visible_at(snapshot)
            })
            .map(|entry| (entry.key.clone(), entry.pointer.clone()))
            .collect()
    }
}