Bitrush-Index

Bitrush-Index是一个Rust库，它提供了一个可序列化的位图索引，能够在单个线程上每秒索引数百万个值。默认情况下，此库使用ozbcbitmap构建bitmap-index，但如果您愿意，您也可以使用其他压缩/未压缩的位图。仅支持相等查询（A = X）。

使用方法

要在Rust项目中使用bitrush-index，请将以下内容添加到您的Cargo.toml

[dependencies]
bitrush_index = "0.1.0"

请参阅memory_index以使用内存模式下的Bitrush-Index，以及storage_index以在持久内存（存储模式）中使用Bitrush-Index。

运行示例

cargo run --release --example memory_index

cargo run --release --example storage_index

测试

cargo t

示例和性能

use bitrush_index::{
    BitmapIndex,
    OZBCBitmap,
};

use rand::Rng;
use std::time::Instant;

fn main() {
    const N: usize = 1 << 30; // 1GB
    const K: usize = (1 << 20) * 1; // 1M
    let mut rng = rand::thread_rng();
    let path = std::path::Path::new("bitrush_index_u32");

    let build_options = bitrush_index::new_default_index_options::<u32>();
    let mut b_index = match BitmapIndex::<OZBCBitmap, u32>::create(&path, build_options) {
        Ok(b_index) => b_index,
        Err(err) => panic!("Error occured creating bitmap index: {:?}", err)
    };

    let mut values: Vec<u32> = Vec::new();
    for _i in 0..K {
        let val: u32 = rng.gen::<u32>();
        values.push(val);
    }
    println!("--------------------------------------------------");
    println!("Inserting {} values in bitmap index...", N);
    let timer = Instant::now();

    for i in 0..N {
        match b_index.push_value(values[i % K]) {
            Ok(_) => {},
            Err(err) => panic!("Error occured inserting i = {}, val = {}, error: {:?}", i, values[i % K], err)
        }
    }
    let time_b_index_insert = timer.elapsed();
    println!("Bitmap index created in {:?}.", time_b_index_insert);
    println!("Insert per second = {}.", N / (time_b_index_insert.as_millis() as usize) * 1000);
    println!("--------------------------------------------------");

    let random_index: usize = rng.gen::<usize>() % values.len();
    let val_to_find = values[random_index];

    let timer = Instant::now();

    let values_indexes: Vec<u64> = match b_index.run_query(val_to_find, None, None) {
        Ok(indexes) => indexes,
        Err(err) => panic!("Error occured running looking for value = {}, error: {:?}", val_to_find, err)
    };

    let time_linear_search = timer.elapsed();
    println!("Bitmap index search runned in {:?}, match values founded: {}.", time_linear_search, values_indexes.len());
    println!("--------------------------------------------------");
}

在表中显示了使用N = 1G（2^30）随机值、K基数创建的u32索引的性能，这些值在我的Acer swift 3笔记本电脑上运行，该笔记本电脑配备Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz、256GB SSD TOSHIBA THNSNK25和8GB内存。

注意：随机值是索引大小的最差输入分布。

动机和目的

位图索引传统上被认为是适用于基数低的列，这些列具有适度的不同值数量。在属性A上使用K基数进行位图索引的最简单和最常见方法是为每个属性值V关联一个位图，然后Vth位图代表谓词A=V。这种方法确保了执行搜索的高效解决方案，但在高基数属性上，位图索引的大小会急剧增加（例如，在32位值上，您需要一个2^32位图，一个用于每个可能的值，因此您有一个由每个索引值的2^32位组成的索引）。如您所理解的，这种方法在高基数列上是实际不可行的。

解决高基数列大小问题的最常见方法非常简单，例如，可以将32位索引拆分为八个4位子索引，然后将位图的数量从2^32减少到8 * 2^4（因此每个插入值有128位，而不是2^32位），但缺点是在查询时间和插入时间现在您必须读取/设置八个位图（每个4位组一个）而不是一个，然后查询和插入时间的索引性能会显著下降。因此，为了在不显著降低查询和插入性能的情况下限制位图索引的大小，最佳方法是拆分索引为子索引，并用一种位图压缩方法（其中一些是Roaring、Compax、EWAH、WAH等）压缩每个位图（文献中有无数种方法）。

此时的主要问题是选择具有正确压缩方法的位图索引的正确位图数量，以找到索引大小和查询/插入性能之间的最佳折衷方案：对于未压缩的位图，更多的位图意味着更好的查询/插入性能和最差的位图大小，反之亦然，但对于压缩位图，这并不正确。对于压缩位图，每个位图的压缩比率取决于位图输入，而位图输入取决于您的输入数据分布以及组成位图索引的位图数量（例如，如果您将16位索引拆分为两个8位子索引，在随机的输入分布中，对于每个位图，平均每个2^8值设置1位，而不是每个2^16值设置1位，因此对于压缩位图，由2^16位组成的16位索引可能具有较小的尺寸，而由2^8位组成的两个8位索引的总和更大）。

因此，我创建了Bitrush-Index，这是一个Rust库，允许您选择每个索引/子索引的位图压缩方法和位图数量，因此可以在每个索引值和输入分布上创建最佳位图索引。Bitrush-Index还提供了一个默认的位图索引，该索引使用ozbcbitmap在每个可能的有符号/无符号整数（从8位到128位整数）上构建。

关于OZBCbitmap

我设计并开发了ozbc，唯一的目标是在位图索引场景中提供最佳的位图压缩方法，这里是我大学论文期间开发的第一个C++版本和一些ozbc、Roaring和EWAH16/32的基准测试：WhyOZBC。

文档

链接 .

路线图

• 改进测试和文档。
• 编写C API。
• 编写备份功能。
• 以异步模式写入位图块。
• 添加其他位图实现。
• 改进插入/查询性能。

建议

对于改进此库的建议，非常欢迎，对于任何建议，您可以通过私信或创建一个issue来联系我。

许可

版权 © 2019 Lorenzo Vannucci

在通用公共许可证（GPL）下许可，版本3（LICENSE http://www.gnu.org/licenses/gpl-3.0.en.html）。

如果您需要许可

如果您需要不同许可并真正想使用我的代码，请与我联系。我是唯一作者，我可以更改许可。

贡献

您有意提交以包含在bitrush-index中的任何贡献，均应按GPLv3或更高版本许可，不得附加任何其他条款或条件。