基于 Slab 的 B-Tree 实现

此crate提供了一种基于slab数据结构的标准BTreeMap和BTreeSet数据结构的替代实现。原则上，此实现更灵活且更节省内存。它通过提供通过BTreeExt trait扩展B-Tree的低级操作集，使其更灵活，该trait可以用来进一步扩展BTreeMap集合的功能。此外，底层的节点分配方案通过一个类型参数进行了抽象，该参数可以被任何实现类似slab操作的任意数据结构实例化。默认情况下，使用的是来自slab crate的Slab类型，这意味着树中的每个节点都在一个连续的内存区域中分配，从而减少了所需的分配数量。理论上，可以使用另一种类型来在堆栈上存储整个B-Tree。

使用方法

从用户的角度来看，此crate提供的集合可以像标准BTreeMap和BTreeSet集合一样使用。

use btree_slab::BTreeMap;

// type inference lets us omit an explicit type signature (which
// would be `BTreeMap<&str, &str>` in this example).
let mut movie_reviews = BTreeMap::new();

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

// 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!", "Office Space"];
for movie in &to_find {
    match movie_reviews.get(movie) {
       Some(review) => println!("{}: {}", movie, review),
       None => println!("{} is unreviewed.", movie)
    }
}

// Look up the value for a key (will panic if the key is not found).
println!("Movie review: {}", movie_reviews["Office Space"]);

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

自定义节点分配

可以使用btree_slab::generic::BTreeMap来使用自定义的slab类型来处理节点分配。

use slab::Slab;
use btree_slab::generic::BTreeMap;

let mut map: BTreeMap<K, V, Slab<Node<K, V>>> = BTreeMap::new();

在此示例中，Slab<Node<_, _>>类型是一个负责节点分配的类似slab的数据结构。它必须实现所有定义cc_traits::Slab trait别名的特质。

扩展 API 及寻址

在本实现中，B树的每个节点通过Address类型进行寻址。通过BTreeExt特质可见的扩展API允许调用者使用这种寻址系统来探索、访问和修改树的内层结构。这可以用来进一步扩展BTreeMap集合的功能，例如在btree-range-map库中。

许可协议

根据以下任一协议授权：

• Apache License，版本2.0（LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0）
• MIT许可协议（LICENSE-MIT 或 http://opensource.org/licenses/MIT）

任选其一。

贡献

除非你明确声明，否则根据Apache-2.0许可证定义的，任何有意提交给作品并包含在内的贡献，都将根据上述协议双授权，不附加任何额外条款或条件。