AI
推荐
模板社区
专题
登录
免费注册
首页
流程图
详情
跳表
2019-07-17 10:08:29
1
举报
分享方式
使用 (￥5)
跳表
SkipList
模版推荐
作者其他创作
大纲/内容
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的概念理解为维护的第几层的索引
收藏
立即使用
I/O event、I/O operation 在ChannelPipeline的流动过程
收藏
立即使用
主从服务器复制过程
收藏
立即使用
跳表
收藏
立即使用
spring ioc容器接口梳理
insaneXs
职业：软件工程师
去主页
Collect
Get Started
Redis数据类型与底层数据结构关系
Collect
Get Started
Java面试知识点大纲
Collect
Get Started
跳表一级索引
Collect
Get Started
跳表
评论
0
条评论
下一页
Document
