QuickList

概念

问题1:ZipList虽然节省内存,但是申请的内存必须是连续空间,如果内存占用过多,申请内存效率低,怎么办?

1. 为了缓解这个问题,我们必须限制ZipList的长度和entry的大小
   问题2:但是我们要存储大量数据,超出了ZipList最佳上限应该怎么办?
2. 我们可以创建多个ZipList来分片存储数据
   问题3:数据拆分后比较分散,不方便管理和查找,这多个ZipList如何建立联系?
3. 使用数据结构QuickList,他是一个双端链表,只不过链表中每个节点都是一个ZipList.

QuickList结构

QuickList的特点

控制ZipList的大小

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

1. 如果值为正,则代表ZipList的允许的entry个数的最大值
2. 如果值为负,则代表ZipList的最大内存大小,分5种情况:

• -1:每个ZipList的内存占用不能超过4kb;
• -2:每个ZipList的内存占用不能超过8kb;
• -3:每个ZipList的内存占用不能超过16kb;
• -4:每个ZipList的内存占用不能超过32kb;
• -5:每个ZipList的内存占用不能超过64kb.
  注:在Redis中,默认值为-2

对节点的ZipList进行压缩

除了控制ZipList的大小,QuickList还可以对节点的ZipList做压缩.通过配置项list-compress-depth来控制.因为链表一般都是首尾访问较多,所以首尾是不压缩的.这个参数控制首尾不压缩的节点个数:

• 0:特殊值,表示不压缩
• 1:表示QuickList的首尾各有1个节点不压缩,中间节点压缩
• 2:表示QuickList的首尾各有2个节点不压缩,中间节点压缩
• 以此类推…
  注:Redis中,默认值为0

总结

• 是一个节点为ZipList的双端链表
• 节点采用了ZipList,解决了传统链表的内存占用问题
• 控制ZipList的大小,解决连续内存空间申请效率的问题
• 中间节点可以压缩,进一步节省内存

SkipList

概念

ZipList和QuickList都是从头到尾遍历或者从尾到头的遍历,所以随机查询的效率很低
SkipList(跳表)首先是链表,但是与传统的链表相比是有几点差异的:

• 元素按照升序排列存储
• 节点可能包含多个指针,且指针跨度不同.
  

源码中结构分析

这里需要我们着重关注的几个设计:

• 在zskiplistNode中设计的一个内部类level[](多级索引数组).
  • 在该多级索引数组中,会对索引的跨度和下一个节点的指针进行存储,也就是说,一个节点中,会根据不同的指针跨度,存放不同的下一个节点指针
  • score:节点分数,相当于一个索引,用于排序.不要误会数据存储在这里
    该数组中存储着不同等级的指针跨度
    

总结

1. 跳表是一个双向链表,每个节点都会包含一个score(用于排序)和ele(真实数据)值
2. 节点按照score值排序,score值一样则按照ele字典进行排序
3. 每个节点都可以包含多层指针,层数是1~32之间的随机数
4. 不同层指针到下一个节点的跨度不同,层级越高,跨度越大
5. 增删查改的效率和红黑树基本一致,实现却很简单