Redis 使用跳表實(shí)現(xiàn)有序集合的方法
近幾年針對 Redis 面試時(shí)會涉及常見數(shù)據(jù)結(jié)構(gòu)的底層設(shè)計(jì)，其中就有這么一道比較有意思的面試題：“Redis 的有序集合底層為什么要用跳表，而不用平衡樹、紅黑樹或者 B+樹？”。
本文就以這道大廠常問的面試題為切入點(diǎn)，帶大家詳細(xì)了解一下跳表這個(gè)數(shù)據(jù)結(jié)構(gòu)。
本文整體脈絡(luò)如下圖所示，筆者會從有序集合的基本使用到跳表的源碼分析和實(shí)現(xiàn)，讓你會對 Redis 的有序集合底層實(shí)現(xiàn)的跳表有著更深刻的理解和掌握。
跳表在 Redis 中的運(yùn)用
這里我們需要先了解一下 Redis 用到跳表的數(shù)據(jù)結(jié)構(gòu)有序集合的使用，Redis 有個(gè)比較常用的數(shù)據(jù)結(jié)構(gòu)叫**有序集合(sorted set，簡稱 zset)**，正如其名它是一個(gè)可以保證有序且元素唯一的集合，所以它經(jīng)常用于排行榜等需要進(jìn)行統(tǒng)計(jì)排列的場景。
這里我們通過命令行的形式演示一下排行榜的實(shí)現(xiàn)，可以看到筆者分別輸入 3 名用戶：xiaoming、xiaohong、xiaowang，它們的score分別是 60、80、60，最終按照成績升級降序排列。
127.0.0.1:6379> zadd rankList 60 xiaoming (integer) 1 127.0.0.1:6379> zadd rankList 80 xiaohong (integer) 1 127.0.0.1:6379> zadd rankList 60 xiaowang (integer) 1 # 返回有序集中指定區(qū)間內(nèi)的成員，通過索引，分?jǐn)?shù)從高到低 127.0.0.1:6379> ZREVRANGE rankList 0 100 WITHSCORES 1) "xiaohong" 2) "80" 3) "xiaowang" 4) "60" 5) "xiaoming" 6) "60"
此時(shí)我們通過 object 指令查看 zset 的數(shù)據(jù)結(jié)構(gòu)，可以看到當(dāng)前有序集合存儲的還是**ziplist(壓縮列表)**。
127.0.0.1:6379> object encoding rankList "ziplist"
因?yàn)樵O(shè)計(jì)者考慮到 Redis 數(shù)據(jù)存放于內(nèi)存，為了節(jié)約寶貴的內(nèi)存空間，在有序集合元素小于 64 字節(jié)且個(gè)數(shù)小于 128 的時(shí)候，會使用 ziplist，而這個(gè)閾值的默認(rèn)值的設(shè)置就來自下面這兩個(gè)配置項(xiàng)。
zset-max-ziplist-value 64 zset-max-ziplist-entries 128
一旦有序集合中的某個(gè)元素超出這兩個(gè)其中的一個(gè)閾值它就會轉(zhuǎn)為 skiplist（實(shí)際是 dict+skiplist，還會借用字典來提高獲取指定元素的效率）。
我們不妨在添加一個(gè)大于 64 字節(jié)的元素，可以看到有序集合的底層存儲轉(zhuǎn)為 skiplist。
127.0.0.1:6379> zadd rankList 90 yigemingzihuichaoguo64zijiedeyonghumingchengyongyuceshitiaobiaodeshijiyunyong (integer) 1 # 超過閾值，轉(zhuǎn)為跳表 127.0.0.1:6379> object encoding rankList "skiplist"
也就是說，ZSet 有兩種不同的實(shí)現(xiàn)，分別是 ziplist 和 skiplist，具體使用哪種結(jié)構(gòu)進(jìn)行存儲的規(guī)則如下：
- 當(dāng)有序集合對象同時(shí)滿足以下兩個(gè)條件時(shí)，使用 ziplist：
ZSet 保存的鍵值對數(shù)量少于 128 個(gè)；
每個(gè)元素的長度小于 64 字節(jié)。
- 如果不滿足上述兩個(gè)條件，那么使用 skiplist 。
手寫一個(gè)跳表
為了更好的回答上述問題以及更好的理解和掌握跳表，這里可以通過手寫一個(gè)簡單的跳表的形式來幫助讀者理解跳表這個(gè)數(shù)據(jù)結(jié)構(gòu)。
我們都知道有序鏈表在添加、查詢、刪除的平均時(shí)間復(fù)雜都都是O(n)即線性增長，所以一旦節(jié)點(diǎn)數(shù)量達(dá)到一定體量后其性能表現(xiàn)就會非常差勁。而跳表我們完全可以理解為在原始鏈表基礎(chǔ)上，建立多級索引，通過多級索引檢索定位將增刪改查的時(shí)間復(fù)雜度變?yōu)镺(log n)。
可能這里說的有些抽象，我們舉個(gè)例子，以下圖跳表為例，其原始鏈表存儲按序存儲 1-10，有 2 級索引，每級索引的索引個(gè)數(shù)都是基于下層元素個(gè)數(shù)的一半。
假如我們需要查詢元素 6，其工作流程如下：
- 從 2 級索引開始，先來到節(jié)點(diǎn) 4。
- 查看 4 的后繼節(jié)點(diǎn)，是 8 的 2 級索引，這個(gè)值大于 6，說明 2 級索引后續(xù)的索引都是大于 6 的，沒有再往后搜尋的必要，我們索引向下查找。
- 來到 4 的 1 級索引，比對其后繼節(jié)點(diǎn)為 6，查找結(jié)束。
相較于原始有序鏈表需要 6 次，我們的跳表通過建立多級索引，我們只需兩次就直接定位到了目標(biāo)元素，其查尋的復(fù)雜度被直接優(yōu)化為**O(log n)**。
對應(yīng)的添加也是一個(gè)道理，假如我們需要在這個(gè)有序集合中添加一個(gè)元素 7，那么我們就需要通過跳表找到小于元素 7 的最大值，也就是下圖元素 6 的位置，將其插入到元素 6 的后面，讓元素 6 的索引指向新插入的節(jié)點(diǎn) 7，其工作流程如下：
- 從 2 級索引開始定位到了元素 4 的索引。
- 查看索引 4 的后繼索引為 8，索引向下推進(jìn)。
- 來到 1 級索引，發(fā)現(xiàn)索引 4 后繼索引為 6，小于插入元素 7，指針推進(jìn)到索引 6 位置。
- 繼續(xù)比較 6 的后繼節(jié)點(diǎn)為索引 8，大于元素 7，索引繼續(xù)向下。
- 最終我們來到 6 的原始節(jié)點(diǎn)，發(fā)現(xiàn)其后繼節(jié)點(diǎn)為 7，指針沒有繼續(xù)向下的空間，自此我們可知元素 6 就是小于插入元素 7 的最大值，于是便將元素 7 插入。
這里我們又面臨一個(gè)問題，我們是否需要為元素 7 建立索引，索引多高合適？
我們上文提到，理想情況是每一層索引是下一層元素個(gè)數(shù)的二分之一，假設(shè)我們的總共有 16 個(gè)元素，對應(yīng)各級索引元素個(gè)數(shù)應(yīng)該是：
1. 一級索引:16/2=8 2. 二級索引:8/2 =4 3. 三級索引:4/2=2
由此我們用數(shù)學(xué)歸納法可知：
1. 一級索引:16/2=16/2^1=8 2. 二級索引:8/2 => 16/2^2 =4 3. 三級索引:4/2=>16/2^3=2
假設(shè)元素個(gè)數(shù)為 n，那么對應(yīng) k 層索引的元素個(gè)數(shù) r 計(jì)算公式為:
r=n/2^k
同理我們再來推斷以下索引的最大高度，一般來說最高級索引的元素個(gè)數(shù)為 2，我們設(shè)元素總個(gè)數(shù)為 n，索引高度為 h，代入上述公式可得：
2= n/2^h => 2*2^h=n => 2^(h+1)=n => h+1=log2^n => h=log2^n -1
而 Redis 又是內(nèi)存數(shù)據(jù)庫，我們假設(shè)元素最大個(gè)數(shù)是65536，我們把65536代入上述公式可知最大高度為 16。所以我們建議添加一個(gè)元素后為其建立的索引高度不超過 16。
因?yàn)槲覀円蟊M可能保證每一個(gè)上級索引都是下級索引的一半，在實(shí)現(xiàn)高度生成算法時(shí)，我們可以這樣設(shè)計(jì)：
- 跳表的高度計(jì)算從原始鏈表開始，即默認(rèn)情況下插入的元素的高度為 1，代表沒有索引，只有元素節(jié)點(diǎn)。
- 設(shè)計(jì)一個(gè)為插入元素生成節(jié)點(diǎn)索引高度 level 的方法。
- 進(jìn)行一次隨機(jī)運(yùn)算，隨機(jī)數(shù)值范圍為 0-1 之間。
- 如果隨機(jī)數(shù)大于 0.5 則為當(dāng)前元素添加一級索引，自此我們保證生成一級索引的概率為50%，這也就保證了 1 級索引理想情況下只有一半的元素會生成索引。
- 同理后續(xù)每次隨機(jī)算法得到的值大于 0.5 時(shí)，我們的索引高度就加 1，這樣就可以保證節(jié)點(diǎn)生成的 2 級索引概率為25%，3 級索引為 12.5%**……
我們回過頭，上述插入 7 之后，我們通過隨機(jī)算法得到 2，即要為其建立 1 級索引：
最后我們再來說說刪除，假設(shè)我們這里要刪除元素 10，我們必須定位到當(dāng)前跳表各層元素小于 10 的最大值，索引執(zhí)行步驟為：
- 2 級索引 4 的后繼節(jié)點(diǎn)為 8，指針推進(jìn)。
- 索引 8 無后繼節(jié)點(diǎn)，該層無要刪除的元素，指針直接向下。
- 1 級索引 8 后繼節(jié)點(diǎn)為 10，說明 1 級索引 8 在進(jìn)行刪除時(shí)需要將自己的指針和 1 級索引 10 斷開聯(lián)系，將 10 刪除。
- 1 級索引完成定位后，指針向下，后繼節(jié)點(diǎn)為 9，指針推進(jìn)。
- 9 的后繼節(jié)點(diǎn)為 10，同理需要讓其指向 null，將 10 刪除。
模板定義
有了整體的思路之后，我們可以開始實(shí)現(xiàn)一個(gè)跳表了，首先定義一下跳表中的節(jié)點(diǎn)Node，從上文的演示中可以看出每一個(gè)Node它都包含以下幾個(gè)元素：
- 存儲的value值。
- 后繼節(jié)點(diǎn)的地址。
- 多級索引。
為了更方便統(tǒng)一管理Node后繼節(jié)點(diǎn)地址和多級索引指向的元素地址，筆者在Node中設(shè)置了一個(gè)forwards數(shù)組，用于記錄原始鏈表節(jié)點(diǎn)的后繼節(jié)點(diǎn)和多級索引的后繼節(jié)點(diǎn)指向。
以下圖為例，我們forwards數(shù)組長度為 5，其中索引 0記錄的是原始鏈表節(jié)點(diǎn)的后繼節(jié)點(diǎn)地址，而其余自底向上表示從 1 級索引到 4 級索引的后繼節(jié)點(diǎn)指向。
于是我們的就有了這樣一個(gè)代碼定義，可以看出筆者對于數(shù)組的長度設(shè)置為固定的 16**(上文的推算最大高度建議是 16)，默認(rèn)data為-1，節(jié)點(diǎn)最大高度maxLevel初始化為 1，注意這個(gè)maxLevel**的值代表原始鏈表加上索引的總高度。
/**
* 跳表索引最大高度為16
*/
private static final int MAX_LEVEL = 16;
class Node {
private int data = -1;
private Node[] forwards = new Node[MAX_LEVEL];
private int maxLevel = 0;
}元素添加
定義好節(jié)點(diǎn)之后，我們先實(shí)現(xiàn)以下元素的添加，添加元素時(shí)首先自然是設(shè)置data這一步我們直接根據(jù)將傳入的value設(shè)置到data上即可。
然后就是高度maxLevel的設(shè)置 ，我們在上文也已經(jīng)給出了思路，默認(rèn)高度為 1，即只有一個(gè)原始鏈表節(jié)點(diǎn)，通過隨機(jī)算法每次大于 0.5 索引高度加 1，由此我們得出高度計(jì)算的算法randomLevel()：
/**
* 理論來講，一級索引中元素個(gè)數(shù)應(yīng)該占原始數(shù)據(jù)的 50%，二級索引中元素個(gè)數(shù)占 25%，三級索引12.5% ，一直到最頂層。
* 因?yàn)檫@里每一層的晉升概率是 50%。對于每一個(gè)新插入的節(jié)點(diǎn)，都需要調(diào)用 randomLevel 生成一個(gè)合理的層數(shù)。
* 該 randomLevel 方法會隨機(jī)生成 1~MAX_LEVEL 之間的數(shù)，且 ：
* 50%的概率返回 1
* 25%的概率返回 2
* 12.5%的概率返回 3 ...
* @return
*/
private int randomLevel() {
int level = 1;
while (Math.random() > PROB && level < MAX_LEVEL) {
++level;
}
return level;
}然后再設(shè)置當(dāng)前要插入的Node和Node索引的后繼節(jié)點(diǎn)地址，這一步稍微復(fù)雜一點(diǎn)，我們假設(shè)當(dāng)前節(jié)點(diǎn)的高度為 4，即 1 個(gè)節(jié)點(diǎn)加 3 個(gè)索引，所以我們創(chuàng)建一個(gè)長度為 4 的數(shù)組maxOfMinArr ，遍歷各級索引節(jié)點(diǎn)中小于當(dāng)前value的最大值。
假設(shè)我們要插入的value為 5，我們的數(shù)組查找結(jié)果當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)和 1 級索引、2 級索引的前驅(qū)節(jié)點(diǎn)都為 4，三級索引為空。
然后我們基于這個(gè)數(shù)組maxOfMinArr 定位到各級的后繼節(jié)點(diǎn)，讓插入的元素 5 指向這些后繼節(jié)點(diǎn)，而maxOfMinArr指向 5，結(jié)果如下圖：
轉(zhuǎn)化成代碼就是下面這個(gè)形式，是不是很簡單呢？我們繼續(xù)：
/**
* 默認(rèn)情況下的高度為1，即只有自己一個(gè)節(jié)點(diǎn)
*/
private int levelCount = 1;
/**
* 跳表最底層的節(jié)點(diǎn)，即頭節(jié)點(diǎn)
*/
private Node h = new Node();
public void add(int value) {
//隨機(jī)生成高度
int level = randomLevel();
Node newNode = new Node();
newNode.data = value;
newNode.maxLevel = level;
//創(chuàng)建一個(gè)node數(shù)組，用于記錄小于當(dāng)前value的最大值
Node[] maxOfMinArr = new Node[level];
//默認(rèn)情況下指向頭節(jié)點(diǎn)
for (int i = 0; i < level; i++) {
maxOfMinArr[i] = h;
}
//基于上述結(jié)果拿到當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)
Node p = h;
for (int i = level - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
maxOfMinArr[i] = p;
}
//更新前驅(qū)節(jié)點(diǎn)的后繼節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)newNode
for (int i = 0; i < level; i++) {
newNode.forwards[i] = maxOfMinArr[i].forwards[i];
maxOfMinArr[i].forwards[i] = newNode;
}
//如果當(dāng)前newNode高度大于跳表最高高度則更新levelCount
if (levelCount < level) {
levelCount = level;
}
}元素查詢
查詢邏輯比較簡單，從跳表最高級的索引開始定位找到小于要查的 value 的最大值，以下圖為例，我們希望查找到節(jié)點(diǎn) 8：
- 跳表的 3 級索引首先找找到 5 的索引，5 的 3 級索引forwards[3]指向空，索引直接向下。
- 來到 5 的 2 級索引，其后繼forwards[2]指向 8，繼續(xù)向下。
- 5 的 1 級索引forwards[1]指向索引 6，繼續(xù)向前。
- 索引 6 的forwards[1]指向索引 8，繼續(xù)向下。
- 我們在原始節(jié)點(diǎn)向前找到節(jié)點(diǎn) 7。
- 節(jié)點(diǎn) 7 后續(xù)就是節(jié)點(diǎn) 8，繼續(xù)向前為節(jié)點(diǎn) 8，無法繼續(xù)向下，結(jié)束搜尋。
- 判斷 7 的前驅(qū)，等于 8，查找結(jié)束。
所以我們的代碼實(shí)現(xiàn)也很上述步驟差不多，從最高級索引開始向前查找，如果不為空且小于要查找的值，則繼續(xù)向前搜尋，遇到不小于的節(jié)點(diǎn)則繼續(xù)向下，如此往復(fù)，直到得到當(dāng)前跳表中小于查找值的最大節(jié)點(diǎn)，查看其前驅(qū)是否等于要查找的值：
public Node get(int value) {
Node p = h;
//找到小于value的最大值
for (int i = levelCount - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
}
//如果p的前驅(qū)節(jié)點(diǎn)等于value則直接返回
if (p.forwards[0] != null && p.forwards[0].data == value) {
return p.forwards[0];
}
return null;
}元素刪除
最后是刪除邏輯，需要查找各層級小于要刪除節(jié)點(diǎn)的最大值，假設(shè)我們要刪除 10：
- 3 級索引得到小于 10 的最大值為 5，繼續(xù)向下。
- 2 級索引從索引 5 開始查找，發(fā)現(xiàn)小于 10 的最大值為 8，繼續(xù)向下。
- 同理 1 級索引得到 8，繼續(xù)向下。
- 原始節(jié)點(diǎn)找到 9。
- 從最高級索引開始，查看每個(gè)小于 10 的節(jié)點(diǎn)后繼節(jié)點(diǎn)是否為 10，如果等于 10，則讓這個(gè)節(jié)點(diǎn)指向 10 的后繼節(jié)點(diǎn)，將節(jié)點(diǎn) 10 及其索引交由 GC 回收。
/**
* 刪除
*
* @param value
*/
public void delete(int value) {
Node p = h;
//找到各級節(jié)點(diǎn)小于value的最大值
Node[] updateArr = new Node[levelCount];
for (int i = levelCount - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
updateArr[i] = p;
}
//查看原始層節(jié)點(diǎn)前驅(qū)是否等于value，若等于則說明存在要刪除的值
if (p.forwards[0] != null && p.forwards[0].data == value) {
//從最高級索引開始查看其前驅(qū)是否等于value，若等于則將當(dāng)前節(jié)點(diǎn)指向value節(jié)點(diǎn)的后繼節(jié)點(diǎn)
for (int i = levelCount - 1; i >= 0; i--) {
if (updateArr[i].forwards[i] != null && updateArr[i].forwards[i].data == value) {
updateArr[i].forwards[i] = updateArr[i].forwards[i].forwards[i];
}
}
}
//從最高級開始查看是否有一級索引為空，若為空則層級減1
while (levelCount > 1 && h.forwards[levelCount - 1] == null) {
levelCount--;
}
}完整代碼以及測試
完整代碼如下，讀者可自行參閱:
public class SkipList {
/**
* 跳表索引最大高度為16
*/
private static final int MAX_LEVEL = 16;
/**
* 每個(gè)節(jié)點(diǎn)添加一層索引高度的概率為二分之一
*/
private static final float PROB = 0.5 f;
/**
* 默認(rèn)情況下的高度為1，即只有自己一個(gè)節(jié)點(diǎn)
*/
private int levelCount = 1;
/**
* 跳表最底層的節(jié)點(diǎn)，即頭節(jié)點(diǎn)
*/
private Node h = new Node();
public SkipList() {}
public class Node {
private int data = -1;
/**
*
*/
private Node[] forwards = new Node[MAX_LEVEL];
private int maxLevel = 0;
@Override
public String toString() {
return "Node{" +
"data=" + data +
", maxLevel=" + maxLevel +
'}';
}
}
public void add(int value) {
//隨機(jī)生成高度
int level = randomLevel();
Node newNode = new Node();
newNode.data = value;
newNode.maxLevel = level;
//創(chuàng)建一個(gè)node數(shù)組，用于記錄小于當(dāng)前value的最大值
Node[] maxOfMinArr = new Node[level];
//默認(rèn)情況下指向頭節(jié)點(diǎn)
for (int i = 0; i < level; i++) {
maxOfMinArr[i] = h;
}
//基于上述結(jié)果拿到當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)
Node p = h;
for (int i = level - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
maxOfMinArr[i] = p;
}
//更新前驅(qū)節(jié)點(diǎn)的后繼節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)newNode
for (int i = 0; i < level; i++) {
newNode.forwards[i] = maxOfMinArr[i].forwards[i];
maxOfMinArr[i].forwards[i] = newNode;
}
//如果當(dāng)前newNode高度大于跳表最高高度則更新levelCount
if (levelCount < level) {
levelCount = level;
}
}
/**
* 理論來講，一級索引中元素個(gè)數(shù)應(yīng)該占原始數(shù)據(jù)的 50%，二級索引中元素個(gè)數(shù)占 25%，三級索引12.5% ，一直到最頂層。
* 因?yàn)檫@里每一層的晉升概率是 50%。對于每一個(gè)新插入的節(jié)點(diǎn)，都需要調(diào)用 randomLevel 生成一個(gè)合理的層數(shù)。
* 該 randomLevel 方法會隨機(jī)生成 1~MAX_LEVEL 之間的數(shù)，且 ：
* 50%的概率返回 1
* 25%的概率返回 2
* 12.5%的概率返回 3 ...
* @return
*/
private int randomLevel() {
int level = 1;
while (Math.random() > PROB && level < MAX_LEVEL) {
++level;
}
return level;
}
public Node get(int value) {
Node p = h;
//找到小于value的最大值
for (int i = levelCount - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
}
//如果p的前驅(qū)節(jié)點(diǎn)等于value則直接返回
if (p.forwards[0] != null && p.forwards[0].data == value) {
return p.forwards[0];
}
return null;
}
/**
* 刪除
*
* @param value
*/
public void delete(int value) {
Node p = h;
//找到各級節(jié)點(diǎn)小于value的最大值
Node[] updateArr = new Node[levelCount];
for (int i = levelCount - 1; i >= 0; i--) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
updateArr[i] = p;
}
//查看原始層節(jié)點(diǎn)前驅(qū)是否等于value，若等于則說明存在要刪除的值
if (p.forwards[0] != null && p.forwards[0].data == value) {
//從最高級索引開始查看其前驅(qū)是否等于value，若等于則將當(dāng)前節(jié)點(diǎn)指向value節(jié)點(diǎn)的后繼節(jié)點(diǎn)
for (int i = levelCount - 1; i >= 0; i--) {
if (updateArr[i].forwards[i] != null && updateArr[i].forwards[i].data == value) {
updateArr[i].forwards[i] = updateArr[i].forwards[i].forwards[i];
}
}
}
//從最高級開始查看是否有一級索引為空，若為空則層級減1
while (levelCount > 1 && h.forwards[levelCount - 1] == null) {
levelCount--;
}
}
public void printAll() {
Node p = h;
//基于最底層的非索引層進(jìn)行遍歷，只要后繼節(jié)點(diǎn)不為空，則速速出當(dāng)前節(jié)點(diǎn)，并移動到后繼節(jié)點(diǎn)
while (p.forwards[0] != null) {
System.out.println(p.forwards[0]);
p = p.forwards[0];
}
}
}對應(yīng)測試代碼和輸出結(jié)果如下：
public static void main(String[] args) {
SkipList skipList = new SkipList();
for (int i = 0; i < 24; i++) {
skipList.add(i);
}
System.out.println("**********輸出添加結(jié)果**********");
skipList.printAll();
SkipList.Node node = skipList.get(22);
System.out.println("**********查詢結(jié)果:" + node+" **********");
skipList.delete(22);
System.out.println("**********刪除結(jié)果**********");
skipList.printAll();
}輸出結(jié)果:
**********輸出添加結(jié)果**********
Node{data=0, maxLevel=2}
Node{data=1, maxLevel=3}
Node{data=2, maxLevel=1}
Node{data=3, maxLevel=1}
Node{data=4, maxLevel=2}
Node{data=5, maxLevel=2}
Node{data=6, maxLevel=2}
Node{data=7, maxLevel=2}
Node{data=8, maxLevel=4}
Node{data=9, maxLevel=1}
Node{data=10, maxLevel=1}
Node{data=11, maxLevel=1}
Node{data=12, maxLevel=1}
Node{data=13, maxLevel=1}
Node{data=14, maxLevel=1}
Node{data=15, maxLevel=3}
Node{data=16, maxLevel=4}
Node{data=17, maxLevel=2}
Node{data=18, maxLevel=1}
Node{data=19, maxLevel=1}
Node{data=20, maxLevel=1}
Node{data=21, maxLevel=3}
Node{data=22, maxLevel=1}
Node{data=23, maxLevel=1}
**********查詢結(jié)果:Node{data=22, maxLevel=1} **********
**********刪除結(jié)果**********
Node{data=0, maxLevel=2}
Node{data=1, maxLevel=3}
Node{data=2, maxLevel=1}
Node{data=3, maxLevel=1}
Node{data=4, maxLevel=2}
Node{data=5, maxLevel=2}
Node{data=6, maxLevel=2}
Node{data=7, maxLevel=2}
Node{data=8, maxLevel=4}
Node{data=9, maxLevel=1}
Node{data=10, maxLevel=1}
Node{data=11, maxLevel=1}
Node{data=12, maxLevel=1}
Node{data=13, maxLevel=1}
Node{data=14, maxLevel=1}
Node{data=15, maxLevel=3}
Node{data=16, maxLevel=4}
Node{data=17, maxLevel=2}
Node{data=18, maxLevel=1}
Node{data=19, maxLevel=1}
Node{data=20, maxLevel=1}
Node{data=21, maxLevel=3}
Node{data=23, maxLevel=1}
和其余三種數(shù)據(jù)結(jié)構(gòu)的比較
最后，我們再來回答一下文章開頭的那道面試題: “Redis 的有序集合底層為什么要用跳表，而不用平衡樹、紅黑樹或者 B+樹？”。
平衡樹 vs 跳表
先來說說它和平衡樹的比較，平衡樹我們又會稱之為 AVL 樹，是一個(gè)嚴(yán)格的平衡二叉樹，平衡條件必須滿足（所有節(jié)點(diǎn)的左右子樹高度差不超過 1，即平衡因子為范圍為 [-1,1]）。平衡樹的插入、刪除和查詢的時(shí)間復(fù)雜度和跳表一樣都是 O(log n)。
對于范圍查詢來說，它也可以通過中序遍歷的方式達(dá)到和跳表一樣的效果。但是它的每一次插入或者刪除操作都需要保證整顆樹左右節(jié)點(diǎn)的絕對平衡，只要不平衡就要通過旋轉(zhuǎn)操作來保持平衡，這個(gè)過程是比較耗時(shí)的。
跳表誕生的初衷就是為了克服平衡樹的一些缺點(diǎn)，跳表的發(fā)明者在論文《Skip lists: a probabilistic alternative to balanced trees》中有詳細(xì)提到：
Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.
跳表是一種可以用來代替平衡樹的數(shù)據(jù)結(jié)構(gòu)。跳表使用概率平衡而不是嚴(yán)格強(qiáng)制的平衡，因此，跳表中的插入和刪除算法比平衡樹的等效算法簡單得多，速度也快得多。
筆者這里也貼出了 AVL 樹插入操作的核心代碼，可以看出每一次添加操作都需要進(jìn)行一次遞歸定位插入位置，然后還需要根據(jù)回溯到根節(jié)點(diǎn)檢查沿途的各層節(jié)點(diǎn)是否失衡，再通過旋轉(zhuǎn)節(jié)點(diǎn)的方式進(jìn)行調(diào)整。
// 向二分搜索樹中添加新的元素(key, value)
public void add(K key, V value) {
root = add(root, key, value);
}
// 向以node為根的二分搜索樹中插入元素(key, value)，遞歸算法
// 返回插入新節(jié)點(diǎn)后二分搜索樹的根
private Node add(Node node, K key, V value) {
if (node == null) {
size++;
return new Node(key, value);
}
if (key.compareTo(node.key) < 0)
node.left = add(node.left, key, value);
else if (key.compareTo(node.key) > 0)
node.right = add(node.right, key, value);
else // key.compareTo(node.key) == 0
node.value = value;
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
int balanceFactor = getBalanceFactor(node);
// LL型需要右旋
if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
return rightRotate(node);
}
//RR型失衡需要左旋
if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
return leftRotate(node);
}
//LR需要先左旋成LL型，然后再右旋
if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
//RL
if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}紅黑樹 vs 跳表
紅黑樹（Red Black Tree）也是一種自平衡二叉查找樹，它的查詢性能略微遜色于 AVL 樹，但插入和刪除效率更高。紅黑樹的插入、刪除和查詢的時(shí)間復(fù)雜度和跳表一樣都是 O(log n)。
紅黑樹是一個(gè)黑平衡樹，即從任意節(jié)點(diǎn)到另外一個(gè)葉子葉子節(jié)點(diǎn)，它所經(jīng)過的黑節(jié)點(diǎn)是一樣的。當(dāng)對它進(jìn)行插入操作時(shí)，需要通過旋轉(zhuǎn)和染色（紅黑變換）來保證黑平衡。不過，相較于 AVL 樹為了維持平衡的開銷要小一些。關(guān)于紅黑樹的詳細(xì)介紹，可以查看這篇文章：紅黑樹。
相比較于紅黑樹來說，跳表的實(shí)現(xiàn)也更簡單一些。并且，按照區(qū)間來查找數(shù)據(jù)這個(gè)操作，紅黑樹的效率沒有跳表高。
對應(yīng)紅黑樹添加的核心代碼如下，讀者可自行參閱理解：
private Node < K, V > add(Node < K, V > node, K key, V val) {
if (node == null) {
size++;
return new Node(key, val);
}
if (key.compareTo(node.key) < 0) {
node.left = add(node.left, key, val);
} else if (key.compareTo(node.key) > 0) {
node.right = add(node.right, key, val);
} else {
node.val = val;
}
//左節(jié)點(diǎn)不為紅，右節(jié)點(diǎn)為紅，左旋
if (isRed(node.right) && !isRed(node.left)) {
node = leftRotate(node);
}
//左鏈右旋
if (isRed(node.left) && isRed(node.left.left)) {
node = rightRotate(node);
}
//顏色翻轉(zhuǎn)
if (isRed(node.left) && isRed(node.right)) {
flipColors(node);
}
return node;
}B+樹 vs 跳表
想必使用 MySQL 的讀者都知道 B+樹這個(gè)數(shù)據(jù)結(jié)構(gòu)，B+樹是一種常用的數(shù)據(jù)結(jié)構(gòu)，具有以下特點(diǎn)：
- 多叉樹結(jié)構(gòu)：它是一棵多叉樹，每個(gè)節(jié)點(diǎn)可以包含多個(gè)子節(jié)點(diǎn)，減小了樹的高度，查詢效率高。
- 存儲效率高:其中非葉子節(jié)點(diǎn)存儲多個(gè) key，葉子節(jié)點(diǎn)存儲 value，使得每個(gè)節(jié)點(diǎn)更夠存儲更多的鍵，根據(jù)索引進(jìn)行范圍查詢時(shí)查詢效率更高。-
- 平衡性：它是絕對的平衡，即樹的各個(gè)分支高度相差不大，確保查詢和插入時(shí)間復(fù)雜度為O(log n)。
- 順序訪問：葉子節(jié)點(diǎn)間通過鏈表指針相連，范圍查詢表現(xiàn)出色。
- 數(shù)據(jù)均勻分布：B+樹插入時(shí)可能會導(dǎo)致數(shù)據(jù)重新分布，使得數(shù)據(jù)在整棵樹分布更加均勻，保證范圍查詢和刪除效率。
所以，B+樹更適合作為數(shù)據(jù)庫和文件系統(tǒng)中常用的索引結(jié)構(gòu)之一，它的核心思想是通過可能少的 IO 定位到盡可能多的索引來獲得查詢數(shù)據(jù)。對于 Redis 這種內(nèi)存數(shù)據(jù)庫來說，它對這些并不感冒，因?yàn)?Redis 作為內(nèi)存數(shù)據(jù)庫它不可能存儲大量的數(shù)據(jù)，所以對于索引不需要通過 B+樹這種方式進(jìn)行維護(hù)，只需按照概率進(jìn)行隨機(jī)維護(hù)即可，節(jié)約內(nèi)存。而且使用跳表實(shí)現(xiàn) zset 時(shí)相較前者來說更簡單一些，在進(jìn)行插入時(shí)只需通過索引將數(shù)據(jù)插入到鏈表中合適的位置再隨機(jī)維護(hù)一定高度的索引即可，也不需要像 B+樹那樣插入時(shí)發(fā)現(xiàn)失衡時(shí)還需要對節(jié)點(diǎn)分裂與合并。
Redis 作者給出的理由
當(dāng)然我們也可以通過 Redis 的作者自己給出的理由:
There are a few reasons: 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.
翻譯過來的意思就是:
有幾個(gè)原因：
1、它們不是很占用內(nèi)存。這主要取決于你。改變節(jié)點(diǎn)擁有給定層數(shù)的概率的參數(shù)，會使它們比 B 樹更節(jié)省內(nèi)存。
2、有序集合經(jīng)常是許多 ZRANGE 或 ZREVRANGE 操作的目標(biāo)，也就是說，以鏈表的方式遍歷跳表。通過這種操作，跳表的緩存局部性至少和其他類型的平衡樹一樣好。
3、它們更容易實(shí)現(xiàn)、調(diào)試等等。例如，由于跳表的簡單性，我收到了一個(gè)補(bǔ)?。ㄒ呀?jīng)在 Redis 主分支中），用增強(qiáng)的跳表實(shí)現(xiàn)了 O(log(N))的 ZRANK。它只需要對代碼做很少的修改。
小結(jié)
本文通過大量篇幅介紹跳表的工作原理和實(shí)現(xiàn)，幫助讀者更進(jìn)一步的熟悉跳表這一數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣，最后再結(jié)合各個(gè)數(shù)據(jù)結(jié)構(gòu)操作的特點(diǎn)進(jìn)行比對，從而幫助讀者更好的理解這道面試題，建議讀者實(shí)現(xiàn)理解跳表時(shí)，盡可能配合執(zhí)筆模擬來了解跳表的增刪改查詳細(xì)過程。
參考資料
- 為啥 redis 使用跳表(skiplist)而不是使用 red-black？:https://www.zhihu.com/question/20202931/answer/16086538
- Skip List--跳表（全網(wǎng)最詳細(xì)的跳表文章沒有之一）:https://www.jianshu.com/p/9d8296562806
- Redis 對象與底層數(shù)據(jù)結(jié)構(gòu)詳解:https://blog.csdn.net/shark_chili3007/article/details/104171986
- Redis 有序集合(sorted set):https://www.runoob.com/redis/redis-sorted-sets.html
- 紅黑樹和跳表比較:https://zhuanlan.zhihu.com/p/576984787
- 為什么 redis 的 zset 用跳躍表而不用 b+ tree？:https://blog.csdn.net/f80407515/article/details/129136998
到此這篇關(guān)于Redis 為什么用跳表實(shí)現(xiàn)有序集合的文章就介紹到這了,更多相關(guān)Redis 有序集合內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了redis配置認(rèn)證密碼的方法,需要的朋友可以參考下2016-08-08
Redis實(shí)現(xiàn)查看服務(wù)狀態(tài)、關(guān)閉和啟動方式
本文介紹了如何在Linux系統(tǒng)中查看、關(guān)閉和啟動Redis服務(wù),包括使用命令行工具和配置文件進(jìn)行相關(guān)操作2025-11-11
今天生產(chǎn)機(jī)報(bào)內(nèi)存爆滿異常被叫過去查看問題,通過各種排除最終定位到了Redis的內(nèi)存碎片的問題,這篇博客將詳細(xì)介紹Redis內(nèi)存碎片問題并給出最佳實(shí)踐解決此問題,需要的朋友可以參考下2024-07-07
對于高并發(fā)系統(tǒng)來說,有三個(gè)重要的機(jī)制來保障其高效運(yùn)行,它們分別是：緩存、限流和熔斷,所以本文就來和大家探討一下多級緩存的實(shí)現(xiàn)方法,希望對大家有所幫助2024-02-02
這篇文章主要介紹了在項(xiàng)目中使用redis做緩存的一些思路，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09
詳談redis跟數(shù)據(jù)庫的數(shù)據(jù)同步問題
文章討論了在Redis和數(shù)據(jù)庫數(shù)據(jù)一致性問題上的解決方案,主要比較了先更新Redis緩存再更新數(shù)據(jù)庫和先更新數(shù)據(jù)庫再更新Redis緩存兩種方案,文章指出,刪除Redis緩存后再更新數(shù)據(jù)庫的方案更優(yōu),因?yàn)樗梢员苊鈹?shù)據(jù)不一致的問題,但可能產(chǎn)生高并發(fā)問題2025-01-01
緩存穿透是指查詢一個(gè)根本不存在的數(shù)據(jù),由于緩存不命中,請求會穿透緩存層直接訪問數(shù)據(jù)庫,本文整理了6個(gè)Redis預(yù)防緩存穿透的方法,希望對大家有一定的幫助2025-04-04
Redis腦裂導(dǎo)致數(shù)據(jù)丟失的解決
Redis中Zset類型常用命令的實(shí)現(xiàn)