Redis常见面试题：ZSet底层数据结构，SDS、压缩列表ZipList、跳表SkipList

Redis 是一款开源的，内存中的数据结构存储系统，它可以用作数据库、缓存和消息代理。Redis 支持多种类型的数据结构，如字符串（String）、哈希（Hash）、列表（List）、集合（Set）、有序集合（Sorted Set）、位图（Bitmap）、HyperLogLog 和地理空间索引（Geospatial）。这些数据结构提供了丰富的操作，使得 Redis 能够应对各种各样的场景。本文将详细介绍 Redis 的各种数据结构，包括它们的特性、底层实现、常用命令以及应用场景。

一、Redis数据结构概述

1.1 Redis有哪些数据类型

Redis是一个key-value的数据库，key一般是String类型，不过value的类型多种多样：包含 6 种基本类型——String（字符串）、List（列表）、Hash（哈希）、Set（集合）、Sorted Set（有序集合）、Stream（流、Redis5.0引入），和三种特殊类型——geospatial（地理位置）、Bitmap（位存储）、HyperLog（基数统计）。

数据结构的底层实现：底层数据结构一共有 6 种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。

从上图可以看出：String 的底层是简单动态字符串；List 的底层是双向链表和压缩链表；Set 的底层是整数数组和哈希表；Hash 的底层是压缩链表和哈希表；Sorted Set 底层压缩链表和跳表。即 String 类型的底层实现只有一种数据结构，也就是简单动态字符串。而 List、Set、Hash 和 Sorted Set这四种数据类型，都有两种底层实现结构。通常情况下，我们会把这四种类型称为集合类型，它们的特点是一个键对应了一个集合的数据。

Redis 之所以采用不同的数据结构，其实是在性能和内存使用效率之间的平衡。

1.2 Redis本质是哈希表

Redis 本身是一个键值对数据库，这种键值对的存储方式就是哈希映射（Hashmap）的一种体现，即通过键（Key）来快速查找对应的值（Value）。

• 一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。也就是说，一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据；
• 不管是键类型还是值类型，哈希桶中的元素保存的都不是值本身，而是指向具体值的指针

根据下图可看出，哈希桶中的 entry 元素中保存了 ‘*key’ 和 '*value ’ 指针，分别指向了实际的键和值，这样一来，即使值是一个集合，也可以通过 '*value 指针被查找到：

因为这个哈希表保存了所有的键值对，所以它也叫做全局哈希表。

• 哈希表的最大好处是可以用 O(1) 的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值，就可以知道它对应的哈希桶位置，然后就可以访问相应的 Entry元素；

• 这个查找过程主要依赖于哈希计算，和数据量的多少并没有直接关系。也就是说，不管哈希表里有 10 万个键还是 100 万个键，我们只需要一次计算就能找到相应的键。

也就是说，整个数据库就是一个全局 Hash 表，而 Hash 表的时间复杂度就是 O(1)，只需要计算每个键的 Hash 值，就知道对应的 Hash 桶位置，定位桶里面的 Entry 找到对应数据，这个也是 Redis 快的原因之一。

但如果我们只是了解哈希表 O(1) 复杂度和快速查找特性，那么当我们向 Redis 中写入大量数据之后，就可能发现 操作有时候会突然变慢了。原因是哈希表的冲突问题和 rehash 可能带来的操作阻塞。

1.3 Redis的哈希冲突与渐进式rehash

Redis 使用哈希表作为其底层数据结构，哈希冲突是哈希表中常见的问题。当两个或更多的键被哈希函数映射到同一个哈希桶时，就会发生哈希冲突。Redis 通过链地址法来解决哈希冲突，即在每个哈希桶中维护一个链表，所有哈希到同一个桶的键值对都存储在这个链表中。

当哈希表中的元素数量增长到一定程度，或者哈希表中的元素数量减少到一定程度，Redis 会触发哈希表的扩容或收缩，这个过程称为 rehash。为了避免 rehash 过程中一次性复制所有元素导致的长时间阻塞，Redis 使用了一种称为“渐进式 rehash”的策略。

在渐进式 rehash 过程中，Redis 会同时维护新旧两个哈希表，并在每次对哈希表进行操作时，将一部分桶从旧哈希表移动到新哈希表。同时，为了保证查询操作的正确性，Redis 在查询时会同时查找新旧两个哈希表。这样，通过分摊在一段时间内完成 rehash，避免了一次性操作带来的性能问题。

1.4 数据结构底层

1.4.1 简单动态字符串SDS

我们都知道Redis中保存的Key是字符串，value往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种
数据结构。

不过Redis没有直接使用C语言中的字符串，因为C语言字符串存在很多问题。在C语言中定义字符串 char *str = "message"，本质是字符数组 {‘m’, ‘e’, ‘s’, ‘s’, ‘a’, ‘g’, ‘e’, ‘\0’}。它会存储如下图的样子：

以“\0”代表结束。这样就会产生以下问题：

1. 无法存储“\0”这种特殊字符，因为“\0”代表结束（非二进制安全）；
2. 每次字符串扩容和缩容，都需要使用新的char数组；
3. 没有记录字符串的长度，每次都需要进行遍历到结束、或者通过运算 才能知道长度。
4. 不可修改

Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称SDS。（Redis是C语言实现的）

例如我们执行命令：set name 大哥，那么Redis将在底层创建两个SDS，其中一个是包含“name”的SDS，另一个是包含“大哥”的SDS。

SDS优点：

• 获取字符串长度的时间复杂度为O(1)
• 支持动态扩容
• 减少内存分配次数
• 二进制安全。遍历字符串时不是以介绍标识为标记、而是以长度为基准，

• len：目前已使用的长度；
• alloc：buf的总长度，就是已经分配空间的长度;
• flags：sds的类型，用低三位标识，高5位暂时不用。sdshdr5这种类型该字段为空；sdshdr8、sdshdr16、sdshdr32、sdshdr64用标识进行表示。
• buf：保存具体的字符串。注意这里也会以\0结尾，但它不会计算在len中。

1.4.2 双向链表（后续已废弃）

1.4.3 压缩列表ZipList

ZipList是一种特殊的“双端链表”（并非链表），由一系列特殊编码的连续内存块组成，像内存连续的数组。可以在任意一端进行压入/弹出操作，并且该操作的时间复杂度为O(1)。

压缩列表 底层数据结构：本质是一个数组，增加了列表长度、尾部偏移量、列表元素个数、以及列表结束标识，有利于快速寻找列表的首尾节点；但对于其他正常的元素，如元素2、元素3，只能一个个遍历，效率仍没有很高效。

注意：

• 如果查找定位首个元素或最后1个元素，可以通过表头 “zlbytes”、“zltail_offset” 元素快速获取，复杂度是 O(1)。但是查找其他元素时，就没有这么高效了，只能逐个查找下去，比如 entryN 的复杂度就是 O(N)

• ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请效率较低。

1.4.4 哈希表HashTable

Redis 的散列表（hashtable）是一种常见的键值对映射结构，它通过一个散列函数将键映射到一个桶中，然后在桶中进行查找。Redis 的散列表使用链表法解决哈希冲突，即当多个键映射到同一个桶时，将它们存储在同一个链表中。

在Redis的源代码中，散列表的结构定义如下：

typedef struct dictEntry {
    void *key;
    void *val;
    struct dictEntry *next;
} dictEntry;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

其中：

• dictEntry 结构体表示散列表中的一个节点，包含键（key）、值（val）和指向下一个节点的指针（next）。

• dictht 结构体表示一个散列表，包含指向哈希表数组的指针（table）、哈希表数组的大小（size）、哈希表数组大小掩码（sizemask）和已使用的节点数量（used）。

• dict 结构体表示一个字典，包含两个散列表（ht）、当前进行 rehash 的索引（rehashidx）和当前运行的迭代器数量（iterators）。

1.4.5 跳表SkipList

**SkipList（跳表）**首先是链表，在链表的基础上，增加了多级索引，通过多级索引位置的转跳，实现了快速查找元素。但与传统链表相比有几点差异：

• 元素按照升序排列存储
• 节点可能包含多个指针，指针跨度不同

普通链表想查找元素27，只能从链表头部一个个往后遍历，需要遍历6次 才能找到元素27

跳表怎么做的（how）：建立多级索引

如建立一级索引

如果觉得慢，可以建立二级索引

当数据量特别大的时候，跳表的时间复杂度为 O(logN)。其本身利用的思想，有点类似于二分法。

SkipList的特点：

• 跳跃表是一个双向链表，每个节点都包含score和ele值
• 节点按照score值排序，score值一样则按照ele字典排序
• 每个节点都可以包含多层指针，层数是1到32之间的随机数
• 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
• 增删改查效率与红黑树基本一致，实现却更简单

1.4.6 整数数组IntSet

IntSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。

（int8_t int表示整数、8表示8bit位，即1个字节）

为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中，结构如图：

IntSet升级

现在，假设有一个intSet，元素为{5,10，20}，采用的编码是INTSET_ENC_INT16，则每个整数占2字节：

我们向该其中添加一个数字：50000，这个数字超出了int16_t的范围，intset会自动升级编码方式到合适的大小。以当前案例来说流程如下：

1. 升级编码为INTSET_ENC_INT32，每个整数占4字节，并按照新的编码方式及元素个数扩容数组
2. 倒序依次将数组中的元素拷贝到扩容后的正确位置
3. 将待添加的元素放入数组末尾
4. 最后，将inset的encoding属性改为INTSET_ENC_INT32，将length属性改为4

1.4.7 RedisObject

Redis中的任意数据类型的键和值都会被封装为一个RedisObject，也叫做Redis对象，源码如下：

1.4.8 Redis的编码方式

Redis中会根据存储的数据类型不同，选择不同的编码方式，共包含11种不同类型：

五种数据结构

Redis中会根据存储的数据类型不同，选择不同的编码方式。每种数据类型的使用的编码方式如下：

二、String类型

详细介绍：Redis五种数据类型、String、List、Set、Hash、ZSet

String 是 Redis 最简单的数据类型，也是最常用的数据类型。它可以包含任何数据，包括字符串、整数或者浮点数。在 Redis 中，字符串的最大长度可以达到 512MB。

应用场景：

• 缓存：将查询结果、页面内容等缓存在 Redis 的 String 结构中，提高系统访问速度。
• 计数器：Redis String 结构可以将字符串解析为整数进行自增或自减操作，适合做各种计数器。
• 分布式锁：利用 Redis String 结构的原子性操作，可以实现分布式锁。

底层结构：Redis 的 String 类型是二进制安全的，基于简单动态字符串（SDS）实现，它的底层实际上是一个字节数组，因此 String 类型可以包含任何数据，例如 jpg 图片或者序列化的对象。

在Redis实现中并没有直接采用C语言的字符串，而是自定义了一个SDS（简单动态字符串）的结构体来标识字符串。

在C语言中定义字符串 char *str = "message"它会存储如下图的样子：

以“\0”代表结束。这样就会产生以下问题：

1. 无法存储“\0”这种特殊字符，因为“\0”代表结束；
2. 每次字符串扩容和缩容，都需要使用新的char数组；
3. 没有记录字符串的长度，每次都需要进行遍历到结束才能知道长度。

redis要解决上述问题，就自定义了一个SDS结构，如下图：

• len：目前已使用的长度；
• alloc：buf的总长度，就是已经分配空间的长度;
• flags：sds的类型，用低三位标识，高5位暂时不用。sdshdr5这种类型该字段为空；sdshdr8、sdshdr16、sdshdr32、sdshdr64用标识进行表示。
• buf：保存具体的字符串。注意这里也会以\0结尾，但它不会计算在len中。

redis可以根据字符串的大小使用不同类型的sds，这样可以进一步的节省内存。这里不需要担心buf的长度不够用，2的64次幂是一个非常巨大的数字，同时redis默认也会限制最大的字符为512M，在6.3版本开始可以对最大限制字符大小进行配置。注意：使用不同类型的sds并不是一次性分配这么多空间，而是逐步分配的，例如：使用sdshdr16这种类型，存入一个长度为14的字符串，那么会根据存入的字符串长度预留空闲长度，这里是14；如果字符串大小超过1M，那么预留空间就是1M。

redis除了自定义了SDS类型来存储字符串，还定义了三种编码：

• int：8字节的长整形，值时数字类型，并且数字长度小于20；
• embstr：长度小于等于44字节的字符串；（3.2版本之前是39字节）
• raw：长度大于44字节的字符串。

三、List列表类型

3.1 简介

详细介绍：Redis五种数据类型、String、List、Set、Hash、ZSet

Redis中的List类型与Java中的LinkedList类似，可以看做是一个双向链表结构，按插入顺序排序，你可以添加一个元素到头部（左边）或尾部（右边）。既可以支持正向检索和也可以支持反向检索。特征也与LinkedList类似：有序、元素可重复、插入和删除快、查询速度一般。在 Redis 中，列表最多可以包含 2^32 - 1 个元素。

应用场景：

• 消息队列：可以利用 List 的 push 和 pop 操作，实现生产者消费者模型。
• 时间线、动态消息：比如微博的时间线，可以将最新的内容放在 List 的最前面。
• 常用来存储一个有序数据，例如：朋友圈点赞列表，评论列表等

底层结构：

• 在3.2版本之前，Redis List底层采用压缩链表ZipList和双向链表LinkedList来实现List。当元素数量小于512并且元素大小小于64字节时采用ZipList编码，超过则将自动采用LinkedList编码
• 在3.2版本之后，Redis统一采用快速链表QuickList来实现List

3.2 数据结构

Redis的List结构类似一个双端链表，可以从首、尾操作列表中的元素：

• 在Redis 3.2版本之前，Redis List底层采用压缩链表ZipList和双向链表LinkedList来实现List。当元素数量小于512个并且元素大小小于64字节时采用ZipList编码，超过则将自动采用LinkedList编码。
• 在3.2版本之后，Redis统一采用快速链表QuickList结构来实现List

QuickList结构如下：

在 Redis3.2 版本前，Redis 列表 List 使用两种数据结构作为底层实现：

• 压缩列表 ZipList：插入元素过多或字符串太大，就需要调用 Realloc 扩展内存；
• 双向链表 LinkedList：需附加指针 Prev 和 Next，较浪费空间，加重内存的碎片化

3.3 压缩列表ZipList

在 Redis3.2 版本前 压缩列表不仅是 List 的底层实现之一，同时也是 Hash、 ZSet 两种数据类型底层实现之一。

ZipList是一种特殊的“双端链表”（并非链表），由一系列特殊编码的连续内存块组成，像内存连续的数组。可以在任意一端进行压入/弹出操作，并且该操作的时间复杂度为O(1)。

压缩列表 底层数据结构：本质是一个数组，增加了列表长度、尾部偏移量、列表元素个数、以及列表结束标识，有利于快速寻找列表的首尾节点；但对于其他正常的元素，如元素2、元素3，只能一个个遍历，效率仍没有很高效。

当我们的 List 列表数据量比较少的时候，且存储的数据轻量的（如小整数值、短字符串）时候， Redis 就会通过压缩列表来进行底层实现。

注意：

• 如果查找定位首个元素或最后1个元素，可以通过表头 “zlbytes”、“zltail_offset” 元素快速获取，复杂度是 O(1)。但是查找其他元素时，就没有这么高效了，只能逐个查找下去，比如 entryN 的复杂度就是 O(N)

• ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请效率较低。

3.4 双向链表LinkedList（后续已废弃）

3.5 快速链表QuickList

QuickList底层 LinkedList + ZipList，可以从双端访问，内存占用较低，保含多个ZipList，存储上限高。其特点：

• 是一个节点为ZipList的双端链表
• 节点采用ZipList，解决了传统链表的内存占用问题
• 控制了ZipList大小，解决连续内存空间申请效率问题
• 中间节点可以压缩，进一步节省了内存

ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请效率较低。

四、Set集合类型

详细介绍：Redis五种数据类型、String、List、Set、Hash、ZSet

Set 是 Redis 的一种数据类型，它是字符串类型的无序集合，不一定确保元素有序，可以满足元素唯一、查询效率要求极高。和列表一样，你可以添加、删除、查找元素。但它保证每个元素只出现一次。在 Redis 中，集合最多可以包含 2^32 - 1 个元素。满足下列特点：

• 不保证有序性
• 保证元素唯一（可以判断元素是否存在）
• 求交集、并集、差集

应用场景：

1. 社交网络中的好友关系、共同好友、二度好友等功能。
2. 利用集合支持的交集、并集、差集等操作，可以计算共同喜好、全部的喜好、自己独有的喜好等。

底层结构：

Redis Set 的底层实现为整数集合和哈希表两种，当集合中的元素都是整数且元素数量较少时，Redis 会选择整数集合作为底层实现，这样可以更加节省内存；当数据量变大或者集合中的元素不全是整数时，Redis 会自动将底层实现从整数集合切换为哈希表（类似于Java 中，hashset是基于hashmap实现的）

• 为了查询效率和唯一性，Set采用HT编码（Dict）。Dict中的key用来存储元素，Value统一为null。
• 当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries时，Set会采用lntSet编码，以节省内存。

注意事项：

1. 集合中的元素是无序的，如果需要获取有序的数据，可以使用 Sorted Set 数据类型。
2. 集合中的元素不允许重复，如果需要存储重复元素，可以使用 List 数据类型。

五、Hash哈希类型

5.1 简介

详细介绍：Redis五种数据类型、String、List、Set、Hash、ZSet

Hash 是 Redis 的一种数据类型，也叫散列，其value是一个无序字典，类似于Python 的字典、Java中的HashMap结构。它是键值对集合，是一个字符串字段和字符串值之间的映射表，其字段和值的最大长度都是 512MB。在 Redis 中，哈希可以存储超过 4 亿个键值对。

String结构是将对象序列化为JSON字符串后存储，当需要修改对象某个字段时很不方便：

Hash结构可以将对象中的每个字段独立存储，可以针对单个字段做CRUD，只需要通过key + field找到：

Hash结构与Redis中的Zset非常类似：

• 都是键值存储
• 都需求根据键获取值
• 键必须唯一

区别如下：

• zset的键是member，值是score；hash的键和值都是任意值
• zset要根据score排序；hash则无需排序

因此Hash底层采用的编码与ZSet也基本一致，只需要把排序有关的SkipList去掉即可

应用场景：

• 存储对象：Hash 结构可以看作是 String 类型的 field 和 value 的映射表，非常适合用于存储对象。例如，你可以使用 Hash 类型存储用户的信息，如用户名、密码、邮箱等；
• 数据缓存：可以将数据库中的一条记录映射成一个 Hash 结构，Hash 的每个字段对应记录的每个列；
• 数据分析：你可以使用 Hash 类型存储各种统计数据，例如用户的行为数据，然后进行数据分析；
• 社交网络：在社交网络应用中，你可以使用 Hash 类型存储用户的朋友列表、粉丝列表等

底层结构：

Hash底层采用的编码与ZSet也基本一致，只需要把排序有关的SkipList去掉即可。Redis Hash 的底层实现为压缩列表和哈希表两种，当 Hash 中的元素个数较少且每个元素的大小较小的时候，Redis 会选择压缩列表作为底层实现，这样可以更加节省内存；当数据量变大时，Redis 会自动将底层实现从压缩列表切换为哈希表。

• Hash结构默认采用ZipList编码，用以节省内存。ZipList中相邻的两个entry分别保存field和value
• 当数据量较大时，Hash结构会转为HT编码，也就是Dict，触发条件有两个：
  • ZipList中的元素数量超过了hash-max-ziplist-entries（默认512）
  • ZipList中的任意entry大小超过了hash-max-ziplist-value（默认64字节）

5.2 数据结构

Redis 的 Hash 类型的底层实现是一个非常优化的数据结构，它会根据实际情况选择使用紧凑的**压缩列表（ziplist）或者散列表（hashtable）**作为底层实现。

• Hash结构默认采用ZipList编码，用以节省内存。ZipList中相邻的两个entry分别保存field和value
• 当数据量较大时，Hash结构会转为HT编码，也就是Dict，触发条件有两个：
  • ZipList中的元素数量超过了hash-max-ziplist-entries（默认512）
  • ZipList中的任意entry大小超过了hash-max-ziplist-value（默认64字节）

Redis 的 Hash 类型会根据实际情况在压缩列表（ziplist）和散列表（hashtable）之间进行切换，这主要取决于两个配置参数：hash-max-ziplist-entries 和 hash-max-ziplist-value。

• hash-max-ziplist-entries：这个参数用于设置压缩列表可以存储的最大节点数量。如果一个 Hash 类型的元素数量超过这个值，那么就会从压缩列表切换到散列表。默认值为 512；

• hash-max-ziplist-value：这个参数用于设置压缩列表中每个节点的最大值大小（以字节为单位）。如果一个 Hash 类型的任何元素的大小超过这个值，那么就会从压缩列表切换到散列表。默认值为 64。

这两个参数都可以在 Redis 的配置文件中进行设置。通过调整这两个参数，你可以根据自己的应用特性，选择更倾向于节省内存，还是更倾向于提高性能。

• 从压缩列表转换到散列表：当 Hash 类型存储的字段和值的数量超过 hash-max-ziplist-entries 的值，或者任何字段或值的大小超过 hash-max-ziplist-value 的值时，Redis 会将底层结构从压缩列表转换为散列表。这个过程是自动进行的，对用户来说是透明的。

• 从散列表转换到压缩列表：一旦 Hash 类型的底层结构被转换为散列表，就无法再转换回压缩列表。这是因为散列表的性能更高，而且在大多数情况下，一旦一个 Hash 类型的大小超过了一定的阈值，那么它的大小就很可能会继续增长。

压缩列表（ziplist）与散列表（hashtable）的详细介绍 可见本文1.4章节。

六、ZSet类型

6.1 简介

详细介绍：Redis五种数据类型、String、List、Set、Hash、ZSet

ZSet（有序集合）也就是SortedSet，其中每一个元素都需要指定一个score值和member值。它是一个可排序的set集合，在 Set 的基础上增加了一个权重参数 score，使得集合中的元素能够按 score 进行有序排列。在 Redis 中，有序集合的最大成员数是 2^32 - 1。ZSet具备下列特性：

• 可排序。根据score值排序
• 元素不重复，member必须唯一
• 查询速度快，也可以根据member查询分数

因为ZSet的可排序特性，经常被用来实现排行榜这样的功能。

应用场景：

• 排行榜应用：有序集合使得我们能够方便地实现排行榜，比如网站的文章排行、学生成绩排行等。
• 带权重的消息队列：可以通过 score 来控制消息的优先级。

底层结构：

ZSet与Java中的TreeSet有些类似，但底层数据结构却差别很大。ZSet中的每一个元素都带有一个score属性，可以基于score属性对元素排序，底层的实现是一个跳表（SkipList）加 hash表。注意，集合成员是唯一的，但是评分可以重复。

• Redis ZSet 的底层实现为跳跃列表和哈希表两种，跳跃列表保证了元素的排序和快速的插入性能，哈希表则提供了快速查找的能力。

• 当元素数量不多时，HT和SkipList的优势不明显，而且更耗内存。因此zset还会采用ZipList结构来节省内存，不过需要同时满足两个条件：

  • 元素数量小于zset_max_ziplist_entries，默认值128
  • 每个元素都小于zset_max_ziplist_value字节，默认值64

补充：ziplist本身没有排序功能，而且没有键值对的概念，因此需要有zset通过编码实现：

• ZipList是连续内存，因此score和element是紧挨在一起的两个entry，element在前，score在后
• score越小越接近队首，score越大越接近队尾，按照score值升序排列

注意事项：

1. 有序集合中的元素是唯一的，但分数（score）可以重复。
2. 插入、删除、查找的时间复杂度都是 O(log(N))。对于获取排名（排行榜）的操作，Redis 有序集合是非常高效的。

6.2 什么时候采用压缩列表、什么时候采用跳表

什么时候采用压缩列表、什么时候采用跳表呢

• 有序集合保存的元素数量小于128个
• 有序集合保存的所有元素的长度小于64字节

上述 1且2的时候，采用压缩列表；否则采用跳表

6.3 跳表

学习一个新知识，从三方面分析：WHAT、WHY、HOW

6.3.1 跳表是什么（what）

**SkipList（跳表）**首先是链表，在链表的基础上，增加了多级索引，通过多级索引位置的转跳，实现了快速查找元素。但与传统链表相比有几点差异：

• 元素按照升序排列存储
• 节点可能包含多个指针，指针跨度不同

SkipList的特点：

• 跳跃表是一个双向链表，每个节点都包含score和ele值
• 节点按照score值排序，score值一样则按照ele字典排序
• 每个节点都可以包含多层指针，层数是1到32之间的随机数
• 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
• 增删改查效率与红黑树基本一致，实现却更简单

普通链表想查找元素27，只能从链表头部一个个往后遍历，需要遍历6次 才能找到元素27

6.3.2 跳表怎么做的（how）

跳表怎么做的（how）：建立多级索引

如建立一级索引

如果觉得慢，可以建立二级索引

当数据量特别大的时候，跳表的时间复杂度为 O(logN)。其本身利用的思想，有点类似于二分法。

6.3.3 为什么需要跳表（WHY）

因为普通链表查找一个元素 时间复杂度O(n)；而跳表查找的时间复杂度为O(logn)，查找速度更快。不仅如此，删除、插入等操作的时间复杂度也是O(logn)

6.3.4 为什么用跳表而不用红黑树或者二叉树呢

红黑树、二叉树查找一个元素的时间复杂度也是O(logn)

• ZSet有个核心操作，范围查找：跳表效率比红黑树高，跳表可以做到 logn 时间复杂度内，快速查找，找到区间起点、依次往后遍历即可，但红黑树范围查找的效率没有跳表高（每一层加了指针）
• 跳表实现比红黑树及平衡二叉树简单、易懂：可以有效控制跳表的索引层级来控制内存的消耗，

6.3.5 zset为什么用跳表而不用二叉树或者红黑树呢，MySQL为什么不用跳表

Redis是直接操作内存的、并不需要磁盘io，而MySQL需要去读取磁盘io，所以MySQL使用b+树的方式去减少磁盘io。B+树原理是 叶子节点存储数据、非叶子节点存储索引，每次读取磁盘页时就会读取一整个节点，每个叶子节点还要指向前后节点的指针，其目的是最大限度地降低磁盘io

数据在内存种读取 耗费的时间是磁盘IO读取的百万分之一，而Redis是内存中读取数据、不涉及IO，因此使用了跳表，跳表模型是更快更简单的方式

七、Stream类型

Stream 是 Redis 5.0 版本引入的新特性，它是一种类似于日志系统的数据结构，用于存储多个键值对的列表，每个键值对都会被分配一个自动递增的ID。Stream 主要用于实现消息队列的功能，如 Apache Kafka。

应用场景：

• 消息队列：Stream 可以作为生产者消费者模型的一种实现，生产者添加消息到 Stream，消费者从 Stream 中读取消息并处理。
• 日志记录：由于 Stream 中的每个元素都有唯一的 ID，并且这个 ID 是自动递增的，因此非常适合用来记录日志。

底层结构：

Redis Stream 的底层实现为一种叫做快速列表（quicklist）的数据结构，这是一种同时包含了压缩列表（ziplist）和双向链表特性的数据结构，既可以利用压缩列表节省内存，又可以利用双向链表在两端进行快速的添加、删除操作。

常用命令：

XADD key ID field value [field value …]：向 Stream 中添加元素。
XRANGE key start end [COUNT count]：获取 Stream 中指定范围的元素。
XREAD [COUNT count] [BLOCK milliseconds] STREAMS key [key …] ID [ID …]：从 Stream 中读取数据。
XDEL key ID [ID …]：从 Stream 中删除指定 ID 的元素。
XLEN key：获取 Stream 中的元素数量。

注意事项：

• Stream 是 Redis 中唯一一个可以安全地进行多个写入操作的数据结构，因为每个元素都有一个唯一的、自动递增的 ID。
• Stream 中的元素一旦被添加，就不能被修改，只能被删除。

参考 Redis数据结构：Hash类型全面解析、Redis数据结构：List类型全面解析