02｜Redis 数据对象

1. Redis 的数据类型有哪些？

#

分析

Redis 提供了丰富的数据类型，常见的有五种数据类型：String（字符串）、Hash（哈希）、List（列表）、Set（集合）、Zset（有序集合）。

随着 Redis 版本的更新，后面又支持了四种数据类型：BitMap（2.2 版新增）、HyperLogLog（2.8 版新增）、GEO（3.2 版新增）、Stream（5.0 版新增）。

Redis 五种数据类型的应用场景：

• String 类型：缓存对象、常规计数、分布式锁、共享 session 信息等；
• List 类型：消息队列（但是有两个问题：1. 生产者需要自行实现全局唯一 ID；2. 不能以消费组形式消费数据）等；
• Hash 类型：缓存对象、购物车等；
• Set 类型：聚合计算（并集、交集、差集）场景，比如点赞、共同关注、抽奖活动等；
• Zset 类型：排序场景，比如排行榜、电话和姓名排序等。

Redis 后续版本又支持四种数据类型，它们的应用场景如下：

• BitMap（2.2 版新增）：二值状态统计的场景，比如签到、判断用户登陆状态、连续签到用户总数等；
• HyperLogLog（2.8 版新增）：海量数据基数统计的场景，比如百万级网页 UV 计数等；
• GEO（3.2 版新增）：存储地理位置信息的场景，比如滴滴叫车；
• Stream（5.0 版新增）：消息队列，相比于基于 List 类型实现的消息队列，有这两个特有的特性：自动生成全局唯一消息 ID，支持以消费组形式消费数据。

面试能回答出五种常见的数据类型就可以，其他新的数据类型则需学习。

回答

Redis 支持的数据类型有：

2. Redis 有哪些底层数据结构？

#

分析

数据对象通常指 String、List、Set、Hash、ZSet 这些，它们是用户直接能操作的数据类型，而它们具体实现还依托于底层数据结构，包括 SDS、链表、压缩列表等，回答时列举即可，如果特别熟悉某一种可以专门提出来，引导面试官追问。

回答

数据对象 String、List、Set、Hash、ZSet 的实现都依托于底层数据结构，这些结构包括 SDS、链表、压缩列表、哈希表、跳表等，比如 ZSet 就是利用跳表高效实现了有序集合的能力。

String

#

3. SET 一个已有的数据会发生什么？

#

分析

常用操作考察，答不上来会认为你没用过 Redis。

回答

SET 一个已有数据会覆盖原有的值，同时会覆盖或者擦除键的过期时间。

4. 浮点型在 String 是用什么表示？

#

分析

基础知识考查，只有三种编码模式，INT 只针对整型，所以浮点型必然是字符串存储。

回答

要将一个浮点数放入字符串对象里面，需要先将这个浮点数转换成字符串值，然后再保存转换所得的字符串值。

浮点数在字符串对象里面是用字符串值表示的，用 Raw 还是 Embstr 编码，取决于转换后字符串的长度。

5. String 可以有多大？

#

分析

基础知识考查，需要知道明确的数值，更进一步需要来源背书，再进一步需要思考为什么是这个数值。

回答

一个 Redis 字符串最大为 512MB，官网有明确注明，我看源码里也是直接写死的。

最大存储长度可以通过配置项 proto-max-bulk-len 控制。

6. Redis 字符串是怎么实现的？

#

分析

这个问题，首先需要分情况说出编码类型，分别应用在什么场景。

EMBSTR 编码和 RAW 编码的选择阈值也比较重要，回答的时候，可以先说自己用的 Redis 版本的数值，面试官会感觉你确实有关注过编码的阈值。

如果能记得是 3.2 版本之前是 39，3.2 版本之后才是 44，也可以说出来，有一定程度的加分，但是说了这个差别可能会引导面试官追问为什么，如果记不清就不要说版本差别了。

回答

Redis 字符串底层是 String 对象，String 对象有三种编码方式：INT 型、EMBSTR 型、RAW 型。如果是存一个整型，可以用 long 表示的整数就以 INT 编码存储；如果存字符串，当字符串长度小于等于一个阈值，使用 EMBSTR 编码；字符串大于阈值，则用 RAW 编码。在我用的 5.0.5 版本中阈值是 44。

7. 为什么 EMBSTR 的阈值是 44？（几乎不考）

#

分析

这个问题是上个问题的追问，有以下几个要点：

1. Redis 使用的是 jemalloc 作为内存分配器；
2. jemalloc 是以 64 字节作为内存单元做内存分配，如果超出了 64 个字节就超过了一个内存单元，则会用 RAW 编码；反之，如果小于等于 64 个字节，就认为是一个小字符串，会用到 EMBSTR 编码；
3. 围绕 64 字节的关键分界来分析版本变化，Redis 的字符串对象是由 redisObject 和 sdshdr 这两部分组成，redisObject 大小为 4 + 4 + 24 + 32 + 64 = 128bits = 16bytes，这个是一直没变过的。

// from Redis 3.9.5
#define LRU_BITS 24

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time or
                            * LFU data */
    int refcount;
    void *ptr;
} robj;

回顾 sdshdr 结构：

// from Redis 3.9.5
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

sdshdr 占用的内存大小：1byte + 1byte + 1byte + 内联数组的大小，由于内联数组中还有一个 '\0' 占位一个字节，所以能用的大小为 64 - 16(redisObject) - 3(sdshdr非内容属性) - 1(’\0’) = 44。

回答

Redis 是使用 jemalloc 内存分配器，jemalloc 以 64 字节为阈值区分大小字符串。

所以 EMBSTR 的边界数值，其实是受 64 这个阈值影响。

redisObject 占用的内存大小由 redisObject 和 sdshdr 这两部分组成，redisObject 16 字节，sdshdr 中已分配、已申请、标记三个字段固定占了 3 个字节，'\0' 占了一个字节，能存放的数据就是 64 - (16 + 4) = 44。

8. 你知道为什么 EMBSTR 曾经的阈值是 39 吗？（几乎不考）

#

分析

实际上一般面试官不会主动这么问，一般聊到这个还是因为在上面问题里提到了版本差异。要回答的话，要从 SDS 结构来分析，sdshdr 3.2 之前版本结构如下：

struct SDS {
    unsigned int capacity; // 4byte
    unsigned int len; // 4byte
    byte[] content; // 内联数组，长度为 capacity
}

当时都是通用的 SDS 结构，非数据字段一共占据了 8 个字节，为了节约内存，就在 3.2 版本之后将 SDS 分为 sdshdr5（这个结构不被使用）、sdshdr8、sdshdr16、sdshdr32、sdshdr64，EMBSTR 使用 sdshdr8 节约了 6 个字节，但多引入了一个 flags 字段占据 1 字节，所以相比 3.2 版本之前的 SDS 多了 5 个字节，从这一点也能看出 Redis 也是不断在优化内存和性能的。

回答

3.2 之后的版本，SDS 结构进行了拆分，EMBSTR 用的 sdshdr8，总容量和已使用容量字段减少了 6 个字节，但由于增加了一个 flags 字段，所以最终节约了 5 个字节。

9. SDS 有什么用？

#

分析

Redis 是用 C 语言写的，SDS 可以说是对 C 字符串的封装，一般对比普通 C 字符串。可以从计算长度、扩容、缩容、二进制存储这几个场景来描述。

回答

主要有三点：

1. SDS 包含已使用容量字段，O(1) 时间快速返回字符串长度，相比之下，C 原生字符串需要 O(n)；
2. 有预留空间，在扩容时如果预留空间足够，就不用再重新分配内存，节约性能，缩容时也可以将减少的空间先保留下来，后续可以再使用；
3. 不再以 '\0' 作为判断标准，二进制安全，可以很方便地存储一些二进制数据。

List

#

10. List 是完全先入先出吗？

#

分析

题目所说的完全先入先出，很明显就是指只允许从尾部入队、从头部出队，而 List 是一个双端操作对象，所以不是完全先入先出，他也可以后入先出。

这道题就是考察是否对 LIST 有最基本的认识。

回答

List 是双端操作对象，所以不是完全的先入先出，List 也可以后入先出。

11. List 对象底层编码方式是什么？

#

分析

在 Redis 3.2 版本之前和之后，List 对象的底层编码方式是不同的。面试的时候如果能对不同版本 Redis 的 List 对象底层编码方式做出分析，是一个加分项。

回答

在 3.2 版本之前，List 对象的编码是 ZIPLIST 和 LINKEDLIST。ZIPLIST 适用于元素数量较少、且元素都较短的情况，否则用 LINKEDLIST。

3.2 版本之后，List 对象的编码全部由 QUICKLIST 实现。QUICKLIST 是一个压缩列表组成的双向链表，结合了 ZIPLIST 和 LINKEDLIST 两者的优点，在后面比较新的版本（Redis 7.0）中 ZIPLIST 优化为了 LISTPACK。

12. ZIPLIST 是怎么压缩数据的？

#

分析

这个问题就是对 ZIPLIST 数据结构本身的考察。ZIPLIST 是为了节约内存而开发的，回答这个问题可以从 ZIPLIST 的结构入手。ZIPLIST 的结构如下：

* The general layout of the ziplist is as follows:
*
* <zlbytes> <zltail> <zllen> <entry> <entry> .. <entry> <zlend>

其中 entry 结构为：

<prevlen> <encoding> <entry-data>

为了方便记忆和理解，可以将 ZIPLIST 分为三部分讲述：

1. 结构头，即 header，包括 <zlbytes>、<zltail>、<zllen> 字段；
2. 数据部分，即 entry 列表，entry 中有 <prevlen>、<encoding>、<entry-data> 字段；
3. 结尾标识，即 zlend。

回答

压缩列表是一块连续的内存空间，元素之间是紧挨着存储的，一个压缩列表中可以包含多个节点（entry），是在连续的内存空间上实现的双端链表。

对于一个普通的双向链表，链表中每一项都占用独立的一块内存，各项之间用地址指针（或引用）连接起来。这种方式会带来大量的内存碎片，而且地址指针也会占用额外的内存。而 ziplist 却是将表中每一项存放在前后连续的地址空间内，一个 ziplist 整体占用一大块内存。

而且 ziplist entry 对于不同类型会有不同长度的数据存储，保证尽可能地压缩内存。

13. ZIPLIST 下 List 可以从后往前遍历吗？

#

分析

首先，一切的基石，在于要知道 List 是一种双端数据结构，无论哪种底层编码，都需要能支持从后往前遍历。

接着，需要阐述 ZIPLIST 是如何做到从后往前遍历的，其实还是在考察 ZIPLIST 的数据结构。

ZIPLIST 下 entry 的结构包含了上一个节点的长度，所以可以通过上一个节点的长度，找到上个节点的起始位置，这样就能实现从后往前遍历。

回答

可以，List 是双端数据结构，无论哪种底层编码，都需要能支持从后往前遍历。ZIPLIST 每个节点中都保存了上一个节点的长度，所以可以用当前节点地址减去上一个节点长度来找到上个节点起始位置，进而实现从后往前的遍历。

14. 在 ZIPLIST 数据结构下，查询节点个数的时间复杂度是多少？

#

分析

由于 ZIPLIST 的 header 中定义了记录节点数量的字段 zllen，所以通常是可以 O(1) 时间复杂度直接返回，为什么说通常呢？是因为 zllen 是 2 个字节的，当 zllen 大于 65535 时，zllen 就存不下了，所以真实的节点数量需要遍历来得到。

回答

在 ZIPLIST 编码下，查询节点个数的时间复杂度是 O(1)，因为 ZIPLIST 中的 header 定义了记录节点数量的字段，但是这里也有个限制，记录节点数量的字段只有 2 字节，也就说如果节点数量超过 65535，就失效了，此时只能通过 O(n) 复杂度的遍历来查节点总数。

15. LINKEDLIST 编码下，查询节点个数的时间复杂度是多少？

#

分析

这个问题我们可以回顾一下 LINKEDLIST 的表头结构：

// from Redis 5.0.5
typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

LINKEDLIST 的表头结构中定义了链表所包含节点数量的字段 len，所以 LINKEDLIST 编码下，查询节点个数的时间复杂度是 O(1)。

回答

LINKEDLIST 编码下，查询节点个数的时间复杂度是 O(1)。因为 LINKEDLIST 的表头结构中定义了链表所包含节点数量的字段 len。

Set

#

16. Set 编码方式？

#

分析

Set 底层使用了两种编码，一种是整数集合，另一种是字典。成员的数据结构和成员数量会触发 Set 更改底层编码，当 Set 同时满足元素都是整数且元素个数不超过 512 这两个条件，会使用整数集合编码，否则使用字典编码。

回答

Set 使用整数集合和字典作为底层编码，当元素都是整数同时元素个数不超过 512 个，会使用整数集合编码，否则使用字典编码。

17. Set 是有序的吗？

#

分析

Set 的底层实现是整数集合或字典，前者是有序的，后者是无序的。

回答

Set 的底层实现是整数集合或字典，前者是有序的，后者是无序的。整体来看，但是不应该依赖 SET 的顺序，业务使用适合始终应该按无序来用。

18. Set 为什么要用两种编码方式？

#

分析

我们可以从编码转换的条件来进行思考，Set 的底层编码从 INTSET 到 HASHTABLE 的条件是元素个数或者元素类型的变化。所以采用两种编码方式的原因是 INTSET 更节约内存，所以在小数据量时使用，而数据多起来了，需要 HASHTABLE 的查找性能。

实际上如果 Set 中保存的所有元素都是整数，而且元素个数不是特别多的情况下，使用 intset 会比较节约内存，Redis 用一个含有三个字段的结构体来表示 intset，分别是编码方式、元素数量和实际存储元素的有序柔性数组：

typedef struct intset {
    uint32_t encoding;   // 编码格式
    uint32_t length;     // 元素数量
    int8_t contents[];   // 保存元素的数组
} intset;

intset 用来保存元素的数组默认情况下是 int16 编码，后续如果插入更大的整数，才会升级到 int32 或者 int64 编码。这种策略可以尽可能的节约内存以及提升整数集合的灵活性。

但是升级也有弊端，升级之后，整个数组的编码会变成与最大元素的类型一致。假如这个时候，元素的数量非常多，就不那么节约内存了，而且数组查找的平均时间复杂度是 \(O(\log n)\)，不如使用字典编码。

回答

Set 的底层编码是整数集合和字典，当元素数量小并且全部是整数的时候，会使用整数集合编码，更加的节约内存。元素数量变大会使用字典编码，查找元素的速度会更快。

Hash

#

19. Hash 的编码方式是什么？

#

分析

Hash 底层有两种编码结构，一个是 ZIPLIST，一个是 HashTable。ZIPLIST 适用于元素较少且单个元素长度较小的情况，这里的阈值分别是元素个数少于 512 个，值和键长度都小于 64 字节。

回答

一个是 ZIPLIST，一个是 HashTable。ZIPLIST 适用于元素较少且单个元素长度较小的情况，其它情况使用 HashTable。

20. Hash 查找某个 key 的平均时间复杂度是多少？

#

分析

这种问对象复杂度的，要考虑多种底层编码。ZIPLIST 需要遍历，平均复杂度为 \(O(N)\)，HashTable 是字典，可以 \(O(1)\) 找到对应 key。

回答

Hash 有两种底层结构，ZIPLIST 时是 \(O(N)\)，HashTable 则是 \(O(1)\)。

21. Redis 中 HashTable 查找元素总数的平均时间复杂度是多少？

#

分析

这题考察的是 Redis 字典的表头结构，如果表头结构中有储存键值对个数的字段，那么查找元素总数的平均时间复杂度就是 \(O(1)\)，而如果没有这个字段，那字典就需要去遍历所有的键值对。

下面是 Redis 字典的表头结构：

// from Redis 5.0.5
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    // 键值对数量
    unsigned long used;
} dict_t;

可以发现字典的表头结构中的 used，就记录了当前键值对数量的字段。

回答

HashTable 查找元素总数的平均时间复杂度是 \(O(1)\)，因为 HashTable 的表头结构中有储存键值对数量的字段，这个字段我记得叫 used。

22. 一个数据在 HashTable 中的存储位置，是怎么计算的？

#

分析

当一个新的键值对要插入到 HashTable 中时，首先会使用哈希函数计算这个 key 的哈希值，Redis 使用的哈希算法是 MurmurHash2 哈希算法，然后把哈希值和哈希掩码做与运算得到索引值，哈希掩码其实就是哈希表数组的大小减去 1。然后程序会根据索引值把键值对插入到相应的位置。

回答

首先会通过哈希函数计算出 key 的哈希值，然后与哈希掩码做与运算得到索引值，索引值就是这个数据在 HashTable 中的存储位置。

23. HashTable 怎么扩容？

#

分析

HashTable 的扩容通过渐进式 rehash 操作来完成。

回答

首先程序会为 HashTable 的 1 号表分配空间，空间大小是第一个大于等于 0 号表大小 * 2 的 \(2^n\)。在 rehash 进行期间，标记位 rehashidx 从 0 开始，每次对字典的键值对执行增删改查操作后，都会将 rehashidx 位置的数据迁移到 1 号表，然后将 rehashidx 加 1，随着字典操作的不断执行，最终 0 号表的所有键值对都会被 rehash 到 1 号表上。之后，1 号表会被设置成 0 号表，接着在 1 号表的位置创建一个新的空白表。

24. HashTable 怎么缩容？

#

分析

HashTable 的缩容也通过渐进式 rehash 操作来完成。

回答

首先程序会为 HashTable 的 1 号表分配空间，新表大小为第一个大于等于原表 used 的 2 次幂。在 rehash 进行期间，标记位 rehashidx 从 0 开始，每次对字典的键值对执行增删改查操作后，都会将 rehashidx 位置的数据迁移到 1 号表，然后将 rehashidx 加 1，随着字典操作的不断执行，最终 0 号表的所有键值对都会被 rehash 到 1 号表上。之后，1 号表会被设置成 0 号表，接着在 1 号表的位置创建一个新的空白表。

25. HashTable 什么时候扩容，什么时候缩容？

#

分析

这是问扩容时机，HashTable 的扩容与缩容由哈希表的负载因子决定，负载因子 = 键值对数量 / 哈希表大小。

回答

我先说扩容，当以下两个条件中的任意一个被满足时，哈希表会自动开始扩容：

• 第一个是服务器目前没有在执行 BGSAVE 或者 BGREWRITEAOF，并且负载因子 >= 1；
• 第二个是服务器目前正在执行 BGSAVE 或者 BGREWRITEAOF，并且负载因子 >= 5。

缩容的话也是负载因子影响，当哈希表的负载因子小于 0.1 时，程序会自动开始对哈希表进行收缩操作。

ZSet

#

26. ZSet 底层有几种编码方式？

#

分析

ZSet 即有序列表，这个问题是基础知识考查，ZSet 的底层编码可以是 ziplist 或者 skiplist + 字典，需要分情况说出不同的编码类型。

ziplist 和 skiplist + 字典 编码的选择阈值不一定可以记得清，记不清说大概是 128 或者 256 也可。

当有 ZSet 对象可以同时满足以下两个条件时，对象使用 ziplist 编码：

• ZSet 保存的元素数量小于 128 个；
• ZSet 保存的所有元素成员的长度都小于 64 字节。

不能满足以上两个条件的有序集合对象将使用 skiplist + 字典 编码。

回答

ZSet 就是有序集合对象，ZSet 对象的底层有两种编码方式：ziplist 或者 skiplist + 字典。

如果一个 ZSet 对象中的所有元素同时满足：元素数量小于 128 个 以及 所有元素成员的长度都小于 64 字节，那么会使用 ziplist 编码，否则使用 skiplist + 字典 编码。

27. 跳表编码模式下，查询节点总数的平均时间复杂度是多少？

#

分析

这个问题是对 Redis 跳表数据结构的考察，首先我们可以想想跳表的表头结构：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    // 节点数量
    unsigned long length;
    int level;
} zskiplist;

跳表的表头结构中定义了保存节点数量的字段 length，所以对 Redis 跳表查询节点总数的平均时间复杂度应该为 \(O(1)\)。我们也可以进一步查看相关的 API 底层源码：

unsigned int zsetLength(robj *zobj) {
    int length = -1;
    // zset 下 ZIPLIST 节点数在 128 以内，一定 < 65535，所以也是 O(1)
    if (zobj->encoding == REDIS_ENCODING_ZIPLIST) {
        length = zzlLength(zobj->ptr);
    // O(1)
    } else if (zobj->encoding == REDIS_ENCODING_SKIPLIST) {
        length = ((zset*)zobj->ptr)->zsl->length;
    } else {
        redisPanic("Unknown sorted set encoding");
    }
    return length;
}

查询有序集合成员总数的 API 是 zsetLength，而当编码模式是 REDIS_ENCODING_SKIPLIST，源码中会直接返回跳表表头结构的 length 字段，平均时间复杂度是 \(O(1)\)。

回答

跳表编码模式下，查询节点总数的平均时间复杂度是 \(O(1)\)，因为跳表的表头结构中定义了一个保存节点数量的字段 length，源码中调用查询节点总数的 API 时会直接返回这个字段。

28. 跳表插入一条数据的平均时间复杂度是多少？

#

分析

这个问题同样是对跳表这种数据结构本身的考察，跳表实际上就是在一维链表上建立多层索引的二维链表，多出来的层数可以让跳表实现类似二分查找的算法。所以跳表的插入平均时间复杂度是 \(O(\log n)\)。

回答

跳跃表是一种支持多级索引的结构，查询效率可以媲美二分查找，它插入一条数据也是需要先查找，找到之后会进行索引的重建，整体平均时间复杂度是 \(O(\log N)\)。

29. 为什么跳表和 HashTable 要配合使用？

#

分析

使用了两种数据结构来实现自然是为了让有序集合拥有这两种数据结构的优势。可以结合跳表和字典相较于各自的优势来进行回答。

回答

为了结合这两种数据结构各自的优势，当 ZSet 要根据成员来查找分值的时候，将使用字典来实现，时间复杂度为 \(O(1)\)。而当 ZSet 要执行范围操作时，比如 ZRANK、ZRANGE 等命令时，将使用原本就有序的跳跃表来实现。

30. 跳表中一个节点的层高是怎么决定的？

#

分析

这个问题是对跳表这种数据结构本身的考察，跳表中插入一个节点之前会选择一个随机化的层数，因为如果跳表的层数从下至上呈一定的比例关系，那么后期插入和删除的时候就需要去维护这种比例关系，会使时间复杂度退化。所以跳表选择在插入节点的时候，选择一个随机化的层数。

但是生成的随机层数得遵循一个算法，使得生成小数值层数的概率很大，而生成大数值层数的概率很小，这个算法就是幂次定律。跳表在插入新节点之前，会利用这个幂次定律算法生成一个随机层数。

回答

跳表在插入新节点之前会计算一个随机的层高，具体来说，跳表的每一个节点一开始默认都是 1 层，然后每增加一层的概率都是 25%，最高为 32 层。

31. zset 为什么用跳表而不用平衡树？

#

分析

对于这个问题，Redis 的作者 @antirez 是怎么说的：

There are a few reasons:

1. They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
2. A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
3. They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

简单翻译一下，主要是从内存占用、对范围查找的支持、实现难易程度这三方面总结的原因：

• 它们不是非常内存密集型的。基本上由你决定。改变关于节点具有给定级别数的概率的参数将使其比 btree 占用更少的内存；
• Zset 经常需要执行 ZRANGE 或 ZREVRANGE 的命令，即作为链表遍历跳表。通过此操作，跳表的缓存局部性至少与其他类型的平衡树一样好；
• 它们更易于实现、调试等。例如，由于跳表的简单性，我收到了一个补丁（已经在 Redis master 中），其中扩展了跳表，在 \(O(\log N)\) 中实现了 ZRANK。它只需要对代码进行少量修改。

回答

• 跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗；
• 跳表的代码实现比平衡树来说，实现要简单多了，平衡树插入和删除都会导致树的旋转，实现起来很复杂，而跳表就简单很多，跳表插入就比普通的链表插入节点稍复杂一点；
• 按照区间来查找数据这个操作（比如查找值在 [100, 200] 之间的数据），平衡树的效率没有跳表高。对于按照区间查找数据这个操作，跳表可以做到 \(O(\log n)\) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了，这样做非常高效。

总体来说，主要是为了代码的简单、易读、不容易出错，比起平衡树复杂性，Redis 选择了跳表。