Redis中的set数据结构底层用的是跳表和哈希表实现的(新的版本优化). 跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。 跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。 跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。 * 跳表是可以实现二分查找的有序链表； * 每个元素插入时随机生成它的level； * 最低层包含所有的元素； * 如果一个元素出现在level(x)，那么它肯定出现在x以下的level中； * 每个索引节点包含两个指针，一个向下，一个向右； * 跳表查询、插入、删除的时间复杂度为O(log n)，与平衡二叉树接近； 为什么Redis选择使用跳表而不是红黑树来实现有序集合？(O(logN)) 首先，我们来分析下Redis的有序集合支持的操作： * 插入元素 * 删除元素 * 查找元素 * 有序输出所有元素 * 查找区间内所有元素 其中，前4项红黑树都可以完成，且时间复杂度与跳表一致。但是，最后一项，红黑树的效率就没有跳表高了。 在跳表中，要查找区间的元素，我们只要定位到两个区间端点在最低层级的位置，然后按顺序遍历元素就可以了，非常高效。 而红黑树只能定位到端点后，再从首位置开始每次都要查找后继节点，相对来说是比较耗时的。 此外，跳表实现起来很容易且易读，红黑树实现起来相对困难，所以Redis选择使用跳表来实现有序集合。