Redis是一个开源的内存数据库，它支持多种数据类型，其中有序集合（sorted set）是一种非常常用的类型。有序集合可以存储一组带有分数（score）的元素，并且可以按照分数对元素进行排序。有序集合可以实现很多功能，比如排行榜、时间轴、延迟队列等。
那么，Redis是如何实现有序集合的呢？它使用了一种叫做跳表（skiplist）的数据结构。跳表是一种基于链表的数据结构，它在链表的基础上增加了多级索引，使得查找、插入和删除操作的时间复杂度都是O(logn)。跳表的结构如下图所示：
跳表中每个节点都包含一个元素和一个分数，以及一个指向下一个节点的指针数组。指针数组的长度是随机生成的，越靠近链表头部的节点越有可能拥有更长的指针数组。这样，当我们要查找一个元素时，我们可以从最高级别的索引开始，如果当前节点的分数小于目标分数，就沿着当前级别的指针前进；如果当前节点的分数大于或等于目标分数，就降低一个级别，继续查找。这样，我们可以跳过很多不必要的节点，提高查找效率。
那么，为什么Redis选择了跳表而不是红黑树呢？红黑树是一种自平衡的二叉搜索树，它也可以实现O(logn)的查找、插入和删除操作。而且，红黑树在内存占用方面比跳表更优秀，因为它不需要额外的指针数组。
Redis之所以选择跳表而不是红黑树，主要有以下几个原因：
1.跳表比红黑树更容易实现。红黑树需要维护很多复杂的性质和旋转操作，而跳表只需要简单地调整指针即可。
2.跳表比红黑树更适合并发环境。在并发场景下，如果多个线程同时对红黑树进行修改，可能会导致树的结构失衡或者出现死锁。而跳表可以通过加锁粒度控制来避免这些问题。例如，Redis可以对每个索引级别加锁，或者对每个节点加锁。
3.跳表比红黑树更支持范围查询。由于跳表是按照分数排序的链表，所以可以很方便地对分数区间进行遍历。而红黑树需要先找到区间的最小值和最大值，然后再中序遍历。
4.跳表比红黑树更易于扩展。如果要增加或减少跳表的索引级别，只需要修改链表头部即可。而红黑树需要重新构建整棵树。