redis之zset的底层结构–>跳跃表

跳跃表,又名skiplist,是一种虽然不如红黑树,AVL树等自平衡树强大,却可以在查找,删除,增加达到(logn)^2的效率的一种表,并且可以O(n)的实现区间数据的范围查找获取,性能上不属于平衡树,编码却很更加简单,可以称得上是一种物美价廉的数据结构。我曾经手写一次红黑树,只是完成了插入,查找的功能,已经是160行代码量了,加上删除,估计要230左右的代码量吧。还是有点复杂的。

常见的两种数据集合结构,一种是链表,一种是数组,前者在查找上的效率无法忍受,却在添加上很方便,后者可以做到随机查找,但是增删数据却是很麻烦,跳跃表可以理解为是链表的增强版,通过多个维度的有序链表实现查询上的优化,具体结构定义如下。

class SkipListNode{

Element data;//用来存储数据

SkipListNode forward[];//用来存储指针节点

SkipListNode(Element d , int level)

{

data = d;

forward = new skipListNode[level+1];

}

}

class SkipList{

int maxLevel;

SkipListNode header;

SkipListNode tail;

SkipList(int maxLev)

{

maxLevel = maxLev;

heaer = new SkipListNode(null , maxLevel);

tail = new SkipListNode(maxValue , maxLevel);

for(int i = 0; i <= maxLevel;i++){

header.forward[i] = tail;

}

}

}

由以上可以看到,跳跃表是在header和tail之间构成一个区间,一个链表构成的区间,就像两堵墙 , 这个链表是有序的,保证链表的最小的值都比header开头的大,最大的数组也不会超过maxValue,这样加上header,tail在一起,是一个完整的链表,而以后无论节点如何添加,都不会大于tail,都不会小于header,这点很重要。

在上面的class中可以看到,  forward = new skipListNode[level+1],forward指针纵向的构成一个结构体数组,而forward中每一个节点指向的结构体节点本身也有forward指向下一个结构体节点,这样就可以和header以及tail构成横向的链表,查找的时候,会在maxLevel开始查找,如果你把它理解成墙的话,就是在墙头开始查找,因为是从墙头,这个时候遍历的节点数目是统计意义上的(1/2)^Level * k (k是元素个数,level是所处的节点数),在上层找到一个区间,然后进入下一层,根据在上一层的时候找到的已经缩小了的区间,在第二层的链表中,进一步缩小空间,一直进入到最后一层,唯一确定找到的节点。

插入的方式很奇葩,也很让人意外,第一次遇到这种统计意义上的效率,理解上多少有点难以接受。根据上面的内容,找到具体要插入的位置,然后具体这个节点层级是多少,是通过摇色子来决定的,具体算法如下

int generateRandomLevel(){

int level = 0;

while(newlevel < maxLevel && Math.random() < 0.5) level++;

return level;

}

这个就是那篇英文文档最后留下的如何确定新插入节点的算法,就是摇色子,当时不理解,想骂娘。其实是对的。从概率上来说,当前一共有k个节点,那么,最底层的链表长度就是k嘛,然后第一层链表长度,就应该是1/2 * k ,第二层长度就应该是(1/2)^2 *k,而这个生成函数,可以再概率上保证每一层的链表的长度是对的,剩下的,就是要求这些链表的分布尽量的均匀离散,跳跃表没有保证掘对的离散平均,这点让我在个人揣测的时候百思不得其解到底如何做到绝对的离散,实际上,保证绝对的分布均匀是需要很大的代价的,需要向平衡树那样,跳跃表保证了统计意义上的均匀,因为统计意义上的个数毫无规律的分布在整个区间内,本身就是符合统计意义上离散的。

 

==========================

改天上图,整理

=========================

 

它的最底层,和我们大众所知的单向链表没有什么区别,第二层

为了看这个skiplist,找了一篇10多页的英文文档啃,结果前5页没看懂说什么,后几页还不错,把查找讲的很透彻,插入却一句带过,fuck,顿时想骂娘,最后还是找人博客看明白怎么回事。算法太弱了,一怒之下将麻省的算法课全部下载下来,争取一两个月内啃完

Leave a comment

Your email address will not be published.

*