導讀
前面文章【
一、深入理解redis之需要掌握的知識點
】中，我們對redis需要學習的內容框架進行了一個梳理。【
二、redis中String和List兩種資料型別和應用場景
】、【
二、redis中Hash、Set、SortedSet應用場景
】兩篇文章我們對redis中String、List、Hash、Set、SortedSet五種資料型別做了一下講解，並且對他們各自的應用場景進行了介紹。
本篇文章我們將要深入學習支撐SortedSet排序背後的資料結構，跳躍表；
如果大家在工作、學習、面試中針對redis還有什麼疑問或者其他問題，可以評論區告訴我。為了保證可以連續不間斷的獲取最新的技術分析及講解，建議關注本頭條號【程式猿的花果山】。
解釋
一、
在redis的SortedSet中使用雙向連結串列儲存資料，並按照權重（Score分值）進行排序，但是它用空間換時間的方式實現了跳躍表的概念。
二、
如果此時SET只是一個單純的雙向連結串列，那麼當現在要新插入資料“A1-8”時候，他需要從雙向連結串列的頭部元素U開始，從左向右尋找，直到找到“W1-7”和“X1-10”之間然後插入。
此時他查詢的時間複雜度是O（n），插入的時間複雜度為O（1）。之所以插入的時間複雜度為O（1）因為他只需要改變“W1-7”元素的next指標到“A1-8”，“A1-8”的next指標到“X1-10”。
（注意：要理解這個操作需要先理解連結串列，請自行了解，連結串列的優缺點是：插入、刪除快查詢慢）
三、
在redis的SortedSet中使用了跳躍表邏輯的雙向連結串列（注意去看跳躍雙向連結串列的論文
）。當此時要插入新資料“A1-8”時，他從雙向連結串列的頭部元素“U1-1”開始自上而下開始尋找。
他首先判斷當前“A1-8”的值大於“U1-1”的值，因此應該向右側看，因此開始自上而下的開始找他的跳躍索引；
當他找到“U3”時候，發現“U3”的右邊都指向空；那麼繼續向下尋找找到“U2”，發現“U2”右側指向“W2”，然後跳躍到“W2”節點；
此時用“W2”的根節點“W1-7”的值與“A1-8”進行比較發現還需要自己向右側看；
此時再自上而下遍歷“W1-7”的跳躍索引“W2”，發現“W2”右側節點指向“Y2”，然後跳躍到“Y2”節點；
此時用“Y2”的根節點“Y1-12”的值與“A1-8”進行比較，發現需要向左側看，因此跳躍到“X1-10”節點；
然後再用“X1-10”的值與“A1-8”的值進行比較，發現需要繼續向左看，然後跳躍到“W1-7”節點：然後再進行比較發現“A1-8”的值大於“W1-7”的值，所以把“A1-8”插入到“W1-7”與“X1-10”之間。
四、
當跳躍連結串列要插入的新資料“A1-8”找到要插入的位置並插入到“W1-7”和“X1-10”之間後，他開始用投硬幣的方式構建自己的跳躍索引。
如果此時他投硬幣的結果為0，那麼直接結束構建跳躍索引的過程；
如果此時他投硬幣的結果為1，那麼他建立一個自己的跳躍索引“A2”，並透過遞迴查詢“A1-8”的左側和右側，直到找到有2層跳躍索引的元素“W1-7”和“Y1-12”，並把“A1-8”的跳躍索引“A2”插入到“W1-7”和“Y1-12”的各自的2層跳躍索引“W2”和“Y2”中間，此時“A1-8”的2層跳躍索引“A2”構建完畢；
此時繼續透過投硬幣的方式判斷是否繼續構建3層索引，如果投硬幣的結果為0則直接結束構建跳躍索引，如果投硬幣的結果為1，那麼繼續構建“A1-8”的第三層索引“A3”；
如此迴圈往復，構建第4層，第5層跳躍索引，直到投硬幣結果為0而結束跳躍索引的構建；
五、
注意：當構建每層次跳躍索引時，它只會尋找具備相同層次的跳躍索引的元素。例如：如果“A1-8”要構建他的第三層跳躍索引“A3”，那麼他向左向右遞迴時候，最終“A3”的右側指向空，“A3”的左側指向同樣具備第三層跳躍索引的元素“U1-1”的跳躍索引“U3”。
圖示
如需瞭解更多更詳細內容也可關注本人CSDN部落格：不吃_花椒
