bplus_store 0.2.0

Copy-on-write B+ tree with page-aligned storage, split/merge, and crash-safety primitives.
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

use crate::api::{KeyEncodingId, TreeId};
use crate::database::manifest::{ManifestRec, ManifestRec::*};
use crate::keyfmt::KeyFormat;

use std::collections::HashMap;
/// Persistent catalog entry describing one logical B+ tree.
#[derive(Clone)]
pub struct TreeMeta {
    /// Stable opaque identifier for this tree (never reused).
    pub id: TreeId,
    /// Human-readable logical name (may change via rename).
    pub name: String,
    /// Comparator / byte ordering (e.g. big-endian u64, big-endian i64, UTF-8).
    pub key_encoding: KeyEncodingId,
    /// On-page key layout (e.g. Raw, PrefixRestarts).
    pub keyfmt_id: KeyFormat,
    /// On-page layout version for forward compatibility.
    pub format_version: u16,
    /// Page ID of metadata slot A.
    pub meta_a: u64,
    /// Page ID of metadata slot B.
    pub meta_b: u64,
    /// Currently committed root node page ID.
    pub root_id: u64,
    /// Current height of the B+ tree.
    pub height: u64,
    /// Approximate number of entries (copied from the metadata page).
    pub size: u64,
    /// Order of the B+ tree (copied from the metadata page).
    pub order: u64,
    /// Last manifest sequence number that modified this record.
    pub last_seq: u64,
}

/// In-memory catalog rebuilt by replaying the manifest log on startup.
///
/// Serves as the authoritative routing table from tree name or ID to its [`TreeMeta`].
#[derive(Clone)]
pub struct Catalog {
    /// Maps logical tree names to their numeric IDs.
    pub by_name: HashMap<String, TreeId>,
    /// Maps numeric tree IDs to their full metadata.
    pub metas: HashMap<TreeId, TreeMeta>,
    /// Next manifest sequence number to assign.
    pub next_seq: u64,
}

impl Default for Catalog {
    fn default() -> Self {
        Self {
            by_name: HashMap::new(),
            metas: HashMap::new(),
            next_seq: 1,
        }
    }
}

impl Catalog {
    /// Creates an empty catalog with sequence numbering starting at 1.
    pub fn new() -> Self {
        Self::default()
    }

    /// Looks up a tree by its logical name.
    pub fn get_by_name(&self, name: &str) -> Option<&TreeMeta> {
        self.by_name.get(name).and_then(|id| self.metas.get(id))
    }

    /// Looks up a tree by its numeric ID.
    pub fn get_by_id(&self, id: &TreeId) -> Option<&TreeMeta> {
        self.metas.get(id)
    }

    /// Applies a single manifest record to update the in-memory catalog state.
    pub fn replay_record(&mut self, rec: &ManifestRec) {
        match rec.clone() {
            CreateTree {
                seq,
                id,
                name,
                key_encoding,
                key_limits,
                key_format,
                encoding_version,
                meta_a,
                meta_b,
                root_id,
                order,
                height,
                size,
            } => {
                self.by_name.insert(name.clone(), id);
                self.metas.insert(
                    id,
                    TreeMeta {
                        id,
                        name: name.clone(),
                        key_encoding,
                        keyfmt_id: key_format,
                        format_version: encoding_version,
                        meta_a,
                        meta_b,
                        root_id,
                        height,
                        size,
                        order,
                        last_seq: seq,
                    },
                );
                let _key_limits = key_limits; // TODO: store and enforce key limits.
                self.next_seq = self.next_seq.max(seq + 1);
            }
            RenameTree { seq, id, new_name } => {
                if let Some(m) = self.metas.get_mut(&id) {
                    self.by_name.remove(&m.name);
                    m.name = new_name.clone();
                    self.by_name.insert(new_name.clone(), id);
                    m.last_seq = seq;
                    self.next_seq = self.next_seq.max(seq + 1);
                }
            }
            DeleteTree { seq, id } => {
                if let Some(m) = self.metas.remove(&id) {
                    self.by_name.remove(&m.name);
                    self.next_seq = self.next_seq.max(seq + 1);
                }
            }
        }
    }
}