2. 缓存索引基础：索引在缓存中的作用、主键索引与二级索引、索引的存储结构

2.1 索引在缓存中的核心作用

在缓存系统中，索引是加速数据检索的核心数据结构。与数据库索引类似，缓存索引通过建立键（Key）到值（Value）或键到元数据的映射关系，将原本需要遍历全量数据的 O(n) 操作降为 O(1) 或 O(log n)。

缓存索引的设计直接影响系统的吞吐量和延迟。一个设计不当的索引可能导致缓存击穿、雪崩或内存浪费。

2.2 主键索引与二级索引

缓存索引按功能可分为主键索引和二级索引，它们在数据组织和查询方式上存在显著差异。

2.3 索引的存储结构

不同的存储结构决定了缓存的查询性能、内存占用和并发能力。以下是三种最常用的索引存储结构。

2.3.1 哈希表（Hash Table）

哈希表是缓存中最基础的索引结构，通过哈希函数将键映射到桶（Bucket）中，实现 O(1) 的平均查找时间复杂度。

• 优点： 读写速度极快，适合等值查询；实现简单，内存开销可控。
• 缺点： 不支持范围查询；哈希冲突时性能退化；扩容时需 rehash，可能引起短暂阻塞。
• 典型应用： Redis 的字典（dict）、Memcached 的哈希表、Java HashMap。

2.3.2 B+ 树（B+ Tree）

B+ 树是一种多路平衡查找树，所有数据都存储在叶子节点，内部节点仅存储键值用于路由。它支持高效的等值查询和范围查询。

• 优点： 范围查询性能优异；树高较低（通常 3~4 层），磁盘 I/O 次数少；数据有序存储。
• 缺点： 写操作需要维护树平衡，开销较大；内存占用高于哈希表。
• 典型应用： MySQL InnoDB 的聚簇索引和二级索引、MongoDB 的 WiredTiger 存储引擎。

2.3.3 跳表（Skip List）

跳表是一种基于链表扩展的概率性数据结构，通过多层索引实现 O(log n) 的查找效率。它结合了链表和二分查找的思想。

• 优点： 实现简单，无需复杂的平衡操作；支持范围查询；并发性能好，适合无锁编程。
• 缺点： 空间开销较大（多层索引指针）；查找性能不如 B+ 树稳定（概率性）。
• 典型应用： Redis 的 ZSET（有序集合）底层实现、LevelDB 的 MemTable。

2.4 三种索引结构的对比总结

2.5 索引结构对比示意图

下图展示了三种索引结构在数据组织方式上的核心差异，帮助理解各自的适用场景。

2.6 索引选择与缓存一致性治理的关系

索引结构的选择直接影响缓存一致性治理的复杂度：

• 哈希表： 失效策略简单，只需删除或更新对应键即可。但无法高效处理“按条件批量失效”的场景。
• B+ 树： 支持范围失效（如删除某个时间范围内的所有缓存），但树结构的更新需要额外的锁机制保证一致性。
• 跳表： 在并发场景下更容易实现无锁更新，适合高写入的缓存系统。但多层索引的同步失效需要精心设计。

2.7 代码示例：Redis 跳表索引实现（简化）

以下代码展示了 Redis 中 ZSET 的跳表索引核心逻辑，用于理解跳表在缓存中的实际应用。

// 跳表节点结构
typedef struct zskiplistNode {
    sds ele;                    // 存储的元素值
    double score;               // 分值（用于排序）
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned int span;             // 跨度
    } level[];                  // 层级数组
} zskiplistNode;

// 跳表结构
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;       // 节点数量
    int level;                  // 当前最大层数
} zskiplist;

// 插入操作（简化）
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL];
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    // 1. 从顶层开始查找插入位置
    // 2. 记录每层需要更新的节点
    // 3. 随机生成新节点的层数
    // 4. 更新各层指针和跨度
    // 5. 更新后退指针
    return newNode;
}