redis为什么要用跳表不用红黑树

在数据结构的世界里，红黑树和跳表都是高效处理有序数据的能手。然而，Redis在其内部实现有序集合（Sorted Set）时，选择了跳表作为其底层数据结构。这一选择背后隐藏着怎样的秘密？让我们一起揭开跳表的神秘面纱，并探讨它与红黑树的不同之处。

跳表与红黑树的比较

定义与目的

跳表（Skip List）是一种概率性的数据结构，它通过在有序的链表上增加多级索引来提高查找、插入和删除操作的效率【1】。跳表的核心思想是在链表的每一层上建立一个指向下一个节点的指针，通过这种方式，可以在对数时间内定位到任何元素，从而实现高效的数据操作。

红黑树（Red-Black Tree）则是一种自平衡的二叉查找树，它通过维护树的平衡性质来确保所有的操作都能在对数时间内完成。红黑树的每个节点除了存储键和值之外，还包含一个表示节点颜色的属性，用于维护树的平衡【1】。

核心区别

空间复杂度

跳表的空间复杂度通常低于红黑树。在跳表中，不是所有的节点都会出现在每一层的索引中，而红黑树的每个节点都需要存储两个指针（左子树和右子树），这使得跳表在空间上更加高效【1】。

时间复杂度

跳表和红黑树在时间复杂度上相当，都能做到O(log N)的查找、插入和删除。但由于跳表的结构更简单，其插入和删除操作通常更快【1】。

实现复杂性

红黑树的实现比跳表复杂，因为它需要处理节点颜色的变化和树的旋转操作来保持平衡。跳表则不需要这些复杂的操作，因此在实现和维护上更加简单【1】。

核心类与方法

跳表的核心类

在Redis中，跳表的实现主要依赖于zskiplist结构。这个结构包含了跳表的节点定义、跳表的最大层数、以及当前跳表的高度等信息。

核心方法

• zslInsert: 用于向跳表中插入新的元素。
• zslDelete: 用于从跳表中删除指定的元素。
• zslFind: 用于在跳表中查找给定的元素。

使用场景

跳表在Redis中的使用场景主要集中在有序集合的操作中。例如，当你需要根据分数对元素进行排序，或者需要快速地查找、插入和删除有序数据时，跳表就显得非常有用。

代码案例

案例1：跳表的插入操作

public void add(int value) {
    // 随机生成高度
    int level = randomLevel();
    Node newNode = new Node();
    newNode.data = value;
    newNode.maxLevel = level;
    // 创建一个node数组，用于记录小于当前value的最大值
    Node[] maxOfMinArr = new Node[level];
    // 默认情况下指向头节点
    for (int i = 0; i < level; i++) {
        maxOfMinArr[i] = head;
    }
    // 基于上述结果拿到当前节点的后继节点
    Node p = head;
    for (int i = level - 1; i >= 0; i--) {
        while (maxOfMinArr[i].forward[i] != null && maxOfMinArr[i].forward[i].data < value) {
            p = maxOfMinArr[i];
            maxOfMinArr[i] = maxOfMinArr[i].forward[i];
        }
        // 设置当前要插入的Node和Node索引的后继节点地址
        newNode.forward[i] = p.forward[i];
        p.forward[i] = newNode;
    }
    // 如果当前newNode高度大于跳表最高高度则更新levelCount
    if (level > levelCount) {
        levelCount = level;
    }
}

案例2：跳表的删除操作

public void delete(int value) {
    Node[] updateArr = new Node[levelCount];
    Node p = head;
    for (int i = levelCount - 1; i >= 0; i--) {
        while (p.forward[i] != null && p.forward[i].data < value) {
            p = p.forward[i];
        }
        updateArr[i] = p;
    }
    if (p.forward[0] != null && p.forward[0].data == value) {
        for (int i = 0; i < levelCount; i++) {
            if (updateArr[i].forward[i] == p) {
                updateArr[i].forward[i] = p.forward[i];
            }
        }
    }
}

对比表格

结语

通过上述对比和代码案例，我们可以看到，跳表在Redis中的应用是出于其在空间效率、实现简单性以及特定场景下的性能优势。虽然红黑树在某些方面也有其独特的优势，但在Redis的特定需求下，跳表无疑是更合适的选择。