暂无图片
暂无图片
暂无图片
暂无图片
暂无图片
首页 / Redis散记:Redis数据结构(四) skiplist

Redis散记:Redis数据结构(四) skiplist

没意思先生 2020-03-22
259
skiplist是sorted set数据结构的底层实现之一.skiplist本质上也是一种查找结构,用于解决算法中的查找问题(Searching),即根据给定的key,快速查到它所在的位置.
假如有一个有序链表,如下图(最左侧的灰色节点表示一个空的头结点):
在这样一个链表中,如果我们要查找某个数据,那么需要从头开始逐个进行比较,直到找到包含数据的那个节点,或者找到第一个比给定数据大的节点为止(没找到).也就是说,时间复杂度为O(n).同样,当我们要插入新数据的时候,也要经历同样的查找过程,从而确定插入位置.
假如我们每相邻两个节点增加一个指针,让指针指向下下个节点,如下图:
这样所有新增加的指针连成了一个新的链表,但它包含的节点个数只有原来的一半(上图中是7,19,26).现在当我们想查找数据的时候,可以先沿着这个新链表进行查找.当碰到比待查数据大的节点时,再回到原来的链表中进行查找.比如,我们想查找23,查找的路径是沿着下图中标红的指针所指向的方向进行的:


  • 23首先和7比较,再和19比较,比它们都大,继续向后比较.
  • 但23和26比较的时候,比26要小,因此回到下面的链表(原链表),与22比较.
  • 23比22要大,沿下面的指针继续向后和26比较.23比26小,说明待查数据23在原链表中不存在,而且它的插入位置应该在22和26之间.
在这个查找过程中,由于新增加的指针,我们不再需要与链表中每个节点逐个进行比较了.需要比较的节点数大概只有原来的一半.当链表足够长的时候,这种多层链表的查找方式能让我们跳过很多下层节点,大大加快查找的速度.
实际上,按照上面生成链表的方式,上面每一层链表的节点个数,是下面一层的节点个数的一半,这样查找过程就非常类似于一个二分查找,使得查找的时间复杂度可以降低到O(log n).但是,这种方法在插入数据的时候有很大的问题.新插入一个节点之后,就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系.如果要维持这种对应关系,就必须把新插入的节点后面的所有节点(也包括新插入的节点)重新进行调整,这会让时间复杂度重新蜕化成O(n).删除数据也有同样的问题.
skiplist为了避免这一问题,它不要求上下相邻两层链表之间的节点个数有严格的对应关系,而是为每个节点随机出一个层数(level).比如,一个节点随机出的层数是3,那么就把它链入到第1层到第3层这三层链表中.每一个节点的层数(level)是随机出来的,而且新插入一个节点不会影响其它节点的层数.因此,插入操作只需要修改插入节点前后的指针,而不需要对很多节点都进行调整.这就降低了插入操作的复杂度.

skiplist与平衡树、哈希表的比较:

  • skiplist和各种平衡树(如AVL、红黑树等)的元素是有序排列的,而哈希表不是有序的.因此,在哈希表上只能做单个key的查找,不适宜做范围查找.所谓范围查找,指的是查找那些大小在指定的两个值之间的所有节点.
  • 在做范围查找的时候,平衡树比skiplist操作要复杂.在平衡树上,我们找到指定范围的小值之后,还需要以中序遍历的顺序继续寻找其它不超过大值的节点.如果不对平衡树进行一定的改造,这里的中序遍历并不容易实现.而在skiplist上进行范围查找就非常简单,只需要在找到小值之后,对第1层链表进行若干步的遍历就可以实现.
  • 平衡树的插入和删除操作可能引发子树的调整,逻辑复杂,而skiplist的插入和删除只需要修改相邻节点的指针,操作简单又快速.
  • 从内存占用上来说,skiplist比平衡树更灵活一些.一般来说,平衡树每个节点包含2个指针(分别指向左右子树),而skiplist每个节点包含的指针数目平均为1/(1-p),具体取决于参数p的大小.如果像Redis里的实现一样,取p=1/4,那么平均每个节点包含1.33个指针,比平衡树更有优势.
  • 查找单个key,skiplist和平衡树的时间复杂度都为O(log n),大体相当;而哈希表在保持较低的哈希值冲突概率的前提下,查找时间复杂度接近O(1),性能更高一些.所以我们平常使用的各种Map或dictionary结构,大都是基于哈希表实现的.
  • 从算法实现难度上来比较,skiplist比平衡树要简单得多.
Redis中sorted set的实现是这样的：
  • 当数据较少时,sorted set是由一个ziplist来实现的.
  • 当数据多的时候,sorted set是由一个dict + 一个skiplist来实现的.简单来讲,dict用来查询数据到分数的对应关系,而skiplist用来根据分数查询数据(可能是范围查找)
随着数据的插入,sorted set底层的这个ziplist就可能会转成zset的实现(转换过程详见t_zset.c的zsetConvert)那么到底插入多少才会转呢?根据redis配置中的两项决定:
zset-max-ziplist-entries 128
zset-max-ziplist-value 64

在如下两个条件之一满足的时候,ziplist会转成zset(具体的触发条件参见t_zset.c中的zaddGenericCommand相关代码):

  • 当sorted set中的元素个数,即(数据, score)对的数目超过128的时候,也就是ziplist数据项超过256的时候.

  • 当sorted set中插入的任意一个数据的长度超过了64的时候.

Redis为什么用skiplist而不用平衡树？

  • skiplist占用内存低

  • skiplist的范围遍历性能比平衡树好

  • 数据结构实现难度较低

redis
文章转载自没意思先生，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

评论