关键词：
----《大规模分布式存储系统：原理解析与架构实战》读书笔记
在了解了
Bitcask存储模型后,又開始研究LSM树存储引擎。LSM在实现的过程中使用了一个非常有意思的数据结构：跳跃表。之前在《算法导论公开课》中听过这一节。当时感觉这样的结构和二叉树简直是殊途同归，可是一直没有亲自己主动手实现过。这次又遇到了。就来实现试试看。话说跳跃表和各种平衡树一样，都是用来加速查询的。要随手实现一个B树不easy，可是实现一个跳跃表就简单非常多。
跳跃表的简介
跳跃列表一个有序链表，按层建造的。底层是一个普通的有序链表。每一个更高层都充当以下列表的"高速跑道"，查找一个元素时，能够先通过高层的“快车道”。在快车道上找不到时，从最接近目标元素的快车道逐步进入慢车道，直到最后找的目标元素。
分析的时候。经常使用的形状例如以下：
各层是全然分开的列表。可是在实际实现中，则使用的为例如以下结构：
这样的方式将多条联表的值合并到一起，同一时候使用指针来构造高层"快车道"。这样的方式管理起来简单。节省空间。
更具体的介绍，请看跳表SkipList。
跳跃表的复杂度分析以及概率因子p
来看看跳跃表的复杂度分析:
- 空间复杂度： O(n) （期望）
- 跳跃表高度： O(logn) （期望）
相关操作的时间复杂度：
- 查找： O(logn) （期望）
- 插入： O(logn) （期望）
- 删除： O(logn) （期望）
跳跃表的操作时间负责度是基于概率的，全部加上了期望。
在层 i 中的元素按某个固定的概率 p 出如今层 i+1 中。当p=1/2或者1/e的时候查找的性能最好。
更具体的对照。请看到这篇文章：跳跃表。其中对不同概率的P对查询性能的影响做了对照。
跳跃表的高度
实际使用时。假设高度太高。会造成空间浪费。我们要做一个空间和时间的平衡。那么跳跃表的高度多少最合适？
如果跳跃表中的元素个数为N，当跳跃表的高度为log(N)时，跳跃表进化为一个二叉树结构，其查询次数与二分查找法一致。这无疑最理想的结果。
假设有一亿条记录，高度log(N)约等于30。redis中。最大高度也就是32。最多能够存几亿条记录。
通常，我们用不了这么多记录。所以高度能够减少一点。
跳跃表的实现
跳跃表在levledb和redis中均有实现。
二者都是用C实现的。我这个实现是C++版本号的
主要特点为：
- 支持模板
- 0.2版本号添加了对迭代器和反向迭代器的支持
- 可自己定义高度，默觉得8。0.2版本号版本号改为了16
由于高度为8的话适合几百条的记录，这时候，选用跳跃表并没有太多优势，不如之间使用排序数组。将默认值改为16的话，能够方便几万条记录大小的地方使用。 - 概率p:临时使用p=1/2
- 做过单元測试，放心使用啦
初始版本号简单直接。支持的函数为insert,find,remove。不支持范围操作。0.2版本号增了对了迭代器的支持。
另外，在实现的时候也遇到一些问题，要注意模板编程与平时编程有所不同，平时编程通常实现和定义分离，分别放在.cpp和.h中。
可是模板编程编写的一般是没有具现的实现。为了方便。一般定义和实现都会放在.h文件里。
初始版本号简单直接，支持的函数为insert,find,remove。不再介绍。以下是0.2版本号实现的函数及其功能：
void insert(const_value_type &value)
在当前表中插入value值。值能够反复。
void remove(const_value_type &value)
删除第一个值为value的元素。
反复值须要多次删除
void clear()
清空跳跃表
iterator find(const_value_type &value)
返回第一个值为value的元素的迭代器，否则返回end.
iterator begin(int level = 0)
返回指向当前表中第level层的第一个元素的迭代器。使用begin的时候，能够指定遍历不同的层。默觉得最底层。这个实际上并非标准的迭代器。为了实现分层遍历进行了特化。
iterator end() const
返回指向当前表中最后一个元素的迭代器。
iterator rbegin() const
返回指向当前表中最后一个元素的反向迭代器。
iterator rend() const
返回指向表中第一个元素的反向迭代器。
unsigned long size()
返回当前表中元素的数目
unsigned int level()
返回当前表的总层数
unsigned int maxlevel()
返回当前表的能使用的最大层数
bool empty()
推断表是否为空
代码地址见上面的链接。
欢迎光临我的站点----蝴蝶忽然的博客园----人既无名的专栏。
假设阅读本文过程中有不论什么问题，请联系作者，转载请注明出处。
第一部分数据结构与对象跳跃表
下面是跳跃表的基本原理，REDIS的实现大致相同跳跃表的一个特点是，插入NODE是通过随机的方式来决定level的，比较奇特下面是skipList的一个介绍，转载来的，源地址：http://kenby.iteye.com/blog/1187303，为防止源地址丢失，故拷贝一份... 查看详情
《redis设计与实现》[第一部分]数据结构与对象-c源码阅读
四、跳跃表关键字：层高随机跳跃表支持平均O（logN）、最坏O(N)复杂度的结点查找，还可以通过顺序性操作来批量处理结点。在大部分情况下，跳跃表的效率可以和平衡树相媲美，因为跳跃表的实现比平衡... 查看详情
原来这就是传说中的跳跃表，不过如此（附：跳跃表的java实现）(代码片段)
1.什么是跳跃表？增加了向前指针的链表叫作跳表。跳表全称叫做跳跃表。跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快... 查看详情
跳跃表的原理及实现
1.跳跃表的原理 学过数据结构的都知道，在单链表中查询一个元素的时间复杂度为O(n)，即使该单链表是有序的，我们也不能通过2分的方式缩减时间复杂度。 如上图，我们要查询元素为55的结点... 查看详情
4跃进表
...询，还可以通过顺序性来批量处理节点；大多数情况下，跳跃表与平衡树效率差不多，并且因为跳跃表的实现比平衡树要来的更简单，所以可以使用跳跃表来替换平衡树。Redis使用跳跃表作为有序集合键的底层实现之一。如果一... 查看详情
skiplist(跳跃表)解析及其实现(代码片段)
目录导言查找结点的效率如何提升？什么是跳跃表？跳跃表必须是完美的？预备知识抛硬币实验模拟建表操作解析伪代码代码实现柔性数组跳跃表的创建与销毁跳跃表表头结构体定义跳跃表结点结构体定义建立跳跃表表头操作操... 查看详情
跳跃表c语言实现(代码片段)
...链表最末尾的元素，那么需要查找时间复杂度是O(n)。跳跃表就是为了解决这个问题而提出，跳跃表可以理解为在链表的基础上加上了多级索引。为了保证插入的均衡以及查询的速率，跳跃表的新节点插入时，会计... 查看详情
跳跃表c语言实现(代码片段)
...链表最末尾的元素，那么需要查找时间复杂度是O(n)。跳跃表就是为了解决这个问题而提出，跳跃表可以理解为在链表的基础上加上了多级索引。为了保证插入的均衡以及查询的速率，跳跃表的新节点插入时，会计... 查看详情
数据结构链表_双向链表的实现与分析
双向链表的实现与分析双向链表的组成：1、数据成员；2、指向下一个元素的next指针；3、指向前一个元素的prev指针。数据结构DListElmt：代表双向链表中的单个元素（节点）。数据结构DList：代表双向链表数据结构，该结构的成... 查看详情
万字总结！！redis数据结构与对象(代码片段)
....3解决键冲突3.4rehash3.5哈希表的扩展与收缩3.6渐进式rehash4跳跃表4.1跳跃表的实现4.2跳跃表节点4.3重点5整数集合5.1整数集合的实现5.2升级5.3降级5.4重点6压缩列表6 查看详情
数据结构——线性表(代码片段)
...结点静态链表小结应用题干:题目解析：代码实现SkipList(跳跃表)例题解析jmu-ds-链表分割题干题目分析代码实现jmu-ds-链表倒数第m个数题干题目解析代码实现两个有序序列的中位数题干题目解析代码实现一元多项式的乘法与加法运... 查看详情
concurrentskiplistmap源码分析
看一下跳跃表的示意图，途中蓝色的为头节点，头节点指向的是普通索引节点 通过上图可以看到跳跃表的基本结构，下面分析一下普通索引节点和头节点的源码，可以发现头节点和普通索引节点的区别就是头节点有level... 查看详情
数据结构——跳跃表(代码片段)
跳跃表介绍跳跃表（skiplist）是一种随机化的数据结构，是一种可以与平衡树媲美的层次化链表结构——查找、删除、添加等操作都可以在对数期望时间下完成，以下是一个典型的跳跃表例子：到底有多随机&#x... 查看详情
redis源码分析4---结构体---跳跃表
redis源码分析4---结构体---跳跃表 跳跃表是一种有序的数据结构，他通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的；跳跃表支持平均O（logN），最坏O（N）复杂度的节点查找，还可以通过顺序... 查看详情
跳跃表的实现和原理(代码片段)
1.跳跃表的原理 学过数据结构的都知道，在单链表中查询一个元素的时间复杂度为O(n)，即使该单链表是有序的，我们也不能通过2分的方式缩减时间复杂度。 如上图，我... 查看详情
数据结构——跳跃表(代码片段)
文章目录跳跃表介绍跳跃表原理查找插入删除跳跃表实现跳跃表节点跳跃表跳跃表初始化基本操作插入查找与删除随机化的方法实现代码跳跃表介绍跳跃表（skiplist）是一种随机化的数据结构，是一种可以与平衡树媲... 查看详情
跳跃表skiplist数据结构原理及实现
为什么选择跳表目前经常使用的平衡数据结构有：B树，红黑树，AVL树，SplayTree,Treep等。想象一下，给你一张草稿纸，一只笔，一个编辑器，你能立即实现一颗红黑树，或者AVL树出来吗？很难吧，这需要时间，要考虑很多细节，... 查看详情
读书笔记-《redis设计与实现》数据结构与对象(代码片段)
...2哈希算法3.3解决键冲突3.4rehash3.5渐进式rehash3.6重点回顾4.跳跃表4.1跳跃表的实现4.2跳跃表节点4.3跳跃表4.4重点回顾5.整数集合5.1整数集合的实现5.2升级5.3升级的好处5.3.1提升灵活性5.3.2节约内存5.4不支持降级5.5重点回顾6.压缩列表6... 查看详情