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