阿竺 ·1. 前言
上一章節介紹了 SDS 數據結構，即 Redis 最基礎的 Key-Value 存儲實現，本章節繼續介紹 Redis 底層的高級數據結構。
Redis 的五種基本結構中還有一個叫做 zset 的數據結構，zset 保證了每個值的唯一性，這方面性質同傳統的 set 集合，也可以對每個值賦予 score，按照 score 進行排序。這種高級性質依賴于底層的跳躍表數據結構實現。
2. SkipList
2.1 SkipList 數據結構
面試官提問： Redis zset 數據結構的底層實現是什么？為什么要使用跳躍表？
題目解析：
在介紹跳躍表（SkipList，簡稱跳表）之前，我們可以以單鏈表數據結構作為對比。
在單鏈表中，我們查詢一個元素的時間復雜度是 O (N)，其中 N 是鏈表的長度，因為需要誒個遍歷節點，單鏈表不支持數組的隨機插入和刪除，也不支持數組的自動排序，顯然不適合作為 zset 的實現方式。
跳躍表的基礎定義可參考維基百科定義
參考定義，我們給出 C 語言的結構體定義：
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
候選人需要描述跳表的數據結構，可以通過畫圖或者其他方式給出定義。
?
從結構體可以看出，節點有不同的定義：
- sds：存儲的字符串對象；
- score：分數，跳表中所有節點按照 score 由大到小排列；
- backward：指向后退節點的指針；
- forward：指向下一個節點的指針；
- level：數組，數組中的每一個元素包括了指向其他節點的指針，level 的長度在 1 到 32（2^5）之間。
其中跳表的主要組成結構有：
- 表頭：表示跳表的入口；
- 表尾：表示跳表的尾部，數值全部都是 NULL；
- 節點：保存具體數值，并且具有層結構；
- 層：就是上述 level 定義中的單個元素，保存前一個節點的指針，以及該層下個節點向前跨越的數值（span）。
跳表的查詢過程本質上是自上而下的二分查找，插入和查詢過程都相對復雜，這里不做贅述。
在闡述基本定義之后，我們需要關注跳躍表的核心特點：
- 本質是隨機化數據結構，可以在對數（logN）時間內完成對數據的查找、插入、刪除操作；
- 跳躍表在 Redis 的唯一應用，就是作為有序集合支撐底層數據結構。
2.2 跳躍表 vs 二叉樹
面試官提問： 二叉查找樹也能實現對數時間的查找插入特性，為什么還要使用跳躍表？
題目解析：
面試官經常會拿跳表和其他數據結構進行對比，依次同時考察候選人數據結構的基礎能力。
雖然二叉查找樹（Binary Search Tree）也滿足插入、查找、刪除時間復雜度為 O (logN)，但是在極端情況下，如果插入的數據滿足完全有序（例如 1，2，3，4 …），則每次插入二手樹都是右節點，這時二叉查找樹會退化為線性鏈表，查詢時間復雜度退化為 O（N）。相對于二叉查找樹，跳躍表的表現更穩定。
2.3 跳躍表 vs 紅黑樹
面試官提問： 紅黑樹也能實現對數時間的查找插入特性，為什么還要使用跳躍表？
題目解析：
紅黑樹（Red Black Tree）是二叉查找樹的一種變形，查找、插入、刪除的時間復雜度也是 O (logN)，為什么 Redis 不使用紅黑樹作為 zset 的數據結構實現？
關于這一點，Redis 的官方解釋已經很全面：
There are a few reasons:
- 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）相對于 B 樹 / 紅黑樹，跳躍表修改節點對內存的變量影響?。?/p>
（2）性能接近紅黑樹，但是跳表編碼實現更簡單，方便調試，簡單來說就是編碼完整的紅黑樹實現麻煩且不直觀。
3. 小結
本章節介紹了跳躍表的基本數據結構定義、插入查找的時間復雜度，以及和其他數據結構的對比。跳表是常見的 Redis 底層數據結構，希望大家能夠深入理解并掌握。
2025 imooc.com All Rights Reserved |