跳躍表基本概念？

• 跳躍表是（skiplist）是一種有序的數據結構，通過在每個節點中維持多個指向其他節點的指針，從而使查找更加迅速。
• 跳躍表的查找時間復雜度平均O（logN），最壞O（n）。
• 跳躍表可以看作為是一個升級版的鏈表，從原理來推的話也有些像是從二叉樹演變過來的。
• Redis中有序集合鍵的底層實現之一就是跳躍表（有序集合元素數量比較多，有序集合元素的成員是比較長的字符串）

快速了解跳躍表的底層推薦一篇博客：https://www.jianshu.com/p/09c3b0835ba6。

跳躍表的實現

前邊提到過，跳躍表可以稱得上是一個進化版的鏈表，跳躍表中每一層的每一個節點都有一個前進指針，和跨度（就是當前指針指的節點和現在節點的距離），當然還有回退指針等，下邊就來詳細的分析以下它的底層數據結構和設計思路。

跳躍表節點的設計思路

typedef struct zskiplistNode{//后退struct zskiplistNode *backward;//分值double score;//成員對象robj *obj;//層struct zskiplistLevel{//前進指針struct zskiplistNode *forward;//跨度unsigined int span;} level[]; }zskiplistNode;前進指針：比如我們需要遍歷所有的跳躍表節點，那就使用前進指針來一步一步向前遍歷（指向的節點跨度為1就相當于遍歷了）后退指針：可以進行從后往前的遍歷，從上邊的結構體可以看到，每一個節點只有一個backward指針，因此，從后往前的遍歷結過也一定是唯一的。跨度就相當于現實生活中的路程，也可以說成為里程，或者是排位。指向null的所有節點的跨度都為0.obj：是指向一個SDS類型的指針，它就是保存的值在我們使用有序集合的時候，它的有序性就是利用score來決定的，因此score是有序性的保證。層的實現是一個數組，為什么是一個數組有沒有想過？ 我認為它是為了在查找過程中從上往下，從大跨度到小跨度，縮小范圍的時候就層數減一進入下一層搜索。 level可以包含多個元素，每一個元素都包含一個zskiplistLevel的結構體（指向其他節點的指針）：可以理解為level是某一個SDS值存的指向其他SDS值的指針。 每次創建新的跳躍表節點時，程序根據冪等定律（越大的數出現的概率越少）隨機生成一個1到32層的值作為level數組的大小。

跳躍表

跳躍表就是多個跳躍表節點組成，通過一個跳躍表節點來標記和記錄一些跳躍表的信息（zskiplist）。

typedef struct zskiplist{//表頭和表尾struct skiplistNode *header,*tial;//表中節點數量unsigined long length;//表中最大的層數 int level;}zskiplist;

理解了前面的，這個就只是一個頭節點記錄一些東西罷了。
跳躍表雖然實現不難，但是對于有序查找效率還是極高的！

總結

以上是生活随笔為你收集整理的Redis的设计与实现之跳表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。