位图索引通过将字段的取值映射为二进制位序列，利用位运算的高效特性实现快速数据筛选，在低基数字段的查询场景中性能远超传统B树索引。其核心优势在于可以用极小的内存存储大量数据的索引信息，同时通过位与、位或等操作快速完成多条件组合查询。
位图索引的核心存储结构
位图索引的底层存储基于位数组，每个不同的字段取值对应一个位数组，数组的长度等于数据表的总行数。如果某行数据对应这个字段取值，那么位数组中对应位置的位就设为1，否则设为0。在C++中可以用std::vector<uint64_t>来存储位数组，每个uint64_t可以存储64个位的索引信息，最大化利用内存空间。
假设我们有一个用户表，其中性别字段只有男、女两个取值，表总共有1000行数据，那么性别字段的位图索引会包含两个位数组：
- 男性位图：长度为1000的二进制序列，第i位为1表示第i行用户性别为男
- 女性位图：长度为1000的二进制序列，第i位为1表示第i行用户性别为女
底层核心算法实现
位图构建算法
构建位图索引需要遍历全表数据，将每一行的字段取值映射到对应的位图中。为了避免频繁的位操作开销，我们可以按uint64_t的粒度批量设置位值。
#include <vector>
#include <unordered_map>
#include <string>
// 位图索引类
class BitmapIndex {
private:
// 字段取值到对应位图的映射
std::unordered_map<std::string, std::vector<uint64_t>> bitmap_map;
// 数据总行数
size_t total_rows;
// 每个uint64_t存储的位数量
static const size_t BITS_PER_UNIT = 64;
public:
BitmapIndex(size_t rows) : total_rows(rows) {}
// 添加一行数据的索引信息
void add_row(size_t row_id, const std::string& value) {
// 如果当前取值还没有对应的位图，先初始化位图
if (bitmap_map.find(value) == bitmap_map.end()) {
// 计算需要的uint64_t数量，向上取整
size_t unit_count = (total_rows + BITS_PER_UNIT - 1) / BITS_PER_UNIT;
bitmap_map[value] = std::vector<uint64_t>(unit_count, 0);
}
// 计算row_id对应的uint64_t索引和位偏移
size_t unit_idx = row_id / BITS_PER_UNIT;
size_t bit_offset = row_id % BITS_PER_UNIT;
// 设置对应位为1
bitmap_map[value][unit_idx] |= (1ULL << bit_offset);
}
// 获取某个取值对应的位图
const std::vector<uint64_t>* get_bitmap(const std::string& value) const {
auto it = bitmap_map.find(value);
if (it == bitmap_map.end()) {
return nullptr;
}
return &(it->second);
}
};
单条件查询算法
单条件查询只需要取出对应字段取值的位图，位图中为1的位置就是符合条件的行ID。如果需要返回行ID列表，可以遍历位图提取所有为1的位对应的行号。
#include <vector>
#include <cstdint>
// 从位图中提取所有为1的位对应的行ID
std::vector<size_t> extract_row_ids(const std::vector<uint64_t>& bitmap, size_t total_rows) {
std::vector<size_t> result;
size_t unit_count = bitmap.size();
for (size_t i = 0; i < unit_count; ++i) {
uint64_t unit = bitmap[i];
// 如果当前unit为0，跳过
if (unit == 0) {
continue;
}
// 遍历当前unit的每一位
for (size_t j = 0; j < 64; ++j) {
// 检查第j位是否为1
if (unit & (1ULL << j)) {
size_t row_id = i * 64 + j;
// 避免超过总行数的位被计入
if (row_id < total_rows) {
result.push_back(row_id);
}
}
}
}
return result;
}
多条件组合查询算法
位图索引的最大优势是可以通过位运算快速完成多条件组合查询。比如查询性别为男且年龄在某个区间的用户，只需要将男性位图和对应年龄区间的位图做按位与运算，结果位图中为1的位置就是同时满足两个条件的行ID。
位运算的实现需要保证两个位图的长度一致，按uint64_t为单位逐个做与、或、非运算即可：
#include <vector>
#include <cstdint>
// 两个位图做按位与运算，返回结果位图
std::vector<uint64_t> bitmap_and(const std::vector<uint64_t>& a, const std::vector<uint64_t>& b) {
size_t len = a.size();
std::vector<uint64_t> result(len, 0);
for (size_t i = 0; i < len; ++i) {
result[i] = a[i] & b[i];
}
return result;
}
// 两个位图做按位或运算，返回结果位图
std::vector<uint64_t> bitmap_or(const std::vector<uint64_t>& a, const std::vector<uint64_t>& b) {
size_t len = a.size();
std::vector<uint64_t> result(len, 0);
for (size_t i = 0; i < len; ++i) {
result[i] = a[i] | b[i];
}
return result;
}
// 位图取反运算，返回结果位图
std::vector<uint64_t> bitmap_not(const std::vector<uint64_t>& bitmap, size_t total_rows) {
size_t len = bitmap.size();
std::vector<uint64_t> result(len, 0);
for (size_t i = 0; i < len; ++i) {
result[i] = ~bitmap[i];
}
// 处理最后一个unit中超过总行数的高位，将其置为0
size_t last_unit_idx = (total_rows - 1) / 64;
size_t valid_bits = total_rows % 64;
if (valid_bits != 0) {
// 生成掩码，保留低valid_bits位
uint64_t mask = (1ULL << valid_bits) - 1;
result[last_unit_idx] &= mask;
}
return result;
}
性能优化策略
为了进一步提升位图索引的查询性能，可以采用以下优化手段：
- 压缩存储：对于稀疏位图（1的数量很少），可以使用游程编码或者Roaring Bitmap的压缩方式，减少内存占用同时提升位运算效率
- 批量位运算：利用CPU的SIMD指令集，一次处理多个uint64_t的位运算，大幅提升多条件组合查询的速度
- 缓存热点位图：将频繁查询的字段取值对应的位图缓存在CPU高速缓存中，减少内存访问的开销
- 延迟物化：查询时先只做位运算得到结果位图，等到需要返回具体数据的时候再按行ID去取数据，避免提前加载无用数据
适用场景与局限性
位图索引最适合低基数字段（比如性别、状态、类型等取值少的字段）的查询场景，在高基数字段（比如用户ID、手机号等取值多的字段）中，位图会非常稀疏，内存占用大且查询效率下降。另外位图索引的更新成本很高，每次插入、删除、修改字段取值都需要更新对应的位图，因此更适合读多写少的数据库场景。
通过合理的底层算法实现和优化，C++实现的位图索引可以将低基数字段的多条件查询速度提升数倍甚至数十倍，有效解决数据库查询的性能瓶颈问题。