Redis设计与实现——跳跃表

6个月前 (05-31) wang 技术杂谈 0评论 已收录 200℃ 浏览数:171

跳跃表是一种有序的数据结构,它通过在每个结点中维持多个指向其他结点的指针,从而达到快速访问节点的目的。

跳跃表支持平均O(logN),最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点。

Redis使用跳跃表左右有序集合键的底层实现之一,如果一个有序集合包含的元素数量较多,或者有序集合的元素是较长的字符串的时候,Redis就会使用跳跃表作为底层实现。

我们看一个图就能明白,什么是跳跃表。


上面基本上就是跳跃表的思想,每一个结点不单单只包含指向下一个结点的指针,可能包含很多个指向后续结点的指针,这样就可以跳过一些不必要的结点,从而加快查找、删除等操作。对于一个链表内每一个结点包含多少个指向后续元素的指针,这个过程是通过一个随机函数生成器得到,这样子就构成了一个跳跃表。这就是为什么论文“Skip Lists : A Probabilistic Alternative to Balanced Trees ”中有“概率”的原因了,就是通过随机生成一个结点中指向后续结点的指针数目。随机生成的跳跃表可能如下


跳跃表具有如下性质:

(1) 由很多层结构组成

(2) 每一层都是一个有序的链表

(3) 最底层(Level 1)的链表包含所有元素

(4) 如果一个元素出现在 Level i 的链表中,则它在 Level i 之下的链表也都会出现。

(5) 每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。

 

Redis中跳跃表结点的层高是1-32之间的随机数。

 

其他内容可以查看https://blog.csdn.net/ict2014/article/details/17394259

 

 

博主

Just do it. Now or never.

相关推荐

嗨、骚年、快来消灭0回复。