redis为什么用跳表而不是红黑树

Redis是一种常用的内存缓存和数据库系统，因为它的高效性和可扩展性而受到广泛关注。Redis以其优秀的性能和对分布式处理的支持而著称，但是这也导致了对其使用的底层数据结构的追捧。Redis的核心是一个键值存储系统，每个键值对存储在一个哈希表中，而这个哈希表中的每个桶都可以作为一个简单的单向链表来实现。然而，为了支持更复杂的操作，Redis需要一种更高效的数据结构，因此它选择了跳表。

什么是跳表

跳表是一种支持快速查找和插入删除的数据结构。它在平均情况下的时间复杂度为O(log n)，与红黑树的时间复杂度相同。跳表最初于1990年由William Pugh发明用于解决数据库中的索引问题。跳表可以被看作是同时开了多个单链表的组合体，每层单链表称为一层，每个节点有多个指针指向下一层节点，这些指针使得高级别的层能够“跳过”低级别的一些节点，从而降低搜索的时间复杂度。跳表的高效性和易于实现和调整的特性使得它在Redis中得到了很好的应用。

为什么Redis选择跳表

Redis中使用跳表相对于其他数据结构如红黑树和AVL树的优势在于随机性。红黑树和AVL树表现良好的主要是因为树是一种二叉数据结构，然而，随机性往往会打破树的平衡性。如果我们能有一个算法展开一个链表，避免由随机因素带来的变化，那么我们就有一个不依赖于树平衡性的高效算法了。

跳表中每个节点都有一个名为level的属性，表示节点的高度。跳表的高度是根据随机概率来平衡分布的。从下到上的每一层都是一个链表的集合。每个链表都是下一个链表的一部分。通过往上跳，它可以“跳过”很多节点，从而大大减少搜索时间。在跳表中进行查找，插入和删除操作的时间复杂度均为O(log n)。除此之外，跳表的实现和红黑树和AVL树相比较简单，这使得Redis可以更容易地对跳表进行修改或优化。因此，Redis选择使用跳表，作为其底层数据结构。