Redis 中的跳躍表（Skiplist）是一種用于有序元素集合的快速查找數據結構。它通過一個多級索引來提高搜索效率，能夠在對數時間復雜度內完成查找、插入和刪除操作。跳躍表特別適用于實現有序集合（sorted set）的功能，比如 Redis 的 ZSET 數據類型。
跳躍表的基本結構
跳躍表主要由以下部分組成：
-
節點（Node）：每個節點包含多個層（level），每個層都有一個指向前方節點的指針（forward pointer）。這些層形成了一個多層鏈表，其中每一層都是一個有序的鏈表。最底層包含了所有的元素，而上面的層則是隨機選擇的一些元素（通常是基于某種概率），使得上層的鏈表更稀疏。
-
層（Level）：每個節點可以有多個層，層數越多，該節點在跳躍表中“跳躍”的能力就越強，即能夠更快地跳過多個節點。
-
跨度（Span）：每個層除了有一個指向前方節點的指針外，還有一個跨度（span）字段，記錄了兩個節點之間的距離（即兩個節點之間有多少個節點）。這個信息在搜索過程中可以用來計算位置，優化搜索過程。
-
頭節點（Header）：跳躍表有一個特殊的頭節點，它不包含任何數據元素，但擁有最大的層數，其作用是作為跳躍表的起點，方便從任何一層開始搜索。
-
高度（Height）：跳躍表的高度是其頭節點的層數。
跳躍表的操作
-
搜索：從最高層開始，沿著指針向前移動，如果當前節點的下一個節點的值大于要搜索的值，則向下移動到下一層，并繼續向前移動。這個過程會重復，直到找到目標值或到達最底層且下一個節點的值大于目標值。
-
插入：首先執行搜索操作，找到應該插入新節點的位置。然后，根據一定的概率決定新節點的層數（通常是隨機生成），并逐層插入新節點。
-
刪除：與插入類似，首先通過搜索找到要刪除的節點，然后逐層刪除該節點。
跳躍表在 Redis 中的應用
Redis 使用跳躍表作為有序集合（sorted set）的底層實現之一（另一個實現是平衡樹）。有序集合是一種不允許重復成員，且每個成員都會關聯一個 double 類型的分數（score），Redis 通過分數來為集合中的成員進行從小到大的排序。跳躍表能夠高效地實現這些操作，如添加、刪除和范圍查詢等。
總的來說，跳躍表是 Redis 中一個非常重要的數據結構，它以其高效的有序集合操作能力，為 Redis 提供了強大的功能支持。
