1.什么是skiplist跳表

跳表是一種特殊的鏈表，特殊的點在于其可以進行二分查找。普通的鏈表要查找元素只能挨個遍歷鏈表中的所有元素，而跳表則利用了空間換時間的策略，在原來有序鏈表的基礎(chǔ)上面增加了多級索引，然后利用類似二分查找的思路來快速實現(xiàn)查找功能。跳表可以支持快速的查找，插入，刪除等操作，時間復(fù)雜度為O(logn)，空間復(fù)雜度為O(n)。

2.隨機層數(shù)的計算

跳表在節(jié)點插入時候，會隨機出一個層數(shù)，依靠這個隨機數(shù)操作構(gòu)建的多層鏈表結(jié)構(gòu)，能保證一個比較好的查找性能。這個隨機層數(shù)不是一個普通的服從均勻分布的隨機數(shù)，具體的計算邏輯如下

1.首先，每個節(jié)點肯定都有第1層指針（每個節(jié)點都在第1層鏈表里）。
2.如果一個節(jié)點有第i層(i>=1)指針（即節(jié)點已經(jīng)在第1層到第i層鏈表中），那么它有第(i+1)層指針的概率為p。
3.節(jié)點最大的層數(shù)不允許超過一個最大值，記為MaxLevel。

偽代碼如下

randomLevel()
    level := 1
    // random()返回一個[0...1)的隨機數(shù)
    while random() < p and level < MaxLevel do
        level := level + 1
    return level

randomLevel邏輯中包含有兩個參數(shù)，一個是概率p，一個是最大層數(shù)MaxLevel。在redis的實現(xiàn)中，這兩個參數(shù)分別為

p = 1/4
MaxLevel = 32

該部分內(nèi)容來自于如下文檔:

skiplist的算法性能分析

關(guān)于跳表本身更詳細的講解可以參考上述文檔。

3.redis為什么要使用跳表

經(jīng)常會有人問這個問題，redis中為什么要使用跳表？

這個問題，redis作者已經(jīng)給出過明確答案

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.跳表不是非常吃內(nèi)存，并且基本是取決于你自己。你可以通過改變參數(shù)p(第二部分中提到的)，從而達到比btree消耗更少內(nèi)存的目的。

2.redis中的zset結(jié)構(gòu)經(jīng)常會使用ZRANGE或者ZREVRANGE這種操作，這個時候遍歷跳表就相當于遍歷一個普通的鏈表。這種情況下，跳表的表現(xiàn)跟btree一樣優(yōu)秀。

3.很多人認為這一點是最重要的原因。跳表實現(xiàn)起來更容易，只需要一點點代碼就能達到效果，修改起來也很方便。

到此這篇關(guān)于redis為什么要使用skiplist跳表的文章就介紹到這了,更多相關(guān)redis skiplist跳表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論