• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

【Redis】拼多多面试官问我zset底层是如何实现的,我反手就把跳表的数据结构画了出来

互联网 diligentman 1周前 (10-14) 11次浏览

引言

Redis因为其完全基于内存、性能出色,加上具备丰富的数据类型,在电商环境中深受后端开发的喜爱。其中有序集合zset就是基本数据类型之一,并且每个member都带有score(可用于排序),因此很适合在打赏日榜、近一周收益这类场景中运用。

数据结构初探

有序集合对象的编码可以是ziplist或者skiplist。同时满足以下条件时使用ziplist编码:

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

以上两个条件的上限值可通过zset-max-ziplist-entries和zset-max-ziplist-value来修改。

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

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

深入跳表skiplist

在介绍跳表前,我们先来回顾一下基本链表,并思考为何一步一步演化成跳表的数据结构。

【Redis】拼多多面试官问我zset底层是如何实现的,我反手就把跳表的数据结构画了出来

在这样一个链表中,如果我们要查找某个数据,那么需要从头开始逐个进行比较,直到找到包含数据的那个节点,或者找到第一个比给定数据大的节点为止(没找到)。也就是说,时间复杂度为O(n)。同样,当我们要插入新数据的时候,也要经历同样的查找过程,从而确定插入位置。

假如我们每隔一个节点增加一个指针,让指针指向下下个节点,如下图:

【Redis】拼多多面试官问我zset底层是如何实现的,我反手就把跳表的数据结构画了出来

现在当我们想查找数据的时候,可以先沿着这个新链表进行查找。当碰到比待查数据大的节点时,再回到原来的链表中进行查找。比如,我们想查找23,查找的路径是沿着下图中标红的指针所指向的方向进行的:

【Redis】拼多多面试官问我zset底层是如何实现的,我反手就把跳表的数据结构画了出来

  • 23首先和7比较,再和19比较,比它们都大,继续向后比较。
  • 但23和26比较的时候,比26要小,因此回到下面的链表(原链表),与22比较。
  • 23比22要大,沿下面的指针继续向后和26比较。23比26小,说明待查数据23在原链表中不存在,而且它的插入位置应该在22和26之间。

在这个查找过程中,由于新增加的指针,时间复杂度不再是O(N)了,也即我们不再需要与链表中每个节点逐个进行比较了。需要比较的节点数大概只有原来的一半。

利用同样的方式,我们可以在上层新产生的链表上,继续扩展指针,从而产生第三层链表。如下图:

【Redis】拼多多面试官问我zset底层是如何实现的,我反手就把跳表的数据结构画了出来

在这个新的三层链表结构上,如果我们还是查找23,那么沿着最上层链表首先要比较的是19,发现23比19大,接下来我们就知道只需要到19的后面去继续查找,从而一下子跳过了19前面的所有节点。可以想象,当链表足够长的时候,这种多层链表的查找方式能让我们跳过很多下层节点,大大加快查找的速度。

skiplist正是受这种多层链表的想法的启发而设计出来的。实际上,按照上面生成链表的方式,上面每一层链表的节点个数,是下面一层的节点个数的一半,这样查找过程就非常类似于一个二分查找,使得查找的时间复杂度可以降低到O(log n)。但是,这种方法在插入数据的时候有很大的问题。新插入一个节点之后,就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系,就必须把新插入的节点后面的所有节点(也包括新插入的节点)重新进行调整,这会让时间复杂度重新蜕化成O(n)。删除数据也有同样的问题。

skiplist为了避免这一问题,它不要求上下相邻两层链表之间的节点个数有严格的对应关系,而是为每个节点随机出一个层数(level)。附源码:

#define ZSKIPLIST_MAXLEVEL 32 
#define ZSKIPLIST_P 0.25 

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

执行插入操作时计算随机数的过程,是一个很关键的过程,它对skiplist的统计特性有着很重要的影响。这并不是一个普通的服从均匀分布的随机数,而是服从一定规则的:

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

比如,一个节点随机出的层数是3,那么就把它链入到第1层到第3层这三层链表中。为了表达清楚,下图展示了如何通过一步步的插入操作从而形成一个skiplist的过程:

【Redis】拼多多面试官问我zset底层是如何实现的,我反手就把跳表的数据结构画了出来

从上面skiplist的创建和插入过程可以看出,每一个节点的层数(level)是随机出来的,而且新插入一个节点不会影响其它节点的层数。因此,插入操作只需要修改插入节点前后的指针,而不需要对很多节点都进行调整。这就降低了插入操作的复杂度。实际上,这是skiplist的一个很重要的特性,这让它在插入性能上明显优于平衡树的方案。这在后面我们还会提到。

skiplist,指的就是除了最下面第1层链表之外,它会产生若干层稀疏的链表,这些链表里面的指针故意跳过了一些节点(而且越高层的链表跳过的节点越多)。这就使得我们在查找数据的时候能够先在高层的链表中进行查找,然后逐层降低,最终降到第1层链表来精确地确定数据位置。在这个过程中,我们跳过了一些节点,从而也就加快了查找速度。

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

【Redis】拼多多面试官问我zset底层是如何实现的,我反手就把跳表的数据结构画了出来

需要注意的是,前面演示的各个节点的插入过程,实际上在插入之前也要先经历一个类似的查找过程,在确定插入位置后,再完成插入操作。

实际应用中的skiplist每个节点应该包含member和score两部分。前面的描述中我们没有具体区分member和score,但实际上列表中是按照score进行排序的,查找过程也是根据score在比较。

为什么采用跳表,而不使用哈希表或平衡树实现呢

  1. skiplist和各种平衡树(如AVL、红黑树等)的元素是有序排列的,而哈希表不是有序的。因此,在哈希表上只能做单个key的查找,不适宜做范围查找。所谓范围查找,指的是查找那些大小在指定的两个值之间的所有节点。
  2. 在做范围查找的时候,平衡树比skiplist操作要复杂。在平衡树上,我们找到指定范围的小值之后,还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造,这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单,只需要在找到小值之后,对第1层链表进行若干步的遍历就可以实现。
  3. 平衡树的插入和删除操作可能引发子树的调整,逻辑复杂,而skiplist的插入和删除只需要修改相邻节点的指针,操作简单又快速。
  4. 从内存占用上来说,skiplist比平衡树更灵活一些。一般来说,平衡树每个节点包含2个指针(分别指向左右子树),而skiplist每个节点包含的指针数目平均为1/(1-p),具体取决于参数p的大小。如果像Redis里的实现一样,取p=1/4,那么平均每个节点包含1.33个指针,比平衡树更有优势。

喜欢 (0)