CRoaring入门教程：3分钟上手高性能位图数据结构

【免费下载链接】CRoaring Roaring bitmaps in C (and C++), with SIMD (AVX2, AVX-512 and NEON) optimizations: used by Apache Doris, ClickHouse, and StarRocks 项目地址: https://gitcode.com/gh_mirrors/cr/CRoaring

CRoaring是一个用C和C++实现的高性能位图数据结构库，通过SIMD（AVX2、AVX-512和NEON）优化，被Apache Doris、ClickHouse和StarRocks等知名项目广泛采用。本文将带你快速掌握CRoaring的核心功能和使用方法，让你在3分钟内就能上手这个高效的位图工具。

什么是Roaring Bitmap？ 🤔

位图（Bitset）是一种高效的数据结构，但传统位图往往占用过多内存。Roaring Bitmap作为一种压缩位图格式，在性能上优于WAH、EWAH等传统压缩位图，已被Apache Lucene、Elasticsearch、InfluxDB等众多大型系统采用。

📚 核心优势：Roaring Bitmap通过智能压缩算法，在保证查询性能的同时显著减少内存占用，特别适合处理大规模数据集的交并补等集合操作。

快速开始：3分钟上手步骤 ⚡

1️⃣ 获取源码

git clone https://gitcode.com/gh_mirrors/cr/CRoaring
cd CRoaring

2️⃣ 生成合并文件（推荐）

CRoaring支持合并成单个源文件，方便集成到项目中：

./amalgamation.sh

执行后会生成roaring.h、roaring.c和示例文件，你只需将这两个核心文件复制到项目中即可使用。

3️⃣ 基本使用示例（C语言）

创建demo.c文件：

#include <stdio.h>
#include <stdlib.h>
#include "roaring.c"  // 合并模式下直接包含

int main() {
    // 创建空位图
    roaring_bitmap_t *r1 = roaring_bitmap_create();
    
    // 添加元素
    for (uint32_t i = 100; i < 1000; i++) {
        roaring_bitmap_add(r1, i);
    }
    
    // 基本操作
    printf("元素数量: %d\n", (int)roaring_bitmap_get_cardinality(r1));
    printf("是否包含500: %s\n", roaring_bitmap_contains(r1, 500) ? "是" : "否");
    
    // 释放内存
    roaring_bitmap_free(r1);
    return EXIT_SUCCESS;
}

编译运行：

cc -o demo demo.c
./demo

输出结果：

元素数量: 900
是否包含500: 是

4️⃣ C++版本示例

创建demo.cpp文件：

#include <iostream>
#include "roaring.hh"  // C++接口
#include "roaring.c"

using namespace roaring;

int main() {
    Roaring r1;
    for (uint32_t i = 100; i < 1000; i++) {
        r1.add(i);
    }
    
    std::cout << "元素数量: " << r1.cardinality() << std::endl;
    std::cout << "是否包含500: " << std::boolalpha << r1.contains(500) << std::endl;
    
    return 0;
}

编译运行：

c++ -std=c++11 -o demopp demo.cpp
./demopp

核心功能与API 🔑

基本操作

功能	C接口	C++接口
创建位图	roaring_bitmap_create()	Roaring()
添加元素	roaring_bitmap_add(r, x)	r.add(x)
删除元素	roaring_bitmap_remove(r, x)	r.remove(x)
检查存在	roaring_bitmap_contains(r, x)	r.contains(x)
获取数量	roaring_bitmap_get_cardinality(r)	r.cardinality()

集合操作

// C语言示例：计算两个位图的并集
roaring_bitmap_t *union_result = roaring_bitmap_or(r1, r2);

// C++示例：计算并集
Roaring union_result = r1 | r2;

内存优化

Roaring Bitmap会自动选择最优的存储方式，也可手动优化：

// 优化长连续序列的存储
roaring_bitmap_run_optimize(r1);

高级特性 ✨

64位支持

CRoaring提供64位位图支持，适合处理超大范围的整数：

roaring64_bitmap_t *r64 = roaring64_bitmap_create();
roaring64_bitmap_add(r64, 18000000000000000100ULL);

序列化

支持高效的序列化和反序列化，方便存储和网络传输：

// 序列化
size_t size = roaring_bitmap_portable_size_in_bytes(r1);
char *buf = malloc(size);
roaring_bitmap_portable_serialize(r1, buf);

// 反序列化
roaring_bitmap_t *r2 = roaring_bitmap_portable_deserialize(buf);

性能优化建议 🚀

1. 批量操作：使用addMany（C++）或roaring_bitmap_or_many（C）进行批量添加，比单次操作更高效
2. 运行优化：对有长连续序列的数据调用runOptimize()
3. 内存管理：使用自定义内存分配器（通过roaring_init_memory_hook）优化内存使用

实际应用场景 📈

• 数据库索引：ClickHouse等数据库使用Roaring Bitmap加速查询
• 数据分析：高效计算用户标签交集、并集
• 网络安全：IP地址集合管理与匹配
• 搜索引擎：文档倒排索引压缩存储

资源与文档 📚

• 头文件定义：核心API在include/roaring/roaring.h和include/roaring/roaring64.h中定义
• C++接口：cpp/roaring/roaring.hh提供更易用的面向对象接口
• 示例代码：项目中的tests目录包含丰富的使用示例

通过本教程，你已经掌握了CRoaring的基本使用方法。这个强大的位图库能帮助你在处理大规模数据集时显著提升性能并减少内存占用，快去试试吧！

【免费下载链接】CRoaring Roaring bitmaps in C (and C++), with SIMD (AVX2, AVX-512 and NEON) optimizations: used by Apache Doris, ClickHouse, and StarRocks 项目地址: https://gitcode.com/gh_mirrors/cr/CRoaring