复述,中快速表、压缩表和双向链表的区别有哪些

　　

这篇文章主要介绍复述中快速表、压缩表和双向链表的区别有哪些,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!

前言

最近在看《复述的设计与实现》这本的书,写的真的是太好了,一下子就看入迷了,谢谢作者。不过在学习的时候发现一个问题,我服务器上安装的是Redis5.0.9版本的,而作者介绍的是Redis3.0版本的,在第一部分将数据结构与对象章节的时候,出现了一些差别,就是在复述对外暴露的列表结构底层使用的数据结构问题。由于书上没有记录,所以就在网上查阅了些资料学习了一下,自己再做个总结,当做自己的笔记。

差别

出现的差别就是,在redis3.2版本之前,它使用的是ziplist和linkedlist编码作为列表键的底层实现,在它之后,就采用了一个叫做quicklist的数据结构来作其底层实现。
<强> <代码>先来介绍下redis3.2之前的版本的知识点:
在使用ziplist和linkedlist作为列表键底层实现的时候,他们之间会有一个选择标准:
<强>选择ziplist的时候:

<李>

列表对象保存的所有字符串元素的长度都小于64字节;

<李>

列表对象保存的元素量小于512个

上面的是选择ziplist作为底层实现所必须满足的条件,如果没满足的话就选用linkedlist作为其底层实现。

127.0.0.1:6379>, rpush  blah “hello",“world",“again" 　　3. 　　127.0.0.1:6379> object  encoding 等等 　　ziplist 　　127.0.0.1:6379>, rpush  blah “wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww" 　　4 　　127.0.0.1:6379> object  encoding 等等 　　linkedlist

<强> <代码>再来介绍下redis3.2之后的版本:

这个涉及到quicklist这个数据结构了,书上没有记录,所以我查了下资料,也总结到自己的博客当中。

我安装的时候redis5.0.9版本的,所以上面的几个指令执行的结果会有所不同

127.0.0.1:6379>, rpush  blah “hello",“world",“again" 　　3. 　　127.0.0.1:6379> object  encoding 等等 　　quicklist 　　127.0.0.1:6379>, rpush  blah “wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww" 　　4 　　127.0.0.1:6379> object  encoding 等等 　　quicklist

quicklist数据结构的介绍

ziplist和linkedlist就不介绍了，书本上有，我们来看看quicklist。
quicklist其实现也是依赖于ziplist和linkedlist来实现的，它是两个结构的结合。它将ziplist来进行分段存储，也就是分成一个个的quicklistNode节点来进行存储。每个quicklistNode指向一个ziplist，然后quicklistNode之间是通过双向指针来进行连接的。我们来看下大致的结构：

Redis中快速表、压缩表和双向链表的区别有哪些

看到这个结构可能会有些疑问：

  • 这个结构啥意思啊，为什么有的节点是ziplist，有的是quicklistZF？

  • 为什么quicklist头部和尾部各有两个节点是ziplist，剩下中间的是quicklistZF？

  • 为什么每个quicklistNode节点的ziplist内部的数据个数不一致呢？

为什么要把底层数据结构优化成quicklist？

在解决上面的问题之前我们先来解决一个首要的问题，也就是redis为什么要把列表键的底层数据结构优化成quicklist？
其实可以从两个方面来考虑这个原因：

  • ziplist这个结构，它内部的数据存储是一段连续的空间，这样的话，就要求很大一块内存空间。就比如说，我们想存储很多的数据，但是内存中并没有符合要求的连续的存储空间，而是存在很多不连续的小空间（加起来可以符合要求）。

  • 再来说说linkedlist这个结构，它数据存储不要求连续，就可以避免上面的弊端，不过这样以来，每个节点都分配一个一块内存，那就有可能造成大量的内存碎片。

综上两个考虑，redis在3.2版本以后就对此情况进行了优化，就出来了quicklist这个数据结构，quicklist其实就是一个分段的ziplist，为什么这么说呢？其实quicklist存储数据基本单位是quicklistNode，每个quicklistNode的内容区就是以ziplist数据结构存储的。也就是上面图示展示的。

为什么每个quicklistNode节点的ziplist内部的数据个数不一致呢？

现在转化到quicklist了，但是还需要考虑，quicklistNode里的ziplist里的内容处理呢？一个ziplist我需要存储多少个数据呀？也跟上面两个点考虑的一样

复述,中快速表、压缩表和双向链表的区别有哪些