备案网站查询,上哪里建设个人网站,最新项目加盟代理,wordpress指针美化转载#xff1a;https://www.cnblogs.com/lnlvinso/p/8848883.html 结果#xff1a;skiplist的高度是个随机值。
SkipList理解 记下自己对跳表SkipList的理解。 SkipList采用空间换时间的思想#xff0c;通过增加数据间的链接#xff0c;达到加快查找速度的目的。 数据库L…转载https://www.cnblogs.com/lnlvinso/p/8848883.html 结果skiplist的高度是个随机值。
SkipList理解 记下自己对跳表SkipList的理解。 SkipList采用空间换时间的思想通过增加数据间的链接达到加快查找速度的目的。 数据库LevelDB和RocksDB中用到了SkipListRedis中的有序set即zset也用到了SkipList。Java中也提供了ConcurrentSkipListMap在并发量大的情况下ConcurrentSkipListMap性能好。 先看SkipList的查找过程引用网上的经典图片查找19。注意的是数据是有序的。 查找的过程从上至下查找指针所经历的位置顺序如图中的123直到找到目标数据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层节点的数量是k1层节点的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 1;while ((random()0xFFFF) (ZSKIPLIST_P * 0xFFFF))level 1;return (levelZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
} 执行level 1;的概率为ZSKIPLIST_P也就是说k层节点的数量是k1层节点的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使用的随机算法。
templatetypename Key, class Comparator
int SkipListKey,Comparator::RandomHeight() {// Increase height with probability 1 in kBranchingstatic const unsigned int kBranching 4;int height 1;while (height kMaxHeight ((rnd_.Next() % kBranching) 0)) {height;}assert(height 0);assert(height kMaxHeight);return height;
}(rnd_.Next() % kBranching) 0)的概率为1/kBranching所以LevelDB中的SkipList也是一棵四叉树kBranching 4;不就是这个意思吗^_^。 总结skiplist是有序的采用类似二分法方式进行查找。查找、插入的平均时间复杂度是O(ln2)。
