zset底層的數據結構為什麼使用調表而不是紅黑樹 前言 Redis中使用到的數據結構以及各個數據對象的底層數據結構在上一篇文章已經寫得非常詳細，這裡不再贅述。 https://www.cnblogs.com/ruigedada/p/16248689.html zset的底層數據結構是壓縮列表和跳錶， ...
zset底層的數據結構為什麼使用調表而不是紅黑樹
前言
Redis中使用到的數據結構以及各個數據對象的底層數據結構在上一篇文章已經寫得非常詳細，這裡不再贅述。
https://www.cnblogs.com/ruigedada/p/16248689.html
zset的底層數據結構是壓縮列表和跳錶，當滿足以下條件時，Redis將使用壓縮列表存儲
-
有序集合保存的元素個數要小於 128 個；
-
有序集合保存的所有元素成員的長度都必須小於 64 位元組。
我們都知道，調表的查找時間複雜度為O(logn)，但是紅黑樹和AVL樹的查找效率也是O(logn)呀，為什麼zset的底層是調表而不是紅黑樹或者AVL樹呢？
一、跳錶、紅黑樹和AVL樹的區別
| 跳錶 | 紅黑樹 | AVL樹 | |
|---|---|---|---|
| 查詢時間複製度 | O(logn) | O(logn) | O(logn) |
| 插入/刪除效率 | 最高 | 低 | 最低 |
| 範圍查詢效率 | 高 | 低 | 低 |
| 實現難易 | 易 | 難 | 難 |
-
1、雖然跳錶，紅黑樹和AVL樹的查找時間複雜度都是O(logn)，但相比於跳錶，紅黑樹和AVL樹的插入/刪除效率更低。為什麼呢？
-
跳錶在插入或者刪除時，我們只需要考慮相鄰兩個結點就可以了，其插入刪除的過程和鏈表的過程實際上是差不多的，只是需要考慮索引的問題。
-
紅黑樹和AVL樹都是自平衡樹，所以在插入和刪除時會涉及到結點的旋轉問題，因此其效率不如跳錶，而AVL樹是一個嚴格的平衡樹，追求的是絕對的平衡，因此其效率比紅黑樹還不如，這也是HashMap不使用AVL樹的原因之一。
-
-
2、對於範圍查找來說，跳錶只需要查找最小的那個值，然後往後遍歷就可以了。
-
3、因為不需要旋轉操作，因此跳錶的實現更簡單
