跳表
2019-07-17 10:08:29 1 举报
跳表
作者其他创作
大纲/内容
79
23
15
1
L2
13
BW
length 8
82
将上图换个形式，以Redis中跳表的数据结构表示
4
L1
5
level 3
obj4
skiplist
obj1
header
51
当我们查找51时，我们查找过程为：1-》7-》13 -》15 -》23 -》 51
3
当我们维护了一个一级索引后，再查找51时，查找过程为：1-》13 -》23 ； 发现79大于51; 遍历23到79之间；找到51
L3
obj7
NULL
obj8
对链表维护个二级索引
6
对链表维护个一级索引
L32
7
obj3
skiplistNode
tail
2
...
传统链表
obj5
obj2
在一级索引上维护二级索引后，再查找51时，查找过程为：1）先通过2级索引查找1 -》23 ，发现82大于51；2）顺着一级索引查找，发现79依旧大于51；3）回到链表本身，确定区间为（23，79），找到51
可以看到BW（后退指针）和L1形成了类似双向链表的数据结构，而L2，L3则是针对L1维护的一级索引和二级索引，所以我们可以skiplist中LEVEL的概念理解为维护的第几层的索引
0 条评论
回复 删除
下一页
