【从零开始学习Redis | 第八篇】认识Redis底层数据结构（下）

前言：

ZipList：

Ziplist的特性:

QucikList:

QuicList特征：

SkipList：

跳表特征：

RedisObijct：

小心得：

总结：

前言：

在现代软件开发中，数据存储和处理是至关重要的一环。为了高效地管理数据，并实现快速的读写操作，各种数据库技术应运而生。其中，Redis作为一种高性能的内存数据库，广泛应用于缓存、会话存储、消息队列等场景。要深入了解Redis的工作原理，就必须先了解其底层数据结构。

Redis之所以能够在性能上表现出色，部分原因在于其精心设计的数据结构。这些数据结构不仅简单高效，而且能够满足各种复杂的数据处理需求。本文将深入探讨Redis底层数据结构的设计原理，包括字符串、哈希、列表、集合、有序集合等，希望能够帮助读者更好地理解Redis的内部机制，为进一步应用和优化Redis提供指导。

上一篇文章我们介绍了动态字符串，intset，Dict这三个底层的数据结构，本文我们再来介绍一下ZipSet,QuickList,SkipList,RedisObject。

ZipList：

我们在上一篇文章最后介绍了Dict，他是基于链表去做的Hash表。但是链表有一个缺陷：内存空间不连续，因此容易产生内存碎片。

而我们今天要介绍的这个数据结构，他是一种特殊的’双端链表‘,由一系列特殊编码的连续内存块组成，可以在任意一端进行压入/弹出操作，而且该操作的复杂度为（O）1

其实ZipList不是链表，我们只是为了方便描述才这么说。

我们可以在Redis的源码中看一看官方作者对ZipList的数据结构的描述：

我们用自己的图来解释一下各个部分的意思：

（下方此图来自黑马程序员，如有侵权，立即删除）

Ziplist的优势就在于：他的entry的字节大小是不固定的。

而虽然我们这么做可以减少内存的浪费，但是他存在一个问题:当节点的长度不固定的时候，我们是如何遍历节点的？毕竟已经无法通过索引下标进行遍历了。要想知道答案，就得先从他的结点结构看起：

结点的结构数据如图所示：

Pervious:前一个结点的长度，占一个或者5个字节。

如果前一个结点的长度小于254，则采用一个字节来保存这个长度值。

如果前一个结点的长度大于254，则采用五个字节来保存这个长度值，第一个字节为0xfe，后面四个才是真实的长度数据

encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个2个或5个字节。

contents：负责保存结点的数据，可以是字符串或整数

通过了解Ziplist的结点结构之后，其实我们就可以知道：如果我们想要知道下一个结点的长度，只需要用起始地址+当前结点三部分的字节数 ，那就是下一个结点的位置了。

如果我们想要找到上一个结点的位置，也只需要拿当前结点的起始位置-上一个结点的长度就好了。

而ZipList会有连锁更新的问题，很简单:每一个结点都存储着上一个结点的信息，如果当前结点的长度发生变化，那么下一个结点中存储上一个结点长度的字节数也能会发生变化，比如以前长度是5，一个字节存储，现在变成了255，五个字节存储。如果每一个结点都会发生类似的情况，就会引发连锁更新问题

但是目前Redis的作者没有解决这个问题，因为他的概率很低。

其实我觉得解决这个问题的思路很简单，如果我们的节点有100万条数据，那么我们如果触发连锁更新的话，就会导致线程阻塞。那我觉得解决思路也很简单，可以和Dict的Rehash的处理方案一样，用两张表，一张进行正常的读取，不阻塞线程，另外一张表进行渐进式的连锁更新。

Ziplist的特性:

1.压缩列表可以看作是一种连续空间的”双向链表“。

2.节点之间不是通过指针相连接，而是记录上一个节点和本节点的长度来寻址，内存占用低。

3.如果列表数据过多，导致链表长度过长，会影响查询性能。

4.增加或删除较大数据的时候可能会引发连续更新问题。

QucikList:

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

为了解决这个问题，我们想到了ZipList分片，创建多个ZipList来存储数据：

而如何把这多个ZipList建立联系呢？

可以把这几个ZipList用指针连接起来。

而QuickList就是这种结构，他是一个双端链表，不过每一个节点是ZipList。

为了避免QuickList中的每一个 ZipList中entry过多，Redis提供了一个配置项：list-max-ziplist-size来限制。

如果值为正，则标识ZipList中允许的最大entry个数的最大值。

如果值为负，则代表ZipList的最大内存大小，分五种情况：

-1:每个Zip的内存大小不能超过4kb
-2:每个Zip的内存大小不能超过8kb
-3:每个Zip的内存大小不能超过16kb
-4:每个Zip的内存大小不能超过32kb
-5:每个Zip的内存大小不能超过64kb

这个参数的默认值为-2。

除了对每一个ZipList限制大小之外，QuicList还可以对节点的ZipList做压缩，通过配置项list-compress-depth来控制，因为链表一般都是从首尾访问比较多，所以首位是不压缩的。而这个配置的参数就是控制首尾不压缩的节点个数。

常见参数：

0：所有节点都不压缩
1：标识首尾各有一个结点不压缩，中间结点压缩
2：标识QuickList的首尾各有两个结点不压缩，中间结点压缩。

讲了这么多，我们来看一看Redis中的源码：

quicklist源码：

quicklistNode源码：

用黑马的图来看一看ZipList的数据结构：

QuicList特征：

1.是一个结点为ZipList的双端链表。

2.结点采用了ZipList，解决了传统链表的内存占用问题。

3.控制了ZipList的大小，解决了连续内存空间的申请效率。

4.中间节点可以压缩，进一步节省了内存。

SkipList：

虽然前面的几个List在空间方面做了优化，但是他的查询效率却很低，都需要遍历查询。

而SkipList（跳表）就是为了提高查询效率而创建的一种数据结构。

SkipList首先是链表，但是他和传统的链表比起来，有以下区别：

1.元素按照升序排列。

2.允许一个结点包含多个指针，指针跨度不同。

其实这个很好理解，既然是链表，那么我们要寻找一个元素就必须遍历链表。这是因为链表的每一个结点都存储的下一个结点的位置，没有跨越的指针。

而我们如果可以让一个结点的指针指向的距离不再是1，那不就在一定程度上优化了搜索效率。

传统链表：

跳表思想：

这样的话，传统链表我们如果要寻找4，就要遍历4个结点，但是现在基于跳表这种思想我们就只用遍历三个结点。

而这也就是跳表需要元素有序排列的意义，如果元素是乱序排放的，那么他往哪里跳就毫无头绪。

接下来我们看一看Redis中的跳表的数据结构：

我们来看一下一个成熟的跳表结构：

跳表特征：

1.跳表是一个双向链表。

2.跳表每一个接单都可以包含多层指针，层数在1-32之间。

3.不同层指针到下一个结点的跨度不同，层级越高，跨度越大。

4.增删改查效率和红黑树一样，但是实现更加简单。

RedisObijct：

Redis中任意数据类型的键和值都会被封装成为一个RedisObject，也叫做Redis对象，一个键对象，一个值对象。

typedef struct redisObject{
//对象类型，分别是string，set，zet，list，hash
    unsigned type:4;
//编码方式
    unsigned encoding:4;
//当前对象最后一次被访问的时间
    unsighed lru:LRU_BITS;
//引用计数器，如果为0说明当前对象没有被引用，可以被回收
    int  refcount;
//指向五种数据类型对应的内存空间
    void * ptr;
} robj;