redis使用skiplist跳表的缘由解析

1.甚么是skiplist跳表

跳表是一种特殊的链表，特殊的点在于其可以进行二分查找。普通的链表要查找元素只能挨个遍历链表中的所有元素，而跳表则利用了空间换时间的策略，在原来有序链表的基础上面增加了多级索引，然后利用类似二分查找的思路来快速实现查找功能。跳表可以支持快速的查找，插入，删除等操作，时间复杂度为O(logn)，空间复杂度为O(n)。

2.随机层数的计算

跳表在节点插入时候，会随机出一个层数，依托这个随机数操作构建的多层链表结构，能保证一个比较不错的查找性能。这个随机层数不是一个普通的服从均匀散布的随机数，具体的计算逻辑以下

1.首先，每一个节点肯定都有第1层指针（每一个节点都在第1层链表里）。
2.如果一个节点有第i层(i>=1)指针（即节点已在第1层到第i层链表中），那末它有第(i+1)层指针的几率为p。
3.节点最大的层数不允许超过一个最大值，记为MaxLevel。

伪代码以下

randomLevel逻辑中包括有两个参数，一个是几率p，一个是最大层数MaxLevel。在redis的实现中，这两个参数分别为

该部份内容来自于以下文档:

skiplist的算法性能分析

关于跳表本身更详细的讲授可以参考上述文档。

3.redis为何要使用跳表

常常会有人问这个问题，redis中为何要使用跳表？

这个问题，redis作者已给出过明确答案

1. They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
2. A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
3. They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

依照我自己的理解，略微翻译一下就是
1.跳表不是非常吃内存，并且基本是取决于你自己。你可以通过改变参数p(第二部份中提到的)，从而到达比btree消耗更少内存的目的。

2.redis中的zset结构常常会使用ZRANGE或ZREVRANGE这类操作，这个时候遍历跳表就相当于遍历一个普通的链表。这类情况下，跳表的表现跟btree一样优秀。

3.很多人认为这一点是最重要的缘由。跳表实现起来更容易，只需要一点点代码就可以到达效果，修改起来也很方便。

到此这篇关于redis为何要使用skiplist跳表的文章就介绍到这了,更多相关redis skiplist跳表内容请搜索之前的文章或继续浏览下面的相关文章希望大家以后多多支持！