跳跃表的分析与实现

----《大规模分布式存储系统:原理解析与架构实战》读书笔记

在了解了

Bitcask存储模型后,又开始研究LSM树存储引擎。LSM在实现的过程中使用了一个很有意思的数据结构:跳跃表。之前在《算法导论公开课》中听过这一节。当时感觉这种结构和二叉树简直是殊途同归,但是一直没有亲自动手实现过。这次又遇到了,就来实现试试看。话说跳跃表和各种平衡树一样,都是用来加速查询的。要随手实现一个B树不容易,但是实现一个跳跃表就简单很多。

跳跃表的简单介绍

跳跃列表一个有序链表,按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的"快速跑道",查找一个元素时,可以先通过高层的“快车道”,在快车道上找不到时,从最接近目标元素的快车道逐步进入慢车道,直到最后找的目标元素。

分析的时候,常用的形状如下:  

各层是完全分开的列表。但是在实际实现中,则使用的为如下结构:

这种方式将多条联表的值合并到一起,同时使用指针来构造高层"快车道"。这种方式管理起来简单,节省空间。

更详细的介绍,请看跳表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()
判断表是否为空

代码地址见上面的链接。



欢迎光临我的网站----蝴蝶忽然的博客园----人既无名的专栏

如果阅读本文过程中有任何问题,请联系作者,转载请注明出处!

时间: 2014-07-16

跳跃表的分析与实现的相关文章

大家好,问大家一个问题,关于跳跃表的

问题描述 跳跃表是怎么查找的,具体的过程是什么呢?请帮忙解释下,谢谢 解决方案 我就不贴图了,你可以看我的这篇文章跳跃表(Skip List)http://deepfuture.iteye.com/blog/954342解决方案二:跳跃表(Skip List)是1987年才诞生的一种崭新的数据结构,它在进行查找.插入.删除等操作时的期望时间复杂度均为O(logn),有着近乎替代平衡树的本领.而且最重要的一点,就是它的编程复杂度较同类的AVL树,红黑树等要低得多,这使得其无论是在理解还是在推广性上

浅析SkipList跳跃表原理及代码实现

本文将总结一种数据结构:跳跃表.前半部分跳跃表性质和操作的介绍直接摘自<让算法的效率跳起来--浅谈"跳跃表"的相关操作及其应用>上海市华东师范大学第二附属中学 魏冉.之后将附上跳跃表的源代码,以及本人对其的了解.难免有错误之处,希望指正,共同进步.谢谢.     跳跃表(Skip List)是1987年才诞生的一种崭新的数据结构,它在进行查找.插入.删除等操作时的期望时间复杂度均为O(logn),有着近乎替代平衡树的本领.而且最重要的一点,就是它的编程复杂度较同类的AVL树

怎样对ACCESS数据库中的表进行分析和优化

  我们先打开一个要进行分析的数据库,然后单击"工具"菜单上的"分析"选项,弹出的菜单上有"表"."性能"和"文档管理器"三个命令.这三个命令可以对相应的内容进行优化. 1.首先要对对表进行一下优化,单击"表"这个命令.ACCESS开始准备这个表分析器向导,在这个向导的第一页中,为我们提供了建立表时常见的一个问题.这就是表或查询中多次存储了相同的信息,而且重复的信息将会给我们带来很多问题

跳跃表Skip List的原理和实现

二分查找和AVL树查找 二分查找要求元素可以随机访问,所以决定了需要把元素存储在连续内存.这样查找确实很快,但是插入和删除元素的时候,为了保证元素的有序性,就需要大量的移动元素了. 如果需要的是一个能够进行二分查找,又能快速添加和删除元素的数据结构,首先就是二叉查找树,二叉查找树在最坏情况下可能变成一个链表, 于是就出现了平衡二叉树,根据平衡的算法不同有AVL树,B-Tree,B+Tree,红黑树等,但是AVL树实现起来比较复杂, 平衡操作较难理解,这时候就可以用SkipList跳跃表结构. 什

【项目实战】---需求分析+表关系分析

    SSH---小编初次接触的时候傻傻的以为这个跟SHE有什么关系呢?又是哪路明星歌手,后来才知道小编又土鳖了,原来SSH是这个样子滴,百度百科对她这样阐述,SSH即 Spring + Struts +Hibernate. Struts对Model,View和Controller都提供了对应的组件.Spring是一个轻量级的控制反转(IOC)和面向切面(AOP)的容器框架,她由Rod Johnson创建.她是为了解决企业应用开发的复杂性而创建的.Spring使用基本的JavaBean来完成以

[redis设计与实现][4]基本数据结构——跳跃表

Redis使用跳跃表和字典共同来实现有序集合键(sorted set). 定义: 跳跃表节点: [cce lang="c"] typedef struct zskiplistNode { //成员对象 robj *obj; //分值 double score; //后退指针 struct zskiplistNode *backward; //层结构 struct zskiplistLevel { //前进指针 struct zskiplistNode *forward; //跨度 un

mysql锁表机制分析与锁表问题

为了给高并发情况下的mysql进行更好的优化,有必要了解一下mysql查询更新时的锁表机制.一.概述MySQL有三种锁的级别:页级.表级.行级. MyISAM和MEMORY存储引擎采用的是表级锁(table-level locking):BDB存储引擎采用的是页面锁(page-level locking),但也支持表级锁:InnoDB存储引擎既支持行级锁(row-level locking),也支持表级锁,但默认情况下是采用行级锁. MySQL这3种锁的特性可大致归纳如下: 表级锁:开销小,加锁

C++虚函数表实例分析_C 语言

多态是C++面向对象程序设计的一个重要特性.以前看到虚函数觉得很神奇,为什么就能实现多态了呢.最初的时候曾设想,要实现运行时多态,应该让对象的某个部分始终指向一个固定的地址,子类继承的时候,就修改这个地址的内容.这样,父类和子类都是到同一个固定地址去读取内容,在运行时就能表现不同行为. 在看了<深度探索c++对象模型>之后,发现思路是类似的.在对象中,有一个指针指向一张虚函数表,里面按照次序存放了每一个虚函数,当子类继承的时候,即到虚函数表的指定位置去修改函数地址.当我们通过父类指针来操作一个

算法: skiplist 跳跃表代码实现和原理

SkipList在leveldb以及lucence中都广为使用,是比较高效的数据结构.由于它的代码以及原理实现的简单性,更为人们所接受. 所有操作均从上向下逐层查找,越上层一次next操作跨度越大.其实现是典型的空间换时间. Skip lists are data structures that use probabilistic balancing rather than strictly enforced balancing. As a result, the algorithms for