Redis跳躍表如何添加元素？
今天分享的這道題來自于蔚來的真實面試題。
面試 Java 不可能不問 Redis，問到 Redis 不可能不問 Redis 的常用數據類型，問到 Redis 的常用數據類型，不可能不問跳躍表，當問到跳躍表經常會被問到跳躍表的查詢和添加流程，所以接下來我們一起來看這道題的答案吧。
Redis 有序集合ZSet 是由 ziplist (壓縮列表) 或 skiplist (跳躍表) 組成的。
- 壓縮列表 ziplist 本質上就是一個字節數組，是 Redis 為了節約內存而設計的一種線性數據結構，可以包含多個元素，每個元素可以是一個字節數組或一個整數。
- 跳躍表 skiplist 是一種有序數據結構，它通過在每個節點中維持多個指向其他節點的指針，從而達到快速訪問節點的目的。跳躍表支持平均 O(logN)、最壞 O(N) 復雜度的節點查找，還可以通過順序性操作來批量處理節點。
跳躍表介紹
跳躍表 Skip List，也稱之為跳表，是一種數據結構，用于在有序元素的集合中進行高效的查找操作。它通過添加多層鏈表的方式，提供了一種以空間換時間的方式來加速查找。
跳躍表由一個帶有多層節點的鏈表組成，每一層都是原始鏈表的一個子集。最底層是一個完整的有序鏈表，包含所有元素。每個更高層級都是下層級的子集，通過添加額外的指針來跳過一些元素。這些額外的指針稱為“跳躍指針”，它們允許快速訪問更遠的節點，從而減少了查找所需的比較次數。
跳躍表的平均查找時間復雜度為 O(log n)，其中 n 是元素的數量。這使得它比普通的有序鏈表具有更快的查找性能，并且與平衡二叉搜索樹（如紅黑樹）相比，實現起來更為簡單。
簡單的跳躍表如下圖所示：
跳躍表添加流程
前置知識：節點隨機層數
在開始講跳躍表的添加流程之前，必須先搞懂一個概念：節點的隨機層數。所謂的隨機層數指的是每次添加節點之前，會先生成當前節點的隨機層數，根據生成的隨機層數來決定將當前節點存在幾層鏈表中。
為什么要這樣設計呢？
這樣設計的目的是為了保證 Redis 的執行效率。
為什么要生成隨機層數，而不是制定一個固定的規則，比如上層節點是下層跨越兩個節點的鏈表組成，如下圖所示：
如果制定了規則，那么就需要在添加或刪除時，為了滿足其規則，做額外的處理，比如添加了一個新節點，如下圖所示：
這樣就不滿足制定的上層節點跨越下層兩個節點的規則了，就需要額外的調整上層中的所有節點，這樣程序的效率就降低了，所以使用隨機層數，不強制制定規則，這樣就不需要進行額外的操作，從而也就不會占用服務執行的時間了。
添加流程
Redis 中跳躍表的添加流程如下圖所示：
- 第一個元素添加到最底層的有序鏈表中（最底層存儲了所有元素數據）。
- 第二個元素生成的隨機層數是 2，所以再增加 1 層，并將此元素存儲在第 1 層和最低層。
- 第三個元素生成的隨機層數是 4，所以再增加 2 層，整個跳躍表變成了 4 層，將此元素保存到所有層中。
- 第四個元素生成的隨機層數是 1，所以把它按順序保存到最后一層中即可。
其他新增節點以此類推。
隨機層數源碼分析
隨機層數的源碼在 t_zset.c/zslRandomLevel(void) 中，如下所示：
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}從源碼可知，隨機層數有 50% 的概率被分配到 Level 1，25% 的概率被分配到 Level 2，12.5% 的概率被分配到 Level 3，以此類推。
Redis 跳躍表默認允許最大的層數是 32，此值在 ZSKIPLIST_MAXLEVEL 源碼中被定義。
小結
跳躍表是由多個有序的鏈表組成的，最底層存儲了所有元素的數據，這樣存儲讓它的查詢效率更高，查詢復雜度從 O(n) 變為了 O(log n)。跳躍表的添加流程是根據節點生成的隨機層數，將它插入到最底層節點和上層的 N-1 層節點中，描述添加流程的關鍵就是理解隨機層數以及其背后的原理。
參考 & 鳴謝
https://segmentfault.com/a/1190000022028505。
