理解Redis的Skiplist-ZHD的小窝

Redis中的跳跃表（Skip List）是一种有序的数据结构，它通过维护多个指向其他节点的指针来实现快速访问节点。这种数据结构由美国计算机科学家William Pugh在1989年提出，并在其论文《Skip lists: a probabilistic alternative to balanced trees》中详细阐述。跳跃表在Redis中主要被用作有序集合（Sorted Set）的底层实现之一，特别是在有序集合包含的元素数量较多或元素成员是较长的字符串时。下面将详细解释Redis的跳跃表：

一、跳跃表的基本结构

跳跃表由多个节点组成，每个节点都包含多个层（Level）。每一层都带有两个主要属性：前进指针（Forward Pointer）和跨度（Span）。

前进指针：用于访问位于表尾方向的其他节点。每一层都有一个前进指针，指向同一层中下一个节点。
跨度：记录了前进指针所指向节点和当前节点的距离（即跳过了多少个节点）。这个信息在计算节点排位时非常有用。

此外，每个节点还包含一个后退指针（Backward Pointer），用于从表尾向表头方向访问节点。

二、节点的排序

跳跃表中所有节点都按分值（Score）从小到大排序。分值是一个double类型的浮点数，用于表示节点的排序位置。如果两个节点的分值相同，则按照成员对象（Member）在字典中的大小进行排序。

三、跳跃表的特性

搜索速度快：跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找。在大部分情况下，跳跃表的效率可以和平衡树相媲美。
实现简单：相比于平衡树等数据结构，跳跃表的实现更为简单，插入和删除操作只需要修改相邻节点的指针，而不需要进行复杂的子树调整。
支持范围查询：跳跃表支持按照分值范围进行查询，方便获取指定范围内的元素。

四、跳跃表的随机层数

跳跃表为了解决插入和删除节点时可能造成的后续节点重新调整的问题，引入了随机层数的做法。每个新插入的节点会被赋予一个随机的层数（层数在1到最大层数之间随机选择），这个层数决定了节点在跳跃表中的高度。这种随机层数的做法使得跳跃表在插入和删除节点时不需要对多个节点进行调整，从而降低了操作的复杂度。

五、Redis中跳跃表的应用

在Redis中，跳跃表主要被用作有序集合（Sorted Set）的底层实现之一。有序集合是一种不允许重复元素，且每个元素都会关联一个double类型的分数（score）来表示元素之间的顺序的数据结构。通过跳跃表，Redis能够高效地实现有序集合的查找、插入、删除和范围查询等操作。

六、实现一个简单的跳跃表

import java.util.Random;  
  
// 定义跳跃表的节点类
class SkipListNode<T extends Comparable<T>> {  
    T value;  
    SkipListNode<T>[] forward;  
  
    public SkipListNode(T value, int maxLevel) {  
        this.value = value;  
        this.forward = new SkipListNode[maxLevel + 1]; // 数组大小为maxLevel+1，因为层数是从0开始的  
    }  
  
    // 随机生成节点的层数  
    static int randomLevel(int maxLevel) {  
        Random random = new Random();  
        int lvl = 1;  
        while (random.nextDouble() < 0.5 && lvl < maxLevel) {  
            lvl++;  
        }  
        return lvl;  
    }  
}

// 跳跃表
public class SkipList<T extends Comparable<T>> {  
    private final int MAX_LEVEL;  
    private int level;  
    private SkipListNode<T> header;  
  
    public SkipList(int maxLevel) {  
        this.MAX_LEVEL = maxLevel;  
        this.level = 0;  
        // 初始化头节点，所有层的前向指针都指向null  
        this.header = new SkipListNode<>(null, MAX_LEVEL);  
    }  
  
    // 插入方法（简化版，不包含删除和查找）  
    public void insert(T value) {  
        SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL + 1];  
        SkipListNode<T> current = header;  
  
        // 查找每个层应该插入的位置  
        for (int i = level; i >= 0; i--) {  
            while (current.forward[i] != null && current.forward[i].value.compareTo(value) < 0) {  
                current = current.forward[i];  
            }  
            update[i] = current;  
  
            // 如果当前层是最高层，则增加一个新的层  
            if (i == 0 && current.forward[0] != null && current.forward[0].value.compareTo(value) == 0) {  
                break;  
            }  
        }  
  
        // 创建新节点并随机确定层数  
        int lvl = SkipListNode.randomLevel(MAX_LEVEL);  
        if (lvl > level) {  
            for (int i = level + 1; i <= lvl; i++) {  
                update[i] = header;  
            }  
            level = lvl;  
        }  
  
        SkipListNode<T> newNode = new SkipListNode<>(value, lvl);  
  
        // 插入新节点  
        for (int i = 0; i <= lvl; i++) {  
            newNode.forward[i] = update[i].forward[i];  
            update[i].forward[i] = newNode;  
        }  
    }  
  
    // ... 其他方法如删除、查找等可以根据需要实现  
}

七、总结

Redis的跳跃表是一种高效的有序数据结构，它通过维护多个指向其他节点的指针来实现快速访问节点。跳跃表在Redis中主要被用作有序集合的底层实现之一，具有搜索速度快、实现简单和支持范围查询等优点。通过随机层数的做法，跳跃表在插入和删除节点时能够保持较低的复杂度，从而满足Redis在高性能场景下的需求。

目录CONTENT

理解Redis的Skiplist