在了解了跳表的原理和實現后，一個常見的問題（尤其是在面試中）隨之而來：為什么像 Redis 的有序集合 (Zset) 這樣的高性能組件會選擇使用跳表，而不是大家熟知的平衡樹（如紅黑樹）呢？

對于這個問題，Redis 的作者 Salvatore Sanfilippo (@antirez) 曾給出過解釋，主要可以歸納為以下幾點：

1. 內存效率與靈活性 (Memory Efficiency & Flexibility):

   • 跳表并非特別消耗內存。其內存占用可以通過調整節點提升的概率 p? 來控制。通過選擇合適的 p? 值，可以使得跳表的平均內存占用低于某些平衡樹。

2. 高效的范圍查詢與緩存局部性 (Efficient Range Queries & Cache Locality):

   • Zset 經常需要執行 ZRANGE? (按排名范圍查詢) 或 ZREVRANGE? (按排名反向范圍查詢) 操作，這本質上是在有序結構上進行一段連續元素的遍歷。
   • 跳表的最底層 (Level 0) 是一個有序鏈表。執行范圍查詢時，只需定位到范圍的起始點，然后沿著 Level 0 的鏈表順序遍歷即可。這種順序訪問模式具有良好的緩存局部性 (cache locality)，與平衡樹的中序遍歷相比，至少同樣好，甚至可能更好。

3. 實現的簡單性與易擴展性 (Implementation Simplicity & Extensibility):

   • 跳表的實現、調試相比平衡樹（尤其是紅黑樹）要簡單得多。平衡樹復雜的旋轉和重新平衡邏輯很容易出錯。
   • 跳表的簡單性也帶來了更好的可擴展性。@antirez 提到，得益于跳表的簡潔，他很容易地集成了一個社區貢獻的補丁，通過對跳表進行少量修改，就在 O(log N) 時間內實現了 ZRANK? (獲取成員排名) 的功能。

進一步解讀與補充：

• 內存占用對比:

  • 平衡樹（如紅黑樹）每個節點通常需要存儲 2 個指向子節點的指針，以及可能的父指針和顏色信息。
  • 跳表每個節點包含的指針數目是可變的，取決于它提升的層數。平均來說，每個節點包含的指針數量為 1 / (1 - p)?（其中 p? 是節點提升一級概率）。在 Redis 的實現中，p? 通常取 0.25 (1/4)，這意味著平均每個節點大約有 1 / (1 - 0.25) = 1.33? 個 right? 指針（再加上 down? 指針和可能的 backward? 指針，但核心指向下一節點的指針數平均較少）。這使得跳表在內存使用上具有一定的靈活性和潛在優勢。

• 范圍查詢的易實現性:

  • 如 @antirez 所說，跳表執行范圍查詢非常自然。找到范圍起點后，沿著最底層的鏈表順序遍歷即可，邏輯簡單清晰。
  • 平衡樹執行范圍查詢，需要先找到范圍起點，然后執行中序遍歷來依次訪問后續節點，直到超出范圍終點。雖然中序遍歷本身不復雜，但在某些實現中，高效地進行部分中序遍歷可能需要額外的輔助結構或遞歸，相對跳表的直接鏈表遍歷要稍微復雜一些。此外，跳表 Level 0 的節點在內存中可能是物理上更連續的（如果內存分配器配合），有利于緩存；而樹的中序遍歷則可能在內存地址上跳躍。

• 實現與維護成本:

  • 這一點對于像 Redis 這樣需要高性能、高穩定性且持續迭代的項目至關重要。更簡單的實現意味著更少的 Bug、更快的開發迭代速度和更低的維護成本。平衡樹，特別是紅黑樹，其插入和刪除操作涉及多種情況的判斷、旋轉和重新染色，邏輯復雜，容易出錯。

總結來說，Redis Zset 選擇跳表是基于其在內存占用、范圍查詢性能與實現簡潔性之間取得的良好平衡。 對于 Zset 這種既需要快速單點查找/更新，又需要高效范圍遍歷的場景，跳表提供了一個非常實用且工程上更優的解決方案。