SkipList理解
记下自己对跳表SkipList的理解。
SkipList采用空间换时间的思想,通过增加数据间的链接,达到加快查找速度的目的。
数据库LevelDB和RocksDB中用到了SkipList,Redis中的有序set即zset也用到了SkipList。Java中也提供了ConcurrentSkipListMap,在并发量大的情况下,ConcurrentSkipListMap性能好。
先看SkipList的查找过程,引用网上的经典图片,查找19。注意的是数据是有序的。
查找的过程从上至下,查找指针所经历的位置顺序如图中的1,2,3,直到找到目标数据19。
再加一张图,是怎么二分法查找的。
SkipList中创建新结点时,产生一个在1~MAX_LEVEL之间的随机level值作为该结点的level。每个节点的高度是随机的。
MAX_LEVEL可以静态指定,也可以动态增长。
关于MAX_LEVEL,觉得这篇文章的解释是比较清楚的:https://blog.csdn.net/kisimple/article/details/38706729。下面是复制了部分的内容
每个节点所能reach到的最远的节点是随机的,正如作者所说,SkipList使用的是概率平衡而不是强制平衡。
O(logN)?
既然是随机算法,那怎么能保证O(logN)的复杂度?SkipList作者在论文中有给出了说明,这里从另一个角度说下我的理解。先定义一下,A node that has k forward pointers is called a level k node。假设k层节点的数量是k+1层节点的P倍,那么其实这个SkipList可以看成是一棵平衡的P叉树,从最顶层开始查找某个节点需要的时间是O(logpN),which is O(logN) when p is a constant。
下面看下Redis与LevelDB中实现SkipList所使用的随机算法。
Redis
在t_zset.c中找到了redis使用的随机算法。
/* Returns a random level for the new skiplist node we are going to create.
* The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
* (both inclusive), with a powerlaw-alike distribution where higher
* levels are less likely to be returned. */
int zslRandomLevel(void) {
int level = ;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += ;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
执行level += 1;的概率为ZSKIPLIST_P,也就是说k层节点的数量是k+1层节点的1/ZSKIPLIST_P倍。ZSKIPLIST_P(这个P是作者论文中的p)与ZSKIPLIST_MAXLEVEL在redis.h中定义,
#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
#define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4 */
所以redis中的SkipList相当于是一棵四叉树。
LevelDB
在skiplist.h中找到了LevelDB使用的随机算法。
template<typename Key, class Comparator>
int SkipList<Key,Comparator>::RandomHeight() {
// Increase height with probability 1 in kBranching
static const unsigned int kBranching = ;
int height = ;
while (height < kMaxHeight && ((rnd_.Next() % kBranching) == )) {
height++;
}
assert(height > );
assert(height <= kMaxHeight);
return height;
}
(rnd_.Next() % kBranching) == 0)的概率为1/kBranching,所以LevelDB中的SkipList也是一棵四叉树(kBranching = 4;不就是这个意思吗^_^)。
最新文章
- webpack vuejs项目学习心得
- Android ui 测试课堂笔记
- ubuntu14.04 archive sources.list
- Mongodb Management Studio
- POJ-2752 Seek the Name, Seek the Fame(KMP,前缀与后缀相等)
- How to use SourceGear DiffMerge in SourceSafe, TFS, and SVN【项目】
- Gvim 在进行文件对比时报cannot read or write temp files
- 字符串截取数字和点击radio显示不同内容
- 产生一个int数组,长度为100,并向其中随机插入1-100,不重复
- Java思维导图之Class对象
- 全面理解Java内存模型
- 【Learning】 莫比乌斯反演
- 2017-2018-1 Java演绎法 第四五周 作业
- JAVA_SE基础——40.super关键字
- ios WKWebView 与 JS 交互实战技巧
- 妙用this关键字
- python简单制作GIF
- springboot学习笔记-6 springboot整合RabbitMQ
- c#控件的动画显示效果
- FTP 服务搭建后不能访问问题解决