### Q.Redis 使用 Skip List 作為資料庫資料結構
### Skip List 結構簡介
Redis 作為 in-memory 的資料庫，其主要可以使用的資料結構除了鍵值對 (Hash) 外還有 Sorted set 、 String 、 List 等資料儲存型態，而 Skip List 根據目前[文檔](https://redis.io/glossary/redis-sorted-sets/)的說明最主要是應用在 Sorted set 這個資料型態中，其他的資料儲存型態則會根據儲存的資料大小與情境搭配使用。

Sorted Set 的最大特色，是能夠以順序方式儲存不重複（unique）的元素，並且支援根據 key 進行排序。以傳統的鏈結串列來說，若要檢查某個元素是否存在，必須線性地 tracerse 每個節點，時間複雜度為 $O(n)$；如果改用陣列（Array）來實作，雖然能用二分搜尋法將查找效率提升至 $O(\log n)$，但在插入或刪除元素時，則需要搬動大量資料，時間複雜度同樣為 $O(n)$。為了兼顧查找與插入刪除的效率，Skip List 結合了上述兩種資料結構的優點：

- 它以多層級的鏈結串列設計，使查找、插入與刪除操作的期望時間複雜度皆為 $O(\log n)$。
- 結構實作與操作較樹狀的資料結構簡單，特別適合用於如 Sorted Set 這類既要求排序又常變動元素的場景。


其架構是除了底層完整的排序過後的鏈結串列外，還會有額外再使用隨機的方式在插入時決定要不要將該元素往上插入上層的鏈結串列中，而也因為這個隨機的決定過程，讓上層的鏈結串列會比下層的鏈結更加稀疏，因此當想查找特元素我們便可以先從上層開始查找，當在該層鏈結串列找到小於目標的最大值時，便往下層繼續 traverse 直到在最下層找到該元素為止，這樣的查詢設計可以跳過中間許多不必要的元素減少比較次數。舉例來說以上述結構想要 INSERT 一個元素 67 到 Skip list 中，首先便是要尋找要他該插入的位置，搜尋的過程可以以下表表示，先從上層找到小於67的最大節點並往下繼續搜索，直到在最底層的鏈結串列中找到要 INSERT 的位置。
當最底層的鏈結串列將該元素 INSERT 後，將有 $P$ 的機率可以將該節點增長一層與上層的鏈結串列作鍊接。
而每一個節點在各層的鏈結串列中插入後都會重複一次這個隨機的過程，因此某一節點可增長到 i 層的機率可寫為 $P^{i-1}$，原論文以 $P=1/2$ 來進行分析。

### Analysis of expected search cost

分析搜尋的成本時會使用回溯的方法來進行路徑總長度的分析
#### 1. 參數定義
- **$n$**：資料筆數
- **$p$**：節點「再增長一層」的機率（實務常取 $(p=\tfrac12)$）
- **$L(n)$**：最高層（定義為**節點期望值 < 1** 的第一層）

##### 每層節點的期望值
第 \(k\) 層的節點期望數
$$
\mathbb{E}[N_k] \;=\; n\,p^{k}
$$

因此最高層的估計可寫為：
$$n\,p^{L(n)} \approx 1
\;\Longrightarrow\;
L(n)\approx \log_{1/p} n.$$

---

#### 2. 回溯模型

反向沿搜尋路徑「爬回」頂端時，任一 forward 指標只會落入三種情形：

| 情形 | 描述 | 機率 | 下一步 |
|------|------|------|--------|
| a | 起始狀態，距頂端尚需爬 \(k\) 層 | — | — |
| b | 當前節點剛好位於第 \(i\) 層頂端：`level(x)=i` | 1-p | **向左** 1 步，仍需爬 \(k\) 層 |
| c | `level(x) > i`：此節點還有更高層 | p | **向上** 1 層，剩餘 \(k-1\) 層 |

令
$$
C(k)=\text{「距頂端尚需上爬 \(k\) 層」時的期望邊數}
$$

遞迴式
$$
\begin{aligned}
C(0) &= 0,\\
C(k) &= (1-p)\bigl[1+C(k)\bigr] + p\bigl[1+C(k-1)\bigr],\quad k\ge 1.
\end{aligned}
$$

整理得

$$
\begin{aligned}
p\,C(k) &= 1 + p\,C(k-1) \\[6pt]
\Longrightarrow\quad
C(k) &= \frac{1}{p} + C(k-1) \\[6pt]
\Longrightarrow\quad
C(k) &= \frac{k}{p}.
\end{aligned}
$$

---

#### 3. 單層「水平＋垂直」期望成本
取 \(k=1\)：
$$
C(1)=\frac{1}{p}
$$
= 「向左 $(\tfrac1p-1)$ 步 + 向上 1 步」的期望總長。

---

#### 4. 爬到頂端的總成本
須自底層爬升 $L(n)$ 層：
$$
\mathbb{E}[\text{cost}]
\;=\;C\!\bigl(L(n)\bigr)
\;=\;\frac{L(n)}{p}.
$$

---

#### 5. 代入原始假設的等式
已知
$$
L(n)\approx\log_{1/p} n,
$$
故可以寫為
$$
\boxed{\;\mathbb{E}[\text{Cost}] = O(\log n)\;}
$$

當常用的 $(p=\tfrac12)$ 時，常數即為 $(2\log_2 n)$。Skip List 因此在期望意義下的時間複雜度為 $O(logn)$。

### skip list 在現代處理器架構下的性能與限制分析
> 參考 [What Cannot be Skipped About the Skiplist: A Survey of Skiplists and Their Applications in Big Data Systems](https://arxiv.org/html/2403.04582v2#S1)

#### 記憶體存取模式與快取效能
典型的 Skip list 由多層鏈結串列組成，節點透過指標連結。這種結構 spatial locality 較差，因為 traverse 時需要經由指標在記憶體中 Skip 到不相鄰的位置。每當追蹤下一個節點的指標時，往往導致一次 cache miss ，因此相較於在連續記憶體區塊中順序掃描資料的結構， Skip list 可能產生較多的 random memory access。尤其當每個節點只包含一個 index 時，skip list 在每前進一步都需讀取新的記憶體位置，對現代處理器的快取並不友善。不過近期有研究提出改良方案，例如 Cache-sensitive Skip List 使用陣列來儲存同一層的節點而透過算術計算直接定位子節點位置，以消除指標並降低 cache miss。針對快取 spatial locality 不佳的問題，也可以利用 CPU 的預取指令沿著 skip list 的層數提前預取未來將存取的節點資料（如 Intel 平台的 `mm_prefetch` ）。
在 B+ 樹中，一個節點（例如一個 page 的資料）包含多個 key 和指標，搜尋時每層節點可以存取大量 key 範圍。由於資料通常以 page 或陣列形式連續存放於節點內， traverse 節點時可連續讀取多個元素，所以 spatial locality 佳。因此一次快取取用即可讀入多筆鍵值資料，使 B+ 樹在快取階層中表現出色。即使資料完全在主記憶體中，仍讓 B+ 樹類索引在實務上明顯快於像 Skip list 這類未優化快取 spatial locality 的結構。但 B+ 樹在進行 update 時，有機會觸發大規模的操作導致樹狀結構改變進而導致 page splits (節點填滿時必須去分裂成多個節點)，這些操作可能導致 pages 中出現 fragmentation 進而會降低有效的記憶體利用率（memory utilization）。

#### 為什麼 Redis 使用 Skip list
根據 Redis 作者 antirez 的說法：

> *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.*

Skip List 結構相對簡單，因此在 latency 方面的優勢來自其操作的穩定性──不必像 B⁺ Tree 那樣可能進行耗時的 page split 或 rebalancing；論文實驗亦顯示 tail latency 較小，極端情況下的操作較少見。然而，由於指標 skip 對 cache 存取不友善，單次操作延遲通常仍略高於 B⁺ Tree。這是因為 [pointer chasing](https://en.wikichip.org/wiki/pointer_chasing) 在系統執行期間會導致大量的 TLB miss 與 cache miss，原因在於處理器需不斷處理連續的「不規則記憶體存取」指令，使得 cache spatial locality 效果大幅下降，引發 cache 污染（cache pollution），進而拉高整體存取延遲。

為襯托 Skip List 「不需重平衡」的特性，下列論文原文段落說明了傳統樹形結構面臨的退化與調整問題：

> Binary trees perform well when insertions are in random order. However, ordered insertions can lead to degenerate structures with poor performance. Since randomizing input is often impractical, balanced tree algorithms dynamically rearrange the structure to maintain good performance.

上述說明點出：若輸入序列具特殊順序，普通 BST 易退化成鏈結串列，需依賴 AVL、紅黑或 B / B⁺ Tree 等「平衡」機制動態調整，以維持 $O(log n)$ 效能。相對地，Skip List 透過隨機化高度在插入時就避免退化來源，毋須後續全樹旋轉或節點分裂，因而在高併行、追求低 tail latency 的記憶體索引場景中，能以更簡潔的程式碼提供穩定且可預期的 $O(log n)$ 效能。。若考慮 Concurrency Scalability ， Skip list 因為每筆更新只牽涉少量節點，使 critical section 的程式碼較短且彼此獨立，易於以 CAS（Compare-And-Swap）實現 fine-grained locking 與 lock-free 的設計，相對地，B+ Tree 插入或刪除往往需鎖定目標節點與父節點，且若分裂或合併向上連鎖更動，將導致鎖範圍擴大，將形成更嚴重的資源競爭。

參考資料
[Skip Lists: A Probabilistic Alternative to
Balanced Trees](https://epaperpress.com/sortsearch/download/skiplist.pdf)