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