最近看Redis 底層實(shí)現(xiàn)時(shí)砌梆， 看到了關(guān)于有序集合中使用基于跳躍表的實(shí)現(xiàn)萍桌， 突然想記錄一下.
跳躍表
跳躍表是一種有序的隨機(jī)數(shù)據(jù)結(jié)構(gòu)。
它通過在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其他節(jié)點(diǎn)的指針耕腾，從而快速達(dá)到訪問節(jié)點(diǎn)的目的孔轴。
什么是跳躍表 ？
對于一個(gè)單鏈表來說唇礁， 即便鏈表中存儲(chǔ)的數(shù)據(jù)是有序的勾栗， 我們想要隨機(jī)查找一個(gè)數(shù)據(jù)，那么也只能從頭到尾遍歷鏈表節(jié)點(diǎn)盏筐， 這樣查找的效率就會(huì)很低围俘，是件復(fù)雜度為 O(n)
如果我們想要提高其查找效率， 可以考慮在鏈表上建索引的方式琢融。每2個(gè)節(jié)點(diǎn)提取一個(gè)節(jié)點(diǎn)到上一級界牡，我們把抽出來的那一級叫作索引。
這個(gè)時(shí)候漾抬，假設(shè) 我們要查找節(jié)點(diǎn)8 宿亡，我們可以先在索引層遍歷， 當(dāng)遍歷到索引層中7節(jié)點(diǎn)時(shí)纳令，發(fā)現(xiàn)下一個(gè)節(jié)點(diǎn)是9挽荠， 那么要查詢的節(jié)點(diǎn)8 一定在 7和9節(jié)點(diǎn)之間， 我們下降到 原始鏈表層平绩，繼續(xù)遍歷就找到了8這個(gè)節(jié)點(diǎn)圈匆， 原來我們在單鏈表中要找到8這個(gè)節(jié)點(diǎn)要遍歷8個(gè)節(jié)點(diǎn)，而現(xiàn)在有了一層索引后只需要遍歷5個(gè)節(jié)點(diǎn)即可捏雌。
從上面例子里可以看出跃赚， 加了一層索引以后， 查找一個(gè)節(jié)點(diǎn)需要遍歷的節(jié)點(diǎn)數(shù)少了腹忽， 也就是說查找效率提升了来累，同理可以再加一層索引砚作。
從圖中我們可以看出，查找效率又有提升嘹锁。在例子中我們的數(shù)據(jù)很少葫录，當(dāng)有大量的數(shù)據(jù)時(shí)，我們可以增加多級索引领猾，其查找效率可以得到明顯提升米同。
像這種鏈表加多級索引的結(jié)構(gòu)，就是跳躍表!
Redis跳躍表
Redis使用跳躍表作為有序集合鍵的底層實(shí)現(xiàn)之一,如果一個(gè)有序集合包含的元素?cái)?shù)量比較多,又或者有序集合中元素的成員是比較長的字符串時(shí), Redis就會(huì)使用跳躍表來作為有序集合健的底層實(shí)現(xiàn)摔竿。
這里我們需要思考一個(gè)問題——為什么元素?cái)?shù)量比較多或者成員是比較長的字符串的時(shí)候Redis要使用跳躍表來實(shí)現(xiàn)面粮？
從上面我們可以知道，跳躍表在鏈表的基礎(chǔ)上增加了多級索引以提升查找的效率继低，但其是一個(gè)空間換時(shí)間的方案熬苍，必然會(huì)帶來一個(gè)問題——索引是占內(nèi)存的。原始鏈表中存儲(chǔ)的有可能是很大的對象袁翁，而索引結(jié)點(diǎn)只需要存儲(chǔ)關(guān)鍵值值和幾個(gè)指針柴底，并不需要存儲(chǔ)對象，因此當(dāng)節(jié)點(diǎn)本身比較大或者元素?cái)?shù)量比較多的時(shí)候粱胜，其優(yōu)勢必然會(huì)被放大柄驻，而缺點(diǎn)則可以忽略
Redis中跳躍表的實(shí)現(xiàn)
Redis的跳躍表由zskiplistNode和skiplist兩個(gè)結(jié)構(gòu)定義,其中 zskiplistNode結(jié)構(gòu)用于表示跳躍表節(jié)點(diǎn),而 zskiplist結(jié)構(gòu)則用于保存跳躍表節(jié)點(diǎn)的相關(guān)信息,比如節(jié)點(diǎn)的數(shù)量,以及指向表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)的指針等
header:指向跳躍表的表頭節(jié)點(diǎn)，通過這個(gè)指針程序定位表頭節(jié)點(diǎn)的時(shí)間復(fù)雜度就為O(1)
tail:指向跳躍表的表尾節(jié)點(diǎn),通過這個(gè)指針程序定位表尾節(jié)點(diǎn)的時(shí)間復(fù)雜度就為O(1)
level:記錄目前跳躍表內(nèi),層數(shù)最大的那個(gè)節(jié)點(diǎn)的層數(shù)(表頭節(jié)點(diǎn)的層數(shù)不計(jì)算在內(nèi))焙压，通過這個(gè)屬性可以再O(1)的時(shí)間復(fù)雜度內(nèi)獲取層高最好的節(jié)點(diǎn)的層數(shù)鸿脓。
length:記錄跳躍表的長度,也即是,跳躍表目前包含節(jié)點(diǎn)的數(shù)量(表頭節(jié)點(diǎn)不計(jì)算在內(nèi))，通過這個(gè)屬性涯曲，程序可以再O(1)的時(shí)間復(fù)雜度內(nèi)返回跳躍表的長度野哭。
結(jié)構(gòu)右方的是四個(gè) zskiplistNode結(jié)構(gòu),該結(jié)構(gòu)包含以下屬性:
層(level):
節(jié)點(diǎn)中用1、2幻件、L3等字樣標(biāo)記節(jié)點(diǎn)的各個(gè)層,L1代表第一層,L代表第二層,以此類推虐拓。
每個(gè)層都帶有兩個(gè)屬性:前進(jìn)指針和跨度。前進(jìn)指針用于訪問位于表尾方向的其他節(jié)點(diǎn),而跨度則記錄了前進(jìn)指針?biāo)赶蚬?jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的距離(跨度越大傲武、距離越遠(yuǎn))。在上圖中,連線上帶有數(shù)字的箭頭就代表前進(jìn)指針,而那個(gè)數(shù)字就是跨度城榛。當(dāng)程序從表頭向表尾進(jìn)行遍歷時(shí),訪問會(huì)沿著層的前進(jìn)指針進(jìn)行揪利。
每次創(chuàng)建一個(gè)新跳躍表節(jié)點(diǎn)的時(shí)候,程序都根據(jù)冪次定律(powerlaw,越大的數(shù)出現(xiàn)的概率越小)隨機(jī)生成一個(gè)介于1和32之間的值作為level數(shù)組的大小,這個(gè)大小就是層的“高度”。后退(backward)指針：
節(jié)點(diǎn)中用BW字樣標(biāo)記節(jié)點(diǎn)的后退指針,它指向位于當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)狠持。后退指針在程序從表尾向表頭遍歷時(shí)使用疟位。與前進(jìn)指針?biāo)煌氖敲總€(gè)節(jié)點(diǎn)只有一個(gè)后退指針，因此每次只能后退一個(gè)節(jié)點(diǎn)喘垂。分值(score):
各個(gè)節(jié)點(diǎn)中的1.0甜刻、2.0和3.0是節(jié)點(diǎn)所保存的分值绍撞。在跳躍表中,節(jié)點(diǎn)按各自所保存的分值從小到大排列。成員對象(oj):
各個(gè)節(jié)點(diǎn)中的o1得院、o2和o3是節(jié)點(diǎn)所保存的成員對象傻铣。在同一個(gè)跳躍表中,各個(gè)節(jié)點(diǎn)保存的成員對象必須是唯一的,但是多個(gè)節(jié)點(diǎn)保存的分值卻可以是相同的:分值相同的節(jié)點(diǎn)將按照成員對象在字典序中的大小來進(jìn)行排序,成員對象較小的節(jié)點(diǎn)會(huì)排在前面(靠近表頭的方向),而成員對象較大的節(jié)點(diǎn)則會(huì)排在后面(靠近表尾的方向)
在比較的時(shí)候 如果分值相同則會(huì)比較保存的對象。
簡單跳躍表 JAVA 實(shí)現(xiàn)
public class SkipNode<T> {
// 數(shù)據(jù)區(qū)
public Integer score;
public T value;
// 當(dāng)前節(jié)點(diǎn)的 上下左右層級節(jié)點(diǎn)
public SkipNode up;
public SkipNode down;
public SkipNode left;
public SkipNode right;
public SkipNode(Integer score, T value) {
this.score = score;
this.value = value;
}
}
public class SkipList {
// 節(jié)點(diǎn)數(shù)量
public int num;
// 最高層數(shù)
public int max_hight;
public SkipNode head;
public SkipNode tail;
// 概率隨機(jī)
private Random random;
public SkipList() {
this.max_hight = 6; // 設(shè)置最高層數(shù)為6層
this.num = 0; // 初始化時(shí)沒有節(jié)點(diǎn) 這里設(shè)置 0
this.head = new SkipNode(Integer.MIN_VALUE, null);
this.tail = new SkipNode(Integer.MAX_VALUE, null);
this.random = new Random();
this.head.right = tail; // 將鏈表 頭節(jié)點(diǎn)與尾節(jié)點(diǎn)關(guān)聯(lián)
this.tail.left = head;
}
/**
* 基本操作 增加祥绞， 刪除非洲， 查找
* 但是 這些操作都離不開 查詢， 首先要定位到數(shù)據(jù) 然后再進(jìn)行 其他操作
*/
// 查找 , 根據(jù)指定的分?jǐn)?shù)值查找數(shù)據(jù)
private SkipNode find(Integer score) {
SkipNode start = this.head;
while (true) {
// 如果當(dāng)前 節(jié)點(diǎn)的右節(jié)點(diǎn) score 比要查詢的小則 往右移動(dòng)蜕径， 直到遇見比它大的
// 這里進(jìn)來會(huì)一直往右去找
while (start.right.score <= score) {
start = start.right;
}
// 如果已經(jīng)定位到 當(dāng)前這一層 右節(jié)點(diǎn)比要查詢的大了 两踏， 那么將向下定位 ，這里判斷下一層是否為null 不為null 則繼續(xù)定位
if (start.down != null) {
start = start.down;
} else {
break;
}
}
return start; // 注意 這里 start.score 分值是小雨等于 傳入的 score 值
// 注意 這里 是小于等于 score值 兜喻，右2種情況
// 1 如果查找的分值 存在梦染，則返回該對象的底層節(jié)點(diǎn)；
// 2 如果查找的分值 不存在 朴皆，則返回 最接近該對象的底層節(jié)點(diǎn)
}
// get操作 這里就可以獲取 傳入分?jǐn)?shù)對應(yīng)的節(jié)點(diǎn)帕识， 如果完全匹配 那么返回該節(jié)點(diǎn)對應(yīng)的value ， 不匹配 則 return null;
public Object get(Integer score) {
if (num < 1) {
return null;
}
SkipNode mark = find(score);
if (mark.score.equals(score)) {
return mark.value;
} else {
return null;
}
}
public void put(Integer score, Object value) {
// 尋找對應(yīng)的 分值车荔，如果不存在 則返回最近位置的分值 渡冻，等于已經(jīng)找到合適的插入位置
SkipNode mark = find(score);
// 如果找的節(jié)點(diǎn)分值 與要穿入的 相等 那么表示已存在，則進(jìn)行更新
if (mark.score.equals(score)) {
mark.value = value;
return;
}
// 否則 進(jìn)行插入
SkipNode brand_new = new SkipNode<>(score, value);
// 要在 查詢到的 mark 右邊進(jìn)行插入忧便，
// 即 新增的 節(jié)點(diǎn) 左邊為 查詢到的mark族吻。 右邊為 原來mark 的右邊節(jié)點(diǎn)
brand_new.left = mark;
brand_new.right = mark.right;
// 原來 mark 右邊節(jié)點(diǎn)的左節(jié)點(diǎn)更新為 新創(chuàng)建的節(jié)點(diǎn)。 將mark 的右節(jié)點(diǎn) 更新為 新創(chuàng)建的節(jié)點(diǎn)
mark.right.left = brand_new;
mark.right = brand_new;
// 使用變量標(biāo)識(shí) 層級
int i = 0;
while (random.nextDouble() < 0.5) {
if (i > max_hight) {
break;
}
// 這里 mark 在查詢到的時(shí)候 已經(jīng)是最下層 包含所有節(jié)點(diǎn)的 那一層的數(shù)據(jù)了珠增， 然后這里 獲取它的上層超歌，看是否存在更高層
// 如果不存在，那么就切換到左邊一個(gè)節(jié)點(diǎn)繼續(xù)便利蒂教， 一直到獲取到存在最高層的 節(jié)點(diǎn)
while (mark.up == null) {
mark = mark.left;
}
// 找到左側(cè)存在的高層節(jié)點(diǎn)
mark = mark.up;
// 設(shè)置為 新創(chuàng)建的節(jié)點(diǎn)的上層節(jié)點(diǎn)的 左節(jié)點(diǎn)
// 只有最底層的節(jié)點(diǎn) 保存 value 巍举，其他節(jié)點(diǎn)只保存 分值即可
SkipNode up_new = new SkipNode<>(score, null);
up_new.left = mark;
up_new.right = mark.right;
mark.right.left = up_new;
mark.right = up_new;
up_new.down = brand_new;
brand_new.up = up_new;
// 將當(dāng)前 全新引用 指向 新創(chuàng)建的 上層的 引用， 如果 while 繼續(xù)循環(huán)凝垛，那么 mark 也 已經(jīng)是 up懊悯， 上層的了
brand_new = up_new;
++i;
}
++num;
}
public boolean remove(Integer score) {
SkipNode mark = find(score);
// 如果 查詢到的mark 的 score 與傳入的 不同， 表示 根本不存在對應(yīng)的分值對象梦皮， 只是返回了最接近的一個(gè)
if (!mark.score.equals(score)) {
return true;
}
// 查詢到的mark 一定是 最底層的鏈表炭分， 那么就是從最底層開始向上解除關(guān)聯(lián)即 鏈表刪除
SkipNode del;
while (mark != null) {
del = mark.up;
mark.left.right = mark.right;
mark.right.left = mark.left;
// 升一層 如果不為nul 繼續(xù)處理
mark = del;
}
return true;
}
}
