slice-rbtree

一个 #[no_std] 红黑树，完全封装在一个字节数组切片中

最初是为在 Solana 账户 中存储数据而开发的，这个crate允许你在不反序列化整个树的情况下访问树节点。当你有一个在原始内存中的大树，但只想一次交互几个值时，这非常有用。

这个crate中有两个核心类型： RBTree 和 RBForest

RBTree

正如其名所示，它是一个 红黑树，包含在字节数组切片中（使用 borsh 进行序列化和反序列化）。API类似于 BTreeMap，但有几点例外，例如 Entry API，但将在未来的版本中添加。

use slice_rbtree::tree::{tree_size, RBTree, TreeParams};
// RBTree requires input slice to have a proper size
// Each node in the `RBTree` has a fixed size known at compile time,
// so to estimate this size `KSIZE` and `VSIZE` parameters should be passed to tree_size
let size = tree_size(
    TreeParams {
        k_size: 50,
        v_size: 50,
    },
    10,
);

let mut buffer = vec![0; size];

let mut movie_reviews: RBTree<String, String, 50, 50> =
    RBTree::init_slice(&mut buffer).unwrap();

// review some movies.
movie_reviews.insert("Office Space".to_string(),       "Deals with real issues in the workplace.".to_string());
movie_reviews.insert("Pulp Fiction".to_string(),       "Masterpiece.".to_string());
movie_reviews.insert("The Godfather".to_string(),      "Very enjoyable.".to_string());
movie_reviews.insert("The Blues Brothers".to_string(), "Eye lyked it a lot.".to_string());

// check for a specific one.
if !movie_reviews.contains_key("Les Misérables") {
    println!(
        "We've got {} reviews, but Les Misérables ain't one.",
        movie_reviews.len()
    );
}

// oops, this review has a lot of spelling mistakes, let's delete it.
movie_reviews.remove("The Blues Brothers");

// look up the values associated with some keys.
let to_find = ["Up!".to_string(), "Office Space".to_string()];
for movie in &to_find {
    match movie_reviews.get(movie) {
        Some(review) => println!("{movie}: {review}"),
        None => println!("{movie} is unreviewed."),
    }
}

// iterate over everything.
for (movie, review) in movie_reviews.pairs() {
    println!("{movie}: \"{review}\"");
}

RBforest

有时候，你可能必须使用一组大小未知的类似树。在这种情况下，你可以在不同的切片中分配这样的树，但这将非常低效：你必须事先考虑每个树的大小，而且仍然有可能某些树将填满，而其他树（几乎是）为空。

RBForest 通过为树集使用一个共同的节点池来解决此问题。 RBForest 的API模仿 RBTree，但增加了一个额外的参数：树的索引。

use slice_rbtree::forest::{forest_size, ForestParams, RBForest};
// RBForest requires input slice to have a proper size
let size = forest_size(
    ForestParams {
        k_size: 50,
        v_size: 50,
        max_roots: 2,
    },
    10, // the desired number of nodes
);

let mut buffer = vec![0; size];

// `String` type has variable length, but we have to chose some fixed maximum length (50 bytes for both key and value)
let mut reviews: RBForest<String, String, 50, 50> =
    RBForest::init_slice(&mut buffer, 2).unwrap();

// Let tree 0 be the movie tree and tree 1 - the book tree

// review some movies.
reviews.insert(0, "Office Space".to_string(),       "Deals with real issues in the workplace.".to_string());
reviews.insert(0, "Pulp Fiction".to_string(),       "Masterpiece.".to_string());
reviews.insert(0, "The Godfather".to_string(),      "Very enjoyable.".to_string());
reviews.insert(0, "The Blues Brothers".to_string(), "Eye lyked it a lot.".to_string());

// review some books
reviews.insert(1, "Fight club".to_string(),            "Brad Pitt is cool!".to_string());
reviews.insert(1, "Alice in Wonderland".to_string(),   "Deep than you think.".to_string());
reviews.insert(1, "1984".to_string(),                  "A scary dystopia.".to_string());
reviews.insert(1, "The Lord of the Rings".to_string(), "Poor Gollum.".to_string(),
);

// check for a specific one.
if !reviews.contains_key(0, "Les Misérables") {
    println!(
        "We've got {} movie reviews, but Les Misérables ain't one.",
        reviews.len(0).expect("No such tree")
    );
}
if reviews.contains_key(1, "1984") {
    println!(
        "We've got {} book reviews and 1984 among them: {}.",
        reviews.len(0).expect("No such tree"),
        reviews.get(1, "1984").unwrap()
    );
}

// oops, this review has a lot of spelling mistakes, let's delete it.
reviews.remove(0, "The Blues Brothers");

// look up the values associated with some keys.
let to_find = ["Up!".to_string(), "Office Space".to_string()];
for movie in &to_find {
    match reviews.get(0, movie) {
        Some(review) => println!("{movie}: {review}"),
        None => println!("{movie} is unreviewed."),
    }
}

// iterate over movies.
for (movie, review) in reviews.pairs(0).expect("No such tree") {
    println!("{movie}: \"{review}\"");
}
///
// Too many reviews, delete them all!
reviews.clear();
assert!(reviews.is_empty(0));
assert!(reviews.is_empty(1));

基准测试

《slice-rbtree》背后的主要思想是，如果你只想与整个映射的一个小部分进行交互，你不必反序列化整个映射。

为了将RBTree与BTreeMap进行比较，我们进行了以下测量：

1. "反序列化" — 从字节数组中获取映射的时间
2. "访问一个值" — 从现有映射中获取值的时间
3. "添加一个值" — 在映射中插入新值的时间

如你所见，RBTree在访问/插入操作中比BTreeMap慢2-3倍，但可以非常快速地打开。

基准测试中使用的类型

struct MyType {
    array: [u8; 10],
    float: f64,
    num: u64,
    num2: u32,
}