17 | 跳表：为什么Redis一定要用跳表来实现有序集合？-数据结构与算法之美

当前位置:　首页>> 技术小册>> 数据结构与算法之美

### 17 | 跳表：为什么Redis一定要用跳表来实现有序集合？

在深入探讨Redis为何选择跳表（Skip List）作为其有序集合（Sorted Set）的底层数据结构之前，我们首先需要理解有序集合的基本概念、跳表的数据结构特点，以及Redis作为高性能内存数据库对数据结构的特定需求。本章将详细剖析这些方面，从而揭示跳表在Redis有序集合实现中的独特优势。

#### 一、有序集合（Sorted Set）简介

Redis中的有序集合是一种不允许重复成员的数据结构，每个成员都会关联一个分数（score），Redis正是通过分数来为集合中的成员进行从小到大的排序。有序集合提供了丰富的操作接口，如添加、删除成员，以及根据分数范围查询成员等，这些特性使得有序集合在排行榜、实时分析等场景中非常有用。

#### 二、跳表（Skip List）的基本原理

跳表是一种可以替代平衡树的数据结构，它通过在每个节点中维护多个指向其他节点的指针（通常是层数递增的指针），以实现快速的查找、插入和删除操作。跳表通过随机化的方式构建多层索引，使得查找效率可以达到O(log n)的复杂度，与平衡树相当，但实现起来更简单，且无需进行复杂的旋转操作来维持平衡。

**跳表的基本组成包括**：

- **节点**：每个节点包含多层指针，每层指针指向该层上下一个节点。最底层包含所有元素，每向上一层，节点数量逐渐减少。
- **层数**：节点的层数随机生成，通常基于一个概率分布（如幂律分布），确保跳表的平均高度较低。
- **头节点和尾节点**：为了方便操作，跳表通常会包含一个头节点和尾节点，头节点不存储数据，仅作为所有层的起点，尾节点则用于快速定位跳表的末端。

#### 三、Redis选择跳表的原因

##### 1. **实现简单，易于维护**

相较于红黑树、AVL树等自平衡二叉搜索树，跳表的实现更为直观和简单。跳表的核心思想是通过多层索引来加速查找过程，其随机化的层数生成策略保证了数据结构的平衡性，无需像平衡树那样进行复杂的旋转操作来维持树的平衡。这种简单的实现方式降低了出错率，也便于理解和维护。

##### 2. **高效的查找、插入和删除操作**

跳表通过多层索引结构，使得查找、插入和删除操作都能以O(log n)的时间复杂度完成。这对于Redis这样的高性能内存数据库来说至关重要，因为Redis需要频繁地进行这类操作以支持其丰富的数据结构功能。

##### 3. **范围查询性能优异**

有序集合经常需要执行范围查询操作，如查询分数在某个区间内的所有成员。跳表由于其多层索引的特性，可以非常高效地支持这类操作。通过从顶层开始逐层向下遍历，跳表能够快速定位到范围查询的起始和结束位置，然后沿底层链表遍历即可获取所有符合条件的成员。

##### 4. **内存使用高效**

虽然跳表相比单链表等数据结构会占用更多的内存（因为每个节点都可能有多个指针），但相对于其他复杂的数据结构（如平衡树），跳表的内存使用效率并不低。跳表通过随机化的层数控制，可以在保持高效操作性能的同时，尽量减少额外的内存开销。

##### 5. **与Redis的整体设计相契合**

Redis是一个基于内存的键值存储系统，它追求的是高性能和易用性。跳表作为一种简单且高效的数据结构，非常符合Redis的设计哲学。Redis通过提供多种内置的数据结构来简化应用开发，而跳表作为有序集合的底层实现，为Redis用户提供了强大的有序集合操作能力，无需用户自行实现复杂的排序和查找逻辑。

#### 四、跳表在Redis有序集合中的具体应用

在Redis中，有序集合（Sorted Set）通过跳表来实现其有序性和高效的操作性能。每个有序集合成员都会被封装成一个跳表节点，节点中除了存储成员的值外，还会存储一个分数（score），用于排序。跳表的每一层都会根据分数的顺序来组织节点，从而实现对有序集合的快速查找、插入和删除操作。

此外，Redis还为有序集合提供了丰富的命令接口，如`ZADD`（添加成员）、`ZREM`（删除成员）、`ZRANGE`（根据分数范围获取成员列表）等，这些命令的实现都依赖于跳表的高效操作性能。

#### 五、总结

综上所述，Redis选择跳表作为其有序集合的底层实现，是出于其实现简单、操作高效、范围查询性能优异以及内存使用高效等多方面的考虑。跳表不仅满足了Redis对高性能数据结构的需求，也体现了Redis设计哲学中的简洁与高效。通过跳表，Redis为用户提供了强大的有序集合操作能力，使得开发者可以更加轻松地构建出复杂且高效的应用系统。

该分类下的相关小册推荐：

编程之道-算法面试(上)

数据结构与算法(下)

业务开发实用算法精讲

算法面试通关 50 讲

数据结构与算法(上)

编程之道-算法面试(下)

数据结构与算法(中)