去年我们接手了一个数据分析系统，日增数据量500万条，总数据量已经突破10亿。最要命的是，运营部门的查询需求五花八门：“查询所有上海地区、年龄25-35岁、最近7天活跃的VIP用户”，这种查询每天要跑上千次。

原系统用的是普通B+树索引，复杂查询经常要扫描上千万行数据，一个查询跑十几分钟是家常便饭。经过3个月的优化，我们用红黑树优化了内存索引结构，用位图索引处理低基数字段，查询性能提升了50倍。今天就来聊聊这段"与索引死磕"的经历。

问题暴露：B+树索引的局限性

先看看原系统的索引情况：

问题很明显：

1. 低基数字段（如is_vip、gender）用B+树效率极低
2. 组合查询需要多个索引merge，性能差
3. 内存中的热点数据访问存在性能瓶颈

红黑树：内存索引的不二选择

为什么选择红黑树？

我们对比了几种平衡树：

红黑树在插入删除频繁的场景下，调整次数少，综合性能最好。

红黑树的五个性质

实现前先复习下红黑树的性质：

1. 每个节点要么是红色，要么是黑色
2. 根节点是黑色
3. 所有叶子节点（NIL）是黑色
4. 红色节点的两个子节点都是黑色
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

插入调整的血泪史

红黑树插入后的调整是最复杂的部分。我们碰到的情况：

enum class InsertCase {
    ROOT,           // 情况1：新节点是根
    BLACK_PARENT,   // 情况2：父节点是黑色
    RED_UNCLE,      // 情况3：叔叔是红色
    RED_PARENT_LEFT_CHILD,   // 情况4：父红叔黑，当前是左孩子
    RED_PARENT_RIGHT_CHILD   // 情况5：父红叔黑，当前是右孩子
};

void fixInsert(Node* node) {
    while (node != root && node->parent->color == RED) {
        if (node->parent == node->parent->parent->left) {
            Node* uncle = node->parent->parent->right;
            
            if (uncle && uncle->color == RED) {
                // 情况3：叔叔是红色，变色即可
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->right) {
                    // 情况5：先左旋转换成情况4
                    node = node->parent;
                    leftRotate(node);
                }
                // 情况4：变色+右旋
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                rightRotate(node->parent->parent);
            }
        } else {
            // 镜像情况，左右互换
            // ...
        }
    }
    root->color = BLACK;
}

实际调整的统计数据：

删除调整：比插入还要复杂

删除操作的调整更加复杂，我们遇到了6种不同的情况：

性能测试对比

在内存索引中使用红黑树后的效果：

位图索引：低基数字段的救星

什么时候用位图索引？

通过分析查询日志，我们发现很多查询都是针对低基数字段：

结论：基数小于1000的字段都可以考虑位图索引。

位图索引的实现

核心思想是用bit位表示某行是否满足条件：

class BitmapIndex {
private:
    struct Bitmap {
        vector<uint64_t> bits;  // 每个uint64_t存储64位
        size_t size;
        
        void set(size_t pos) {
            size_t idx = pos / 64;
            size_t offset = pos % 64;
            bits[idx] |= (1ULL << offset);
        }
        
        bool test(size_t pos) const {
            size_t idx = pos / 64;
            size_t offset = pos % 64;
            return bits[idx] & (1ULL << offset);
        }
        
        // 位运算实现集合操作
        Bitmap operator&(const Bitmap& other) const {
            Bitmap result;
            for (size_t i = 0; i < bits.size(); i++) {
                result.bits[i] = bits[i] & other.bits[i];
            }
            return result;
        }
    };
    
    // 每个取值对应一个位图
    unordered_map<string, Bitmap> value_bitmaps;
};

位图索引的空间占用

实际空间占用对比：

位图的压缩算法

原始位图太占空间，我们实现了WAH（Word Aligned Hybrid）压缩：

class CompressedBitmap {
    struct Word {
        uint64_t data;
        bool is_literal;  // true:原始数据 false:行程编码
        
        // 行程编码格式：1位标志 + 1位填充值 + 62位长度
        uint64_t getRunLength() const {
            return data & 0x3FFFFFFFFFFFFFFF;
        }
        
        bool getRunValue() const {
            return (data >> 62) & 1;
        }
    };
    
    vector<Word> words;
};

压缩效果统计：

位图索引的查询优化

位图最强大的是组合查询：

-- 查询：上海地区的VIP男性用户
SELECT * FROM users 
WHERE city = '上海' 
  AND is_vip = 1 
  AND gender = 'M'

执行过程：

1. 获取city='上海’的位图 B1
2. 获取is_vip=1的位图 B2
3. 获取gender='M’的位图 B3
4. 计算 B1 & B2 & B3
5. 根据结果位图获取数据

性能对比：

红黑树 + 位图索引的混合方案

整体架构设计

我们最终设计了一个混合索引系统：

查询路由策略

class QueryRouter {
    QueryPlan route(const Query& query) {
        QueryPlan plan;
        
        // 分析查询条件
        for (const auto& condition : query.conditions) {
            if (isHotData(condition)) {
                plan.addStep(L1_CACHE, condition);
            } else if (isLowCardinality(condition.field)) {
                plan.addStep(L3_BITMAP, condition);
            } else if (isHighSelectivity(condition)) {
                plan.addStep(L4_BTREE, condition);
            } else {
                plan.addStep(L2_MEMORY, condition);
            }
        }
        
        // 优化执行顺序
        plan.optimize();
        return plan;
    }
};

实际查询优化案例

最典型的一个查询优化：

原查询：

SELECT user_id, user_name, last_login 
FROM users 
WHERE city = '上海' 
  AND age_group IN (3,4,5)
  AND is_vip = 1
  AND last_login > DATE_SUB(NOW(), INTERVAL 7 DAY)
ORDER BY last_login DESC
LIMIT 1000

执行计划对比：

性能提升：

• 查询时间：15.3秒 → 0.28秒（提升54倍）
• 扫描行数：4800万 → 1.2万（减少99.97%）
• 内存使用：2.3GB → 150MB（减少93%）

踩坑经验总结

红黑树的坑

1. NIL节点的处理

   // 错误：忘记处理NIL
   if (node->left->color == RED) { } // 可能崩溃
   
   // 正确：先判断是否为NIL
   if (node->left != NIL && node->left->color == RED) { }
   

2. 旋转后的父指针更新

   • 左旋右旋都要更新父指针
   • 根节点变化要特殊处理

3. 并发访问问题

   • 红黑树的调整操作不是原子的
   • 需要细粒度锁或无锁设计

位图索引的坑

1. 更新开销大

   操作	B+树索引	位图索引	说明
   插入一行	O(logn)	O(k)	k是基数
   更新一行	O(logn)	O(2k)	需更新新旧值
   删除一行	O(logn)	O(k)	所有位图都要改

2. 基数变化问题

   • 字段基数增长会导致性能下降
   • 需要监控并及时调整策略

3. 内存占用

   • 未压缩的位图非常占内存
   • 压缩解压需要CPU开销

优化效果总结

经过3个月的优化，系统性能有了质的飞跃：

写在最后

这个项目让我深刻体会到，没有万能的索引结构。红黑树适合内存中的动态数据，位图索引适合低基数的分析查询，B+树适合磁盘存储。关键是理解每种数据结构的特点，在合适的场景使用合适的技术。

还有一点感悟：优化永无止境，但要适可而止。我们曾经尝试过更激进的优化，比如自己实现无锁红黑树，结果bug不断。最后还是选择了成熟稳定的方案。

记住：过早优化是万恶之源，但完全不优化是慢性自杀。在数据量达到一定规模时，选择正确的数据结构和算法，往往能带来数量级的性能提升。

如果你也在做大数据查询优化，欢迎交流！索引优化这条路很深，一起探索总比单打独斗强。