江苏龙网

  1. 主页 > 生活百科 > >

看完Redis源码还不理解跳跃表吗？

Redis


看完Redis源码还不理解跳跃表吗？

文章插图
 
前言在这里我们先回忆一下普通链表的时间复杂度，可以看到除了 look up 操作是 O(n) 的，其他操作都是 O(1) 的时间复杂度 。也就是说你需要随机访问里面的任何一个元素的话，它的时间复杂度平均值是 O(n) 的，这也就是链表它的问题所在 。从这里可以看到并没有所谓完美的一种数据结构，如果完美那就不需要 Array 或者 LInked List 这两个数据结构并存了，就直接使用最牛逼的数据结构即可 。所以相当于各有优劣，看你的使用场景在什么地方，作为完整性比较，我这里把两种时间复杂度都列出来 。
Linked List 的时间复杂度
看完Redis源码还不理解跳跃表吗？

文章插图
 
Array 的时间复杂度
看完Redis源码还不理解跳跃表吗？

文章插图
 
注意：正常情况下数组的 prepend 操作的时间复杂度是 O(n)，但是可以进行特殊优化到 O(1) 。采用的方式是申请稍微大一些的内存空间，然后在数组开始预留一部分空间，然后 prepend 的操作则是把头下标前移一个位置即可 。
跳表 Skip List前面回顾了 Array 和 Linked List 的两种结构的时间复杂度，有一种情况下链表它的速度在 O(n) 这一块，就会觉得不太够用，我们来看一下这种情况指的是什么？
链表元素有序的时候
看完Redis源码还不理解跳跃表吗？

文章插图
 
注意是指整个元素，如果是有序的话，在有些时候，比如在数据库里面也好，或者是在其他对一些有序的树进行查询的时候，即使用链表这种方式存储的话，我们发现它的元素是有序的，比如说下面这个升序链表，134578910 它是升序排列的，这个时候我们要快速地查询，比如 9 在什么地方或者查询 5，是不是在这个链表里面出现，这时候你会发现，如果是用普通的数组可以进行二分查找可以很快查到5所在的位置，以及查询到一个元素是否存在 。
一个有序的数组里面存在，那么问题来了，如果是有序的，但是是链表的情况下应该怎样有效地加速呢？于是在近代1990年前后，一种新的数据结构出现了，它的名字叫做 跳表 。
跳表的特点注意：只能用于元素有序的情况 。
所以，跳表（skip list）对表的是平衡树（AVL Tree）和 二分查找，是一种 插入/删除/搜索 都是 O(logn) 的数据结构 。1989 年出现 。
不管是平衡树、二叉搜索树其他哪些树的话都是在1960年和196几年就已经出现了，它的出现比平衡树和二分查找以及所谓的一些高级数据结构出现的要晚 。比其他的晚了接近30年，最后才出现，这就是为什么很多老的数据结构的话，用平衡二叉树会多一点，而一些比较新的，特别是在元素个数不多的情况的情况下，用的全部都是跳表，也就是说在更新换代了 。
它的最大优势是原理简单、容易实现、方便扩展、效率更高 。因此在一些热门的项目里用来替代平衡树，如 redis、LevelDB等 。
跳跃表（skiplist）是一种随机化的数据，由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出，跳跃表以有序的方式在层次化的链表中保存元素，效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成，并且比起平衡树来说，跳跃表的实现要简单直观得多 。
如何给有序的链表加速假设有一个有序的链表，1 3 4 5 7 8 9 10 这么一个原始的链表 。它的时间复杂度查询肯定是 O(n) 的，那么问一下如何优化？如何进行简单优化？可以让它的查询时间复杂度变低，也就是加速它的查询 。
我们可以思考一些，如果你来比如说我要很快地查到 7，有没有在链表中存在和它的位置在哪儿的话，你能够非常快的查询出来吗？

看完Redis源码还不理解跳跃表吗？

文章插图
 
  • 时间复杂度：查询 O(n)
  • 简单优化：添加头尾指针
上面这么一个结构，它是一维的数据结构，现在它是有序了，也就是说我们有附加的信息了，那么如何加速对吧？一般来说这种加速的方式的话，就类似于星际穿越里面这有点玄学，但是你一定要记住一个概念就行了，一维的数据结构要加速的话，经常采用的方式就是升维也就是说变成二维 。为什么要多一层维度，因为你多了一个维度之后，就会有多一级的信息在里面，这样多一级的信息就可以帮助你可以很快地得到一维里面你必须挨个走才能走到的那些元素


推荐阅读


上一篇：仓鼠毛色变黑 为什么仓鼠的毛色越来越黑

下一篇：房子卖了很后悔怎么办心里好难过 房子卖亏了心里难受怎么办