快捷導(dǎo)航

redis使用skiplist跳表的原因解析

更新時(shí)間：2022年10月13日 10:59:07 作者：bitcarmanlee

經(jīng)常會(huì)有人問這個(gè)問題，redis中為什么要使用跳表?這個(gè)問題，redis作者已經(jīng)給出過明確答案,今天通過本文再給大家講解下這個(gè)問題，對redis?skiplist跳表知識(shí)感興趣的朋友一起看看吧

1.什么是skiplist跳表

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

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

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

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

偽代碼如下

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

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

p = 1/4
MaxLevel = 32

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

skiplist的算法性能分析

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

3.redis為什么要使用跳表

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

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

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.
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.
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(第二部分中提到的)，從而達(dá)到比btree消耗更少內(nèi)存的目的。

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

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

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

您可能感興趣的文章: