Redis中的set數據結構底層用的是跳表和哈希表實現的(新的版本優化). 跳表是一個隨機化的數據結構，實質就是一種可以進行二分查找的有序鏈表。 跳表在原有的有序鏈表上面增加了多級索引，通過索引來實現快速查找。 跳表不僅能提高搜索性能，同時也可以提高插入和刪除操作的性能。 * 跳表是可以實現二分查找的有序鏈表； * 每個元素插入時隨機生成它的level； * 最低層包含所有的元素； * 如果一個元素出現在level(x)，那么它肯定出現在x以下的level中； * 每個索引節點包含兩個指針，一個向下，一個向右； * 跳表查詢、插入、刪除的時間復雜度為O(log n)，與平衡二叉樹接近； 為什么Redis選擇使用跳表而不是紅黑樹來實現有序集合？(O(logN)) 首先，我們來分析下Redis的有序集合支持的操作： * 插入元素 * 刪除元素 * 查找元素 * 有序輸出所有元素 * 查找區間內所有元素 其中，前4項紅黑樹都可以完成，且時間復雜度與跳表一致。但是，最后一項，紅黑樹的效率就沒有跳表高了。 在跳表中，要查找區間的元素，我們只要定位到兩個區間端點在最低層級的位置，然后按順序遍歷元素就可以了，非常高效。 而紅黑樹只能定位到端點后，再從首位置開始每次都要查找后繼節點，相對來說是比較耗時的。 此外，跳表實現起來很容易且易讀，紅黑樹實現起來相對困難，所以Redis選擇使用跳表來實現有序集合。