Redis 中的跳跃表是什么

Redis 中的跳跃表（Skiplist）是一种可以替代平衡树的数据结构，它主要用于实现有序集合（Sorted Set）功能。跳跃表通过在多个层级的链表上增加索引来提高查询效率，其效率可以与平衡树相媲美，但实现起来更简单。

跳跃表的基本结构

1. 节点（Node）：每个节点包含多个层（Level），层越高表示该节点在跳跃表中“跳”得越远（即跨度越大）。每层都包含一个指向前一个节点的指针（除了最左侧的第一个节点）和一个指向该层下一个节点的指针（除了最右侧的节点）。

2. 层（Level）：每个节点可以有不同的层数，层数越多，搜索时跳过的节点就越多，搜索效率就越高。但层数也会增加空间消耗。Redis 中通过随机函数来确定每个节点的层数，以保证层数的平均分布。

3. 跨度（Span）：每个节点在同一层中的跨度是指该节点与其前一个节点之间的距离（按节点数计算）。跨度用于计算排名（rank）。

4. 向后指针（Backward Pointer）：部分实现中，每个节点还会有一个指向其“前一个”节点的指针，用于快速进行反向遍历。Redis 的跳跃表实现中包含了此指针。

跳跃表的优势

• 简单：相对于平衡树，跳跃表的实现更简单，更容易理解和实现。
• 插入和删除：跳跃表的插入和删除操作平均时间复杂度为 O(log n)，其中 n 是跳跃表中节点的数量。
• 范围查询：跳跃表支持快速的范围查询操作，即查询某个范围内的所有元素。

Redis 中的跳跃表

Redis 中的有序集合（Sorted Set）是通过跳跃表实现的。除了跳跃表之外，Redis 还为每个有序集合维护了一个字典（Dictionary），字典的键是成员（Member），值是成员的分数（Score）。这样做是为了能够以 O(1) 的时间复杂度进行基于分数的查找操作。

• 插入操作：首先，在字典中插入或更新成员及其分数。然后，在跳跃表中按照分数进行排序插入或更新。
• 删除操作：首先在字典中删除成员，然后在跳跃表中查找并删除对应的节点。
• 范围查询：首先使用字典或跳跃表确定范围的边界，然后在跳跃表中按照分数顺序遍历范围内的所有节点。

总结

Redis 中的跳跃表是一种高效的数据结构，用于实现有序集合的功能。它通过多层级索引来提高搜索效率，同时保持了相对简单的实现。跳跃表在 Redis 的有序集合操作中扮演着核心角色。