有序集合对象 ZSet 的底层原理

2024-07-15 12:12| 来源: 网络整理| 查看: 265

这里写目录标题 ziplist压缩列表结构压缩列表结构压缩列表节点结构连锁更新压缩列表在Redis中的用途 skiplist传统跳表改进后的跳表zset中的跳表redis中如何保证skiplist的查找性能skiplist与哈希表、平衡树、B+树的比较skiplist与哈希表比较skiplist与平衡树的比较skiplist与B+树的比较

有序集合对象ZSet的编码可以是ziplist（压缩列表）或者skiplist（跳表）。同时满足以下条件时使用ziplist编码：

元素数量小于128个。所有member的长度都小于64字节。

以上两个条件的上限值可通过zset-max-ziplist-entries和zset-max-ziplist-value来修改。不满足这两个条件时使用一个dict + 一个skiplist来实现的。简单来讲，dict用来查询数据到分数的对应关系，而skiplist用来根据分数查询数据（可能是范围查找）。

ziplist

ziplist编码的有序集合使用紧挨在一起的压缩列表节点来保存，ziplist内的集合元素按score从小到大排序，score较小的排在表头位置。

一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。

压缩列表结构压缩列表结构

在这里插入图片描述

参数说明： zlbytes：记录 ziplist 整个结构体的占用空间大小。 zltail：记录整个 ziplist 中最后一个 entry 的偏移量。 zllen：记录了 ziplist 包含的entry数量。 entryN：ziplist 的节点。 zlend：特殊值0xFF（十进制255），用于标记 ziplist 的末端。

压缩列表节点结构

在这里插入图片描述

参数说明： previous_entry_length：记录压缩列表中前一个节点的长度。previous_entry_length属性的长度可以是1字节或者5字节：如果前一节点的长度小于 254 字节，那么previous_entry_length属性的长度为1字节。如果前一节点的长度大于等于254字节，那么previous_entry_length属性的长度为5字节。 encoding：记录节点所保存数据的类型以及长度。 contents：节点所保存数据的值。

连锁更新

由于压缩列表的previous_entry_length属性可能是1字节或5字节，若在一个压缩列表中，有多个连续的、长度介于250字节到253字节之间的节点，则添加新节点或删除节点都有可能会引发多个节点的连续多次空间扩展，这种现象称之为“连锁更新”。

压缩列表在Redis中的用途作为list的底层实现之一：当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用ziplist来做list的底层实现。作为hash的底层实现之一：当一个哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用ziplist来做hash的底层实现。作为有zset的底层实现之一：如果一个有序集合包含的元素数量比较少且有序集合中元素的成员是比较短的字符串时,Redis就会使用ziplist来作为zset的底层实现。 skiplist

skiplist编码的有序集合底层是一个命名为zset的结构体，而一个zset结构同时包含一个字典和一个跳跃表。跳跃表按score从小到大保存所有集合元素。而字典则保存着从member到score的映射，这样就可以用O(1)的复杂度来查找member对应的score值。虽然同时使用两种结构，但它们会通过指针来共享相同元素的member和score，因此不会浪费额外的内存。

跳表(skip List)是一种随机化的数据结构，基于并联的链表，实现简单，插入、删除、查找的复杂度均为O(logN)。简单说来跳表也是链表的一种，只不过它在链表的基础上增加了跳跃功能，正是这个跳跃的功能，使得在查找元素时，跳表能够提供O(logN)的时间复杂度。

传统跳表

在这里插入图片描述

改进后的跳表

在传统的跳表上，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似于一个二分查找，使得查找的时间复杂度可以降低到O(log n)。但是，这种方法在插入数据的时候有很大的问题。新插入一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2：1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。删除数据也有同样的问题。

skiplist为了避免这一问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数(level)。比如，一个节点随机出的层数是3，那么就把它链入到第1层到第3层这三层链表中。下图展示了如何通过一步步的插入操作从而形成一个skiplist的过程：在这里插入图片描述

刚刚创建的这个skiplist总共包含4层链表，现在假设我们在它里面依然查找23，下图给出了查找路径：在这里插入图片描述

zset中的跳表

Redis的跳表由zskiplistNode和skiplist两个结构定义,其中 zskiplistNode结构用于表示跳跃表节点,而skiplist结构则用于保存跳跃表节点的相关信息,比如节点的数量,以及指向表头节点和表尾节点的指针等等。Redis中的跳表整体结构如下所示：在这里插入图片描述

上图左边是skiplist结构，该结构包含以下属性：

header：指向跳跃表的表头节点，通过这个指针程序定位表头节点的时间复杂度就为O(1)。tail：指向跳跃表的表尾节点,通过这个指针程序定位表尾节点的时间复杂度就为O(1)。level：记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)，通过这个属性可以再O(1)的时间复杂度内获取层高最高的节点的层数。length：记录跳跃表的长度,即跳表目前包含节点的数量(表头节点不计算在内)，通过这个属性，程序可以再O(1)的时间复杂度内返回跳跃表的长度。

上图右边是四个zskiplistNode结构，该结构包含以下属性：

层(level)：节点中用L1、L2、L3等字样标记节点的各个层,L1代表第一层,L2代表第二层,以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点,而跨度则记录了前进指针所指向节点和当前节点的距离(跨度越大、距离越远)。在上图中,连线上带有数字的箭头就代表前进指针,而那个数字就是跨度。当程序从表头向表尾进行遍历时,访问会沿着层的前进指针进行。每次创建一个新跳跃表节点的时候,程序都根据幂次定律(powerlaw,越大的数出现的概率越小)随机生成一个介于1和32之间的值作为level数组的大小,这个大小就是层的“高度”。后退(backward)指针：节点中用BW字样标记节点的后退指针,它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。与前进指针所不同的是每个节点只有一个后退指针，因此每次只能后退一个节点。分值(score)：各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中,节点按各自所保存的分值从小到大排列。成员对象(oj)：各个节点中的o1、o2和o3是节点所保存的成员对象。

在同一个跳跃表中,各个节点保存的成员对象必须是唯一的,但是多个节点保存的分值却可以是相同的：分值相同的节点将按照成员对象在字典序中的大小来进行排序,成员对象较小的节点会排在前面(靠近表头的方向),而成员对象较大的节点则会排在后面(靠近表尾的方向)。

redis中如何保证skiplist的查找性能

节点插入时随机出一个层数，仅仅依靠这样一个简单的随机数操作而构建出来的多层链表结构，能保证它有一个良好的查找性能吗？为了回答这个疑问，我们需要分析skiplist的统计性能。

执行插入操作时计算随机数的过程十分关键，这并不是一个普通的服从均匀分布的随机数，它的计算过程如下：

首先，每个节点肯定都有第1层指针（每个节点都在第1层链表里）。如果一个节点有第i层(i>=1)指针（即节点已经在第1层到第i层链表中），那么它有第(i+1)层指针的概率为p（即上浮一层的概率为p）。节点最大的层数不允许超过一个最大值，记为MaxLevel。

这个计算随机层数的伪码如下所示：

randomLevel() level := 1 // random()返回一个[0...1)的随机数 while random()

【本文地址】

公司简介

联系我们