跳到主要内容

Redis 数据结构

1. Redis 的数据结构与使用场景​

虽然已经提到了 Redis 最常见的使用场景是缓存，但是不同场景下，对于缓存的需求也不尽相同。

好在，Redis 提供了丰富的数据结构，以便满足不同场景的不同需求。

Redis 支持的全部数据结构可以在 Redis 官方文档 中查看。本文暂时先只介绍面试中常见的数据结构。

2. 字符串​

Redis 作为「键值对」数据库，最基本的结构就是「字符串」，除了字符串之外，还可以用来存储数值类型甚至二进制数据。

字符串类型内部的实现可以理解成一个 「HashTable」。

另外还做了一些优化：

  1. 数字类型支持自增、自减
  2. 使用 「SDS（Simple Dynamic String）」 代替了传统的 C 语言字符串，避免了字符串的拼接、扩容等操作带来的性能损耗
  3. 使用 jemalloc 内存分配器，有效减少了内存碎片

最常见的使用场景就是缓存热点信息等。

3. 列表​

Redis 的列表类型内部的实现可以理解为「双向链表」，支持从头部或尾部插入和删除元素。显然，列表类型可以作为队列来使用。

通过 LPOP、RPOP、RPUSH、LPUSH 等命令，可以「FIFO（先进先出）」或「LIFO（后进先出）」的队列。

虽然列表的实现类似双向链表，但是 Redis 还是做了很多优化，实际上使用了 「QuickList」 来实现。

QuickList 是结合了 LinkedList 和 ZipList 的产物。

  • LinkedList：类似传统链表，节点不需要保存在连续的空间上，可以方便的扩展长度
  • ZipList：一种压缩链表，更类似数组，节点保存在连续的空间上，相比 LinkedList 有更快的遍历效率

在　Redis 中，LinkedList 的每个节点都保存了一个 ZipList，而 ZipList 的每个节点都保存了实际的数据。

在遍历列表元素时，因为虽然也要遍历 LinkedList 的每一个节点，但是因为每个节点内部的数据是通过 ZipList 保存的，所以遍历的效率比只使用 LinkedList 要高。

在插入或者删除元素时，可能会导致 ZipList 的节点被拆分或者合并，因此 ZipList 的节点数量会发生变化。

删除时，如果 ZipList 节点的数量少于阈值（默认的一半），同时两侧也存在节点数量小于阈值的节点，则会将这些节点合并为一个节点。

插入时，如果 ZipList 节点数量大于阈值，则从当前节点中间分裂，形成两个新的 ZipList， 再去将新元素插入到其中一个 ZipList 中。

4. 有序集合​

有序集合是 Redis 中很有特色的数据结构，它会为集合中的每一个元素设置一个 「分数（Score）」，然后根据分数对元素进行排序。

按照分数排序的特征，使得 Redis 的有序集合可以用作排行榜等场景。

有序集合的内部实现就是大名鼎鼎的「跳表（SkipList）」。

跳表的原理类似平衡树，通过分层的方式，从高到低，逐渐缩小查询范围，从而提升查询效率。

  1. 首先在跳表的最底层，会保存所有的元素，是一个完整的双向链表结构
  2. 链表中的每一个节点，都有一定的概率晋升到上一层。假设晋升的概率是 1/2，那么每向上一层，节点的数目会减少一半
  3. 跳表会维护一个最大的层数，如果超过这个层数，则不会继续晋升

下面展示一个简单的 3 层跳表的示例：

Level 2: [4] -> [8]
Level 1: [2] -> [4] -> [6] -> [8] -> [10]
Level 0: [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> [8] -> [9] -> [10]

查询时，从最高层开始，比如查询 5:

  1. 首先查询最高层 Level 2，发现4 < 5，8 > 5，那么查询的范围在[4, 8]之间
  2. 继续查询 Level 1，只需查询 [4, 8] 范围内的元素，发现4 < 5，6 > 5，那么查询的范围在[4, 6]之间
  3. 继续查询 Level 0，只需查询 [4, 6] 范围内的元素，发现5 = 5，找到目标元素

可以发现，为了找到 5， 需要比较 [4]、 [8]、 [6]、 [5] 这 4 个元素，即可找到目标元素；而传统的链表，也就是最底层，需要比较从 1-5 的所有元素才能找到目标值。跳表的方案减少了 1 次比较次数，而减少的次数随着元素的增加会更加明显。

跳表的内部实现也很精巧。

  1. 跳表的核心是一个双向 LinkedList，列表中每一个节点都会保存指向前后节点的指针
  2. 每一个节点还会保存一个 level[] 数组，保存了当前节点的层级信息。比如上述例子中，节点 [4] 的 level[] 就会保存每一层的信息，包括指向同一层级的前后节点的指针
  3. 为了方便遍历每一层，跳表还会为每一层维护一个虚拟的头节点，作为每一层遍历的起点
  4. 查询时，从最高层开始，如果当前节点小于目标值，下一个节点大于目标值，则继续往下层查询，直到找到目标值
  5. 插入时，会随机生成一个层数，然后从最高层开始，找到插入位置，逐层插入
  6. 删除时，会先找到需要删除的节点，然后逐层删除，调整每一层的前后节点的指针，最终完成删除的操作

因为跳表每一层的节点数量都是指数级减少的，因此查询的时间复杂度为 O(logN)，高于普通链表的 O(N)。