目录
前言：
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;小心得：
一个redis对象的头部，不包含引用对象的指针就已经占据了16个字节的大小。所以我们在实际使用redis的时候，尽量避免直接使用String 这种数据结构，因为他是每一个字符串都需要一个键，那么就会多占用对象头，会造成很大的性能浪费。
这张图就很好的表述了我的意思。
RedisObject常见的编码有：
总结：
本文介绍完了Redis的底层数据机构，从下一篇来时，我们就要开始学习Redis我们表层使用的五种数据结构：String ，set，zet，hash，list。
如果我的内容对你有帮助，请点赞，评论，收藏。创作不易，大家的支持就是我坚持下去的动力！文章来源：https://www.toymoban.com/news/detail-848360.html
文章来源地址https://www.toymoban.com/news/detail-848360.html
到了这里，关于【从零开始学习Redis | 第八篇】认识Redis底层数据结构（下）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
