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、因為不需要旋轉操作，因此跳表的實作更簡單
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/499120.html
標籤：NoSQL