Redis是一个开源的内存数据库，它支持多种数据结构，其中有序集合（sorted set）是一种非常常用的数据类型，它可以存储一组带有分数（score）的元素，并按照分数从小到大排序。有序集合在Redis中的应用场景很多，比如排行榜、延时队列、时间轴等。那么，Redis是如何实现有序集合的呢？答案是跳表（skiplist）。
跳表是一种基于链表的数据结构，它通过在链表中增加多级索引，来加快查找、插入和删除的速度。跳表的每一层都是一个有序的链表，最底层是完整的数据链表，每一层都是上一层的子集，越往上层越稀疏。跳表的查找操作是从最高层开始，沿着指针向右移动，直到找到一个大于或等于目标值的节点，然后下降到下一层，重复这个过程，直到到达最底层。跳表的插入和删除操作也是类似的，先找到插入或删除位置，然后更新相应层的指针。跳表的平均时间复杂度为O(log n)，空间复杂度为O(n)。
那么，Redis为什么要用跳表来实现有序集合呢？不是有其他更常见的平衡二叉树（比如红黑树）可以做到同样的效果吗？事实上，跳表相比于平衡二叉树有以下几个优势：
1.跳表的代码实现更简单，更容易维护和调试。平衡二叉树需要维护很多额外的信息（比如颜色、平衡因子等），并且在插入和删除时需要进行复杂的旋转操作，来保持树的平衡性。而跳表只需要维护一个随机生成的索引层数，并且在插入和删除时只需要更新指针即可。
2.跳表对于并发操作更友好，可以支持更高效的锁机制。平衡二叉树在插入和删除时可能会涉及到整棵树的变动，因此需要加全局锁来保证线程安全。而跳表在插入和删除时只会影响局部区域，因此可以采用更细粒度的锁机制（比如读写锁、乐观锁等），来提高并发性能。
3.跳表可以更方便地实现范围查询和排序输出。平衡二叉树虽然也可以按照中序遍历来输出有序序列，但是如果要查询某个范围内的元素，就需要先找到范围的起点和终点，然后再遍历中间的元素。而跳表可以直接通过指针来定位范围的起点和终点，并且沿着底层链表来输出有序序列，更加高效。