Redis基础篇：核心底层数据结构详解

Redis基础篇：核心底层数据结构详解

引用

CSDN

1.

https://blog.csdn.net/rita_0567/article/details/145421785

Redis是互联网技术领域使用最为广泛的存储中间件，其高性能、完美文档、简洁易懂的源码和丰富的客户端库在业界得到广泛使用。本文将从Redis的基础数据结构讲起，深入探讨其底层实现原理，帮助读者建立系统化的知识体系。

初识Redis

Redis可以用来做什么

Redis 是互联网技术领域使用最为广泛的存储中间件，它是「Remote Dictionary Service」的首字母缩写，也就是「远程字典服务」。

Redis 凭借自身的高性能、完美文档、简洁易懂的源码和丰富的客户端库在业界得到广泛使用。很多互联网公司，如：阿里、腾讯、美团等都有使用。

Redis使用场景

以《牛客论坛项目》分析（基本包含Redis基本数据类型使用）

1. 记录帖子的点赞数、评论数和点击数 (hash)。
2. 记录用户的帖子 ID 列表 (排序)，便于快速显示用户的帖子列表 (zset)。
3. 记录帖子的标题、摘要、作者和封面信息，用于列表页展示 (hash)。
4. 记录帖子的点赞用户 ID 列表，评论 ID 列表，用于显示和去重计数 (zset)。
5. 缓存近期热帖内容 (帖子内容空间占用比较大)，减少数据库压力 (hash)。
6. 记录帖子的相关文章 ID，根据内容推荐相关帖子 (list)。
7. 如果帖子 ID 是整数自增的，可以使用 Redis 来分配帖子 ID(计数器)。
8. 收藏集和帖子之间的关系 (zset)。
9. 记录热榜帖子 ID 列表，总热榜和分类热榜 (zset)。
10. 缓存用户行为历史，进行恶意行为过滤 (zset,hash)。

当然，Redis可不止这些，想必大家还知道Redis可以用作分布式环境下作为分布式锁使用，模拟消息队列等，后续会陆续讲解。

键和值用什么结构组织

为了实现从键到值的快速访问，Redis 使用了一个哈希表来保存所有键值对。一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。所以，我们常说，一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据。哈希桶里的Entry元素包含了key-value，key就是Redis的键，value就对应Redis不同的数据类型值。

总结：
hash表
哈希表实则是一个数组+链表+entry，数组每个元素称为哈希桶，entry里包含（key，value，next）key是string类型，value就是各个数据类型（string、list、zset、set...）

Redis 底层数据结构

本篇将先从Redis基础数据结构讲起。若已经特别熟悉的同学，可以快速浏览查漏补缺，还不了解的同学赶快研读起来，看完不错记得点个关注。

聊到这里，你肯定会说：“不就是String、List、Sort Set、Hash、Set吗？"，我想你可能搞错了，这只是Redis键值对中键值对中值的保存形式，这里，我们主要想聊聊它的底层数据结构。

可以看到，String类型的底层实现只有一种数据结构，也就是简单动态字符串。而List、Hash、Set和Sorted Set这四种数据类型，都有两种底层实现结构。通常情况下，我们会把这四种类型称为集合类型，它们的特点是一个键对应了一个集合的数据。

接下来，我们逐个分析：

string (字符串)

Redis 的字符串是动态字符串，是可以修改的字符串，内部结构实现上类似于 Java 的ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配，如图中所示，内部为当前字符串实际分配的空间 capacity 一般要高于实际字符串长度 len。

当字符串长度小于 1M 时，扩容都是加倍现有的空间，如果超过 1M，扩容时一次只会多扩 1M 的空间。需要注意的是字符串最大长度为 512M。

部分基本操作命令：

set name xlcoding
OK
get name
"xlcoding"
exists name
(integer) 1
del name
(integer) 1
get name
(nil)
#自增计数器
set age 1
incr age

过期与set命令（*）:

#过期命令—这两个可以配合实现分布式锁（但一般不使用这种方案）

expire name 10 # 10s 后过期
setnx name xlcoding # 如果 name 不存在就执行 set 创建

其他命令还有很多，这里不过多介绍，有兴趣可以网上看资料。

总结：

• 占用空间：512M
• 底层数据结构：简单动态字符串（free、len，buf[]）(可以保存文本+二进制+不会缓冲溢出+时间O1）
• 基本命令：set,get,strlen,exists,decr,incr,setex 等等。
• 应用场景：计数的场景，用户的访问次数、热点文章的点赞转发数量
• 常考操作：set num 1；incr num【计数器】，expire key 60；ttl key 【设置过期时间+查看】

1. 对C语言中的字符串的封装和优化，c语言字符串不是二进制安全的，字符串中间不能有空格，空格标志结束
2. 频繁修改一个字符串时，会涉及到内存的重分配，比较消耗性能。（Redis中的简单动态字符串会有内存预分配和惰性空间释放）。

如果字符串实际使用长度len<1M**，实际分配空间=len长度来存储字符串+1字节存末尾空字符+len长度的预分配空闲内。
**如果字符串实际使用长度len>1M，实际分配空间=len长度来存储字符串+1字节存末尾空字符+1M长度的预分配空闲内存

list (列表)

Redis中list是由两种数据结构构成的，数据少时用ziplist，数据多时用linkedlist（ziplist连锁更新耗时）。

当列表弹出了最后一个元素之后，该数据结构自动被删除，内存被回收。

Redis 的列表结构常用来做异步队列使用。将需要延后处理的任务结构体序列化成字符串塞进 Redis 的列表，另一个线程从这个列表中轮询数据进行处理。

也可将list模拟队列和栈的使用。

右边进左边出：队列

rpush users user1 user2
(integer) 2
llen users
(integer) 2
lpop users
"user1"
lpop users
"uesr2"
lpop users
(nil)

右边进右边出：栈

rpush users user1 user2
(integer) 2
rpop users
"user2"
rpop users
"uesr1"

快速列表

列表元素较少的情况下会使用一块连续的内存存储，这个结构是 ziplist，也即是压缩列表。它将所有的元素紧挨着一起存储，分配的是一块连续的内存。当数据量比较多的时候才会改成 quicklist。因为普通的链表需要的附加指针空间太大，会比较浪费空间，而且会加重内存的碎片化。

比如这个列表里存的只是 int 类型的数据，结构上还需要两个额外的指针 prev 和 next 。所以 Redis 将链表和 ziplist 结合起来组成了 quicklist。也就是将多个ziplist 使用双向指针串起来使用。这样既满足了快速的插入删除性能，又不会出现太大的空间冗余。

总结：

• 占用空间：2^32-1
• 底层数据结构：双向链表+压缩链表
• 数据少用ziplist，数据多linkedlist（ziplist连锁更新耗时）
• linkedlist维护前后指针，占内存空间，还造成内存碎片化
• ziplist没有前后指针，entry保存了上一个结点长度，所以也可以双向遍历，但是当一个结点长度变化了，后面结点都要变，连锁更新耗时
• ziplist结构：
• zlbytes：整个ziplist占字节数
• zltail：尾结点相对于首地址偏移量
• zllen：结点数
• entry：保存了前一个结点长度+编码+内容
• zlend：代表结束

基本命令：rpush、lpop、lpush、rpop,、lrange、llen 等。
应用场景：发布与订阅或者说消息队列、慢查询。

hash (字典)

Redis 的字典相当于 Java 语言里面的 HashMap，它是无序字典。内部实现结构上同Java 的 HashMap 也是一致的，同样的数组 + 链表二维结构。第一维 hash 的数组位置碰撞时，就会将碰撞的元素使用链表串接起来。

不同的是，Redis 的字典的值只能是字符串，另外它们 rehash 的方式不一样，因为Java 的 HashMap 在字典很大时，rehash 是个耗时的操作，需要一次性全部 rehash。Redis 为了高性能，不能堵塞服务，所以采用了渐进式 rehash 策略。

渐进式 rehash 会在 rehash 的同时，保留新旧两个 hash 结构，查询时会同时查询两个hash 结构，然后在后续的定时任务中以及 hash 的子指令中，循序渐进地将旧 hash 的内容一点点迁移到新的 hash 结构中。

若你还是没看懂，看我的面试总结：
hash表：通常保存用户信息等
解决哈希冲突链过长，进行rehash

rehash过程：

1. 使用两个全局哈希表：hash1、hash2
2. 开始只使用hash1、hash2没有分配空间
3. 数据过多时，给hash2分配更多空间（2*hash1）
4. 将hash1数据拷贝到hash2
5. 释放hash1空间，等下一次rehash使用

渐进式rehash：

1. 若一次性将值全部从hash1拷贝至hash2，会线程阻塞，无法服务其他请求，于是使用渐进式rehash
2. 请求来时，将对应索引上的哈希链rehash到hash2上（惰性）
3. 若没有请求也会定时执行渐进式rehash

set（集合）

这个很简单，不用过多介绍，知道它的特性和常用场景就是。

Redis 的集合相当于 Java 语言里面的 HashSet，它内部的键值对是无序的唯一的。它的内部实现相当于一个特殊的字典，字典中所有的 value 都是一个值 NULL。

特性：由于是set，天然去重功能。
常用场景：set 结构可以用来存储活动中奖的用户 ID，因为有去重功能，可以保证同一个用户不会中奖两次。

总结：

• 占用空间：2^32-1
• 底层数据结构：哈希表+整数数组
• 常用命令：sadd、spop、smembers、sismember、scard、sinterstore、sunion 等。
• 使用场景：数据不重复+可以判断一个成员是否存在+交集并集（共同关注、粉丝，两个集合求交集）

zset（有序列表）

zset特别重要，因为它的底层实现有一种数据结构叫跳表，这是面试官跳表喜欢问的一种数据结构，我曾经【字节二面】，【腾讯一面】都问过。

zset 可以用来存粉丝列表，value 值是粉丝的用户 ID，score 是关注时间。我们可以对粉丝列表按关注时间
进行排序。zset 还可以用来存储学生的成绩，value 值是学生的 ID，score 是他的考试成绩。我们可以对成绩按分数进行排序就可以得到他的名次。

具体跳表面试爱问的我都总结在下面了，其他具体实现细节可以上网查资料。

总结：

• 占用空间：2^32-1
• 底层数据结构：压缩链表+跳表
• 当有序集合结点>128个&&每个元素长度<64字节使用ziplist
• skiplist结构：
• 跳表实际是一个使用分数排序有层数概念的双向链表，有头节点，尾节点，记录长度和层数，头节点是傀儡结点用来指向下一个结点，尾节点是指向跳跃表中最大分数的节点，层数是跳跃表中最高层数。每个元素结点包含数据，分数，后退指针，层级数组（forword指向下一个结点）
• 在链表基础上加多级索引，通过索引跳转实现快速定位
• 操作时间复杂度O(logn)
• 空间复杂度O(n)
• 为何不用红黑树这些？：跳表实现简单，平衡树插入删除可能引发平衡调整，更加复杂，跳表只需要动动结点指针；做范围查找的时候，平衡树比skiplist操作要复杂。
• 插入结点使用随机层数算法建立层数 每层晋升概率0.25

常用命令：zadd,zcard,zscore,zrange,zrevrange,zrem
使用场景：对数据根据某个权重进行排序的场景【直播间：实时排行信息+礼物排行榜】

其他数据类型补充：
这里简单列举一下，有兴趣了解更多的可以看书或则查资料，但是上述的几种基础数据结构必须掌握。

bitmap（位图）

• 占用空间：512M
• 常用命令：setbit 、getbit 、bitcount、bitop
• 使用场景：适合需要保存状态信息（比如是否签到、是否登录...）用户行为统计（比如是否点赞过某个视频）

hyperloglog

Redis HyperLogLog 是用来做基数统计的算法，HyperLogLog 的优点是，在输入元素的数量或者体积非常非常大时，计算基数所需的空间总是固定 的、并且是很小的。

在 Redis 里面，每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基 数。这和计算基数时，元素越多耗费内存就越多的集合形成鲜明对比

geo

Redis GEO 主要用于存储地理位置信息，并对存储的信息进行操作，该功能在 Redis 3.2 版本新增。