底层结构 - Redis 面试题及答案

Java突击队2025/12/19大约 10 分钟

返回Redis 面试题索引第 6/7 章

底层结构

这一部分就比较深了，如果不是简历上写了精通Redis，应该不会怎么问。

46.说说Redis底层数据结构？

Redis有动态字符串(sds)、链表(list)、字典(ht)、跳跃表(skiplist)、整数集合(intset)、压缩列表(ziplist) 等底层数据结构。

Redis并没有使用这些数据结构来直接实现键值对数据库，而是基于这些数据结构创建了一个对象系统，来表示所有的key-value。

redisObject对应的映射
我们常用的数据类型和编码对应的映射关系：

类型-编码-结构
简单看一下底层数据结构，如果对数据结构掌握不错的话，理解这些结构应该不是特别难：

字符串：redis没有直接使⽤C语⾔传统的字符串表示，⽽是⾃⼰实现的叫做简单动态字符串SDS的抽象类型。
C语⾔的字符串不记录⾃身的⻓度信息，⽽SDS则保存了⻓度信息，这样将获取字符串⻓度的时间由O(N)降低到了O(1)，同时可以避免缓冲区溢出和减少修改字符串⻓度时所需的内存重分配次数。

SDS

链表linkedlist：redis链表是⼀个双向⽆环链表结构，很多发布订阅、慢查询、监视器功能都是使⽤到了链表来实现，每个链表的节点由⼀个listNode结构来表示，每个节点都有指向前置节点和后置节点的指针，同时表头节点的前置和后置节点都指向NULL。

链表linkedlist

字典dict：⽤于保存键值对的抽象数据结构。Redis使⽤hash表作为底层实现，一个哈希表里可以有多个哈希表节点，而每个哈希表节点就保存了字典里中的一个键值对。
每个字典带有两个hash表，供平时使⽤和rehash时使⽤，hash表使⽤链地址法来解决键冲突，被分配到同⼀个索引位置的多个键值对会形成⼀个单向链表，在对hash表进⾏扩容或者缩容的时候，为了服务的可⽤性，rehash的过程不是⼀次性完成的，⽽是渐进式的。
跳跃表skiplist：跳跃表是有序集合的底层实现之⼀，Redis中在实现有序集合键和集群节点的内部结构中都是⽤到了跳跃表。Redis跳跃表由zskiplist和zskiplistNode组成，zskiplist⽤于保存跳跃表信息（表头、表尾节点、⻓度等），zskiplistNode⽤于表示表跳跃节点，每个跳跃表节点的层⾼都是1-32的随机数，在同⼀个跳跃表中，多个节点可以包含相同的分值，但是每个节点的成员对象必须是唯⼀的，节点按照分值⼤⼩排序，如果分值相同，则按照成员对象的⼤⼩排序。
整数集合intset：⽤于保存整数值的集合抽象数据结构，不会出现重复元素，底层实现为数组。
压缩列表ziplist：压缩列表是为节约内存⽽开发的顺序性数据结构，它可以包含任意多个节点，每个节点可以保存⼀个字节数组或者整数值。

压缩列表组成

47.Redis 的 SDS 和 C 中字符串相比有什么优势？

C 语言使用了一个长度为 N+1 的字符数组来表示长度为 N 的字符串，并且字符数组最后一个元素总是 \0，这种简单的字符串表示方式不符合 Redis 对字符串在安全性、效率以及功能方面的要求。

C语言的字符串

C语言的字符串可能有什么问题？

这样简单的数据结构可能会造成以下一些问题：

获取字符串长度复杂度高 ：因为 C 不保存数组的长度，每次都需要遍历一遍整个数组，时间复杂度为O(n)；
不能杜绝 缓冲区溢出/内存泄漏 的问题 : C字符串不记录自身长度带来的另外一个问题是容易造成缓存区溢出（buffer overflow），例如在字符串拼接的时候，新的
C 字符串 只能保存文本数据 → 因为 C 语言中的字符串必须符合某种编码（比如 ASCII），例如中间出现的 '\0' 可能会被判定为提前结束的字符串而识别不了；

Redis如何解决？优势？

Redis sds

简单来说一下 Redis 如何解决的：

多增加 len 表示当前字符串的长度：这样就可以直接获取长度了，复杂度 O(1)；
自动扩展空间：当 SDS 需要对字符串进行修改时，首先借助于 len 和 alloc 检查空间是否满足修改所需的要求，如果空间不够的话，SDS 会自动扩展空间，避免了像 C 字符串操作中的溢出情况；
有效降低内存分配次数：C 字符串在涉及增加或者清除操作时会改变底层数组的大小造成重新分配，SDS 使用了 空间预分配 和 惰性空间释放 机制，简单理解就是每次在扩展时是成倍的多分配的，在缩容是也是先留着并不正式归还给 OS；
二进制安全：C 语言字符串只能保存 ascii 码，对于图片、音频等信息无法保存，SDS 是二进制安全的，写入什么读取就是什么，不做任何过滤和限制；

48.字典是如何实现的？Rehash 了解吗？

字典是 Redis 服务器中出现最为频繁的复合型数据结构。除了 hash 结构的数据会用到字典外，整个 Redis 数据库的所有 key 和 value 也组成了一个 全局字典，还有带过期时间的 key 也是一个字典。(存储在 RedisDb 数据结构中)

字典结构是什么样的呢？

Redis 中的字典相当于 Java 中的 HashMap，内部实现也差不多类似，采用哈希与运算计算下标位置；通过 "数组 + 链表" 的链地址法 来解决哈希冲突，同时这样的结构也吸收了两种不同数据结构的优点。
Redis字典结构

字典是怎么扩容的？

字典结构内部包含 两个 hashtable，通常情况下只有一个哈希表 ht[0] 有值，在扩容的时候，把ht[0]里的值rehash到ht[1]，然后进行 渐进式rehash ——所谓渐进式rehash，指的是这个rehash的动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。

待搬迁结束后，h[1]就取代h[0]存储字典的元素。

49.跳跃表是如何实现的？原理？

PS:跳跃表是比较常问的一种结构。

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目的。

为什么使用跳跃表?

首先，因为 zset 要支持随机的插入和删除，所以它 不宜使用数组来实现，关于排序问题，我们也很容易就想到 红黑树/ 平衡树 这样的树形结构，为什么 Redis 不使用这样一些结构呢？

性能考虑： 在高并发的情况下，树形结构需要执行一些类似于 rebalance 这样的可能涉及整棵树的操作，相对来说跳跃表的变化只涉及局部；
实现考虑： 在复杂度与红黑树相同的情况下，跳跃表实现起来更简单，看起来也更加直观；

基于以上的一些考虑，Redis 基于 William Pugh 的论文做出一些改进后采用了 跳跃表 这样的结构。

本质是解决查找问题。

跳跃表是怎么实现的？

跳跃表的节点里有这些元素：

层
跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其它节点的指针，程序可以通过这些层来加快访问其它节点的速度，一般来说，层的数量月多，访问其它节点的速度就越快。
每次创建一个新的跳跃表节点的时候，程序都根据幂次定律，随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度”
前进指针
每个层都有一个指向表尾的前进指针（level[i].forward属性），用于从表头向表尾方向访问节点。
我们看一下跳跃表从表头到表尾，遍历所有节点的路径：
跨度
层的跨度用于记录两个节点之间的距离。跨度是用来计算排位（rank）的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。
例如查找，分值为3.0、成员对象为o3的节点时，沿途经历的层：查找的过程只经过了一个层，并且层的跨度为3，所以目标节点在跳跃表中的排位为3。
分值和成员
节点的分值（score属性）是一个double类型的浮点数，跳跃表中所有的节点都按分值从小到大来排序。
节点的成员对象（obj属性）是一个指针，它指向一个字符串对象，而字符串对象则保存这一个SDS值。