深入理解跳表及其在Redis中的应用

一、跳表基础概念

跳表(Skip List)是一种基于并联链表的数据结构，由William Pugh于1990年发明。它能够达到与平衡树相同的O(logN)时间复杂度，但实现更为简单。

跳表的核心特点

1. 多层链表结构：跳表由多层有序链表组成
2. 有序性：每一层链表都按元素升序(默认)排列
3. 随机层数：元素出现在哪一层是随机决定的，但出现在第k层意味着k层以下所有层都会包含该元素
4. 完整底层：底层链表包含所有元素
5. 头尾节点：头节点和尾节点不存储元素，其层数代表跳表的最大层数
6. 节点指针：每个节点包含两个指针：
   • 指向同层链表的后一节点
   • 指向下层链表的同元素节点

跳表优势

跳表相比平衡树的优势在于：

• 实现简单
• 对并发友好
• 不需要复杂的再平衡操作
• 空间效率较高

二、跳表实现细节

1. 跳表节点定义

public class SkiplistNode {
    public int data;          // 节点存储的数据
    public SkiplistNode next; // 指向同层下一节点
    public SkiplistNode down; // 指向下层同元素节点
    public int level;         // 节点所在层数
    
    public SkiplistNode(int data, int level) {
        this.data = data;
        this.level = level;
    }
}

2. 跳表初始化

跳表初始化时需要：

1. 随机指定初始层数
2. 创建各层头尾节点
3. 建立头尾节点间的层级关系

public class Skiplist {
    public LinkedList<SkiplistNode> headNodes; // 存储各层头节点
    public LinkedList<SkiplistNode> tailNodes; // 存储各层尾节点
    public int curLevel;                      // 当前跳表层数
    public Random random;
    
    public Skiplist() {
        random = new Random();
        headNodes = new LinkedList<>();
        tailNodes = new LinkedList<>();
        curLevel = getRandomLevel(); // 随机初始层数
        
        // 初始化头尾节点
        SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);
        SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);
        
        for (int i = 0; i <= curLevel; i++) {
            head.next = tail;
            headNodes.addFirst(head);
            tailNodes.addFirst(tail);
            
            // 创建更高层的头尾节点
            SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
            SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
            headNew.down = head;
            tailNew.down = tail;
            head = headNew;
            tail = tailNew;
        }
    }
    
    // 获取随机层数
    private int getRandomLevel() {
        int level = 0;
        while (random.nextInt(2) > 1) {
            level++;
        }
        return level;
    }
}

3. 跳表操作

添加元素

添加元素步骤：

1. 随机确定新元素的层数
2. 若层数超过当前跳表层数，则扩展跳表层数
3. 从顶层开始，逐层插入新节点

public void add(int num) {
    // 获取随机层数
    int level = getRandomLevel();
    
    // 需要扩展层数的情况
    if (level > curLevel) {
        expanLevel(level - curLevel);
    }
    
    // 创建新节点
    SkiplistNode curNode = new SkiplistNode(num, level);
    SkiplistNode preNode = headNodes.get(curLevel - level);
    
    // 逐层插入
    for (int i = 0; i <= level; i++) {
        // 找到插入位置
        while (preNode.next.data < num) {
            preNode = preNode.next;
        }
        
        // 插入节点
        curNode.next = preNode.next;
        preNode.next = curNode;
        
        // 如果不是底层，继续向下层插入
        if (curNode.level > 0) {
            SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);
            curNode.down = downNode;
            curNode = downNode;
        }
        
        // 移动到下一层
        preNode = preNode.down;
    }
}

// 扩展层数
private void expanLevel(int expanCount) {
    SkiplistNode head = headNodes.getFirst();
    SkiplistNode tail = tailNodes.getFirst();
    
    for (int i = 0; i < expanCount; i++) {
        SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
        SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
        headNew.down = head;
        tailNew.down = tail;
        head = headNew;
        tail = tailNew;
        headNodes.addFirst(head);
        tailNodes.addFirst(tail);
    }
}

搜索元素

搜索规则：

1. 从顶层开始搜索
2. 目标值大于当前节点的后一节点值时，继续向后搜索
3. 目标值大于当前节点值但小于后一节点值时，向下移动一层
4. 目标值等于当前节点值时，搜索成功

public boolean search(int target) {
    SkiplistNode curNode = headNodes.getFirst();
    
    while (curNode != null) {
        if (curNode.next.data == target) {
            return true;
        } else if (curNode.next.data > target) {
            curNode = curNode.down; // 向下移动
        } else {
            curNode = curNode.next; // 向后移动
        }
    }
    return false;
}

删除元素

删除步骤：

1. 按照搜索方式找到待删除节点
2. 从最高层开始，逐层删除该节点
3. 每层删除都是让前一节点直接指向后一节点

public boolean erase(int num) {
    SkiplistNode curNode = headNodes.getFirst();
    
    while (curNode != null) {
        if (curNode.next.data == num) {
            SkiplistNode preDeleteNode = curNode;
            while (true) {
                // 删除当前层节点
                preDeleteNode.next = curNode.next.next;
                
                // 向下移动
                preDeleteNode = preDeleteNode.down;
                
                if (preDeleteNode == null) {
                    return true; // 底层已删除完毕
                }
                
                // 找到下一层的待删除节点前一节点
                while (preDeleteNode.next.data != num) {
                    preDeleteNode = preDeleteNode.next;
                }
            }
        } else if (curNode.next.data > num) {
            curNode = curNode.down;
        } else {
            curNode = curNode.next;
        }
    }
    return false;
}

三、跳表在Redis中的应用

Redis的有序集合(ZSet)底层使用了跳表作为数据结构之一。

Redis中的ZSet结构

typedef struct zset {
    dict *dict;         // 字典，保存member到score的映射
    zskiplist *zsl;     // 跳表，按score排序保存所有元素
} zset;

Redis跳表实现特点

1. 随机层数生成：
   • Redis使用概率p=0.25
   • 最大层数限制为32
   • 层数生成算法：

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

2. 节点平均层数：

   • 节点层数至少为1
   • 层数k的概率为p^(k-1)*(1-p)
   • 当p=0.25时，平均层数为1/(1-p)=1.33

3. 幂次定律：

   • 跳表层数分布符合幂次定律
   • 大多数节点层数较低，少数节点层数较高

四、跳表与平衡树的比较

五、总结

1. 跳表是一种高效的概率性数据结构，可以达到与平衡树相同的O(logN)时间复杂度
2. 跳表通过多层链表实现快速查找，高层链表充当"快速通道"
3. Redis的有序集合使用跳表作为底层实现之一，配合字典提供高效操作
4. 跳表相比平衡树实现更简单，更适合并发环境，但空间开销略高
5. 跳表的层数分布遵循幂次定律，大多数节点位于较低层

跳表因其简单高效的特性，在许多场景下可以替代平衡树，是现代系统中常用的数据结构之一。