跳跃表SkipList深度解析

老王两点中 2025-04-02

Redis 中的有序集合（ZSet）是一种非常灵活的数据结构，它不仅可以存储唯一的成员，还能为每个成员分配一个分数（score），从而实现对成员的排序。在 Redis 内部，有序集合ZSet使用了两种数据结构来实现：跳跃表（SkipList）和哈希表（Dict）。跳跃表作为一种数据结构，具有简单易实现、性能优越的特点，非常适合 Redis 这样的高性能数据库。

一、跳跃表概述

跳跃表是一种随机化的数据结构，它通过在链表的基础上添加多级索引层来提高查找效率。这种数据结构可以看作是平衡树的一种替代方案，但它在实现上更为简单，同时在某些方面甚至可以提供更好的性能。

1. 跳跃表的主要优点

平均查找时间复杂度为 O(log N)。
插入和删除操作的平均时间复杂度也为 O(log N)。
实现简单，相比平衡树来说更容易理解和实现。
由于使用了指针，它在内存使用上比平衡树更灵活。

二、跳跃表的结构

每个节点至少有一个指向下一个节点的指针（称为“第 0 层”），更高的层则可能有更多的指针。节点的层数是随机的，但通常不超过某个预定义的最大层数，以防止过大的内存消耗。

1. 数据项

存储的数据，对于 Redis 的 ZSet 来说，数据项包括成员和分数。

2. 多个指针

指向其他节点的指针，这些指针构成了不同级别的索引层。

三、跳跃表的设计

跳跃表通过多层链表实现数据的“快速通道”，以空间换时间，将平均时间复杂度优化到 O(log N)，同时避免平衡树（如红黑树）的复杂再平衡操作。

1. 随机层数

新加入的节点随机确定其层数，通常采用一个概率分布，例如以 1/4 的概率增加一层。

2. 层级索引

每一层都构成一个链表，高层索引指向底层索引中的节点，形成一个层次结构。

3. 高效查找

查找操作利用索引层快速定位目标节点。

4. 动态调整

随着节点的增加或删除，跳跃表会动态调整层数以保持性能。

四、跳跃表的实现

1. 节点结构

每个节点包含成员、分数以及指向下一节点的指针数组。
指针数组的长度对应节点的层数。

2. 查找算法

查找时从最高层开始，逐层向下移动，直到找到目标节点或确定目标不在表中。
查找过程中利用了跳跃表的索引结构，使得查找效率大大提高。

3. 插入和删除

插入时首先确定新节点的层数，然后在适当的层级插入新节点，并更新索引。
删除时需要遍历跳跃表以找到目标节点，并删除它以及相关的索引指针。

4. 层级调整

Redis 通过概率分布来控制节点的层数，以确保跳跃表的性能和内存消耗达到平衡。
通常，Redis 限制最高层数，以避免过高的内存使用。

5. Java 实现

下面是一个简化的跳表实现示例，使用 Java 编写。此示例展示了跳表的基本结构和核心操作，包括插入、查找和删除。

（1）节点类 (SkipListNode)

定义一个节点类，该类包含键值对、分数（score）以及指向其他节点的指针数组。

public class SkipListNode<K extends Comparable<K>, V> {
    private K key;
    private V value;
    private double score;
    private SkipListNode<K, V>[] next;


    public SkipListNode(K key, V value, double score, int level) {
      this.key = key;
      this.value = value;
      this.score = score;
      this.next = new SkipListNode[level];
    }
    public K getKey() {
        return key;
    }
    public void setKey(K key) {
        this.key = key;
    }
    public V getValue() {
        return value;
    }
    public void setValue(V value) {
        this.value = value;
    }
    public double getScore() {
        return score;
    }


    public void setScore(double score) {
        this.score = score;
    }


    public SkipListNode<K,V> getNext(int level) {
        if (level < next.length) {
            return next[level];
        }
        return null;
    }


    public void setNext(int level, SkipListNode<K,V> node) {
        if (level < next.length) {
            next[level] = node;
        }
    }


    @Override
    public String toString() {
        return "SkipListNode{" +
                "key=" + key +
                ",value=" + value +
                ", score=" + score +
                '}';
    }
}

（2）跳表类 (SkipList)

接下来定义跳表类，它包含跳表的顶层节点、当前层数等属性，并实现了基本操作。

import java.util.Random;


public class SkipList<K extends Comparable<K>, V> {
    private static final int MAX_LEVEL = 16;
    private static final double P = 0.25;
    private SkipListNode<K, V> head;
    private int levelCount;
    private Random random = new Random();


    public SkipList() {
        head = new SkipListNode<>(null, null, 0.0, MAX_LEVEL);
        levelCount = 1;
    }
    private int randomLevel() {
        int level = 1;
        while (random.nextDouble() < P && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }


    public boolean insert(K key, V value, double score) {
        int newLevel = randomLevel();
        if (newLevel > levelCount) {
            for (int i = levelCount; i < newLevel; i++) {
                head.setNext(i, null);
            }
            levelCount = newLevel;
        }
        SkipListNode<K, V> newNode = new SkipListNode<>(key, value, score, newLevel);
        SkipListNode<K, V>[] update = new SkipListNode[levelCount];
        SkipListNode<K, V> x = head;
        for (int i = levelCount -1 ; i >= 0; i--){
            while (x.getNext(i) != null && (x.getNext(i).getScore() < score || (x.getNext(i).getScore() == score && x.getNext(i).getKey().compareTo(key) < 0))) {
                x = x.getNext(i);
            }
            update[i] = x;
        }
        x = x.getNext(0);
        if (x != null && x.getScore() == score && x.getKey().equals(key)) {
            // 如果已经存在相同的分数，则更新键
            x.setKey(key);
        } else {
            for (int i = 0; i < newLevel; i++) {
                newNode.setNext(i, update[i].getNext(i));
                update[i].setNext(i, newNode);
            }
        }
        return true;
    }


    public boolean delete(K key, double score) {
        SkipListNode<K, V>[] update = new SkipListNode[levelCount];
        SkipListNode<K, V> x = head;
        for (int i = levelCount - 1; i >= 0; i--) {
            while (x.getNext(i) != null && (x.getNext(i).getScore() < score || (x.getNext(i).getScore() == score && x.getNext(i).getKey().compareTo(key) < 0))) {
                x = x.getNext(i);
            }
            update[i] = x;
        }
        x = x.getNext(0);


        if (x != null && x.getScore() == score && x.getKey().equals(key)) {
            for (int i = 0; i < levelCount; i++) {
                if (update[i].getNext(i) != x) {
                    break;
                }
                update[i].setNext(i, x.getNext(i));
            }
            // 清理多余的层级
            while (levelCount > 1 && head.getNext(levelCount - 1) == null) {
                levelCount--;
            }
            return true;
        }
        return false;
    }


    public V find(K key, double score) {
        SkipListNode<K, V> x = head;
        for (int i = levelCount - 1; i >= 0; i--) {
            while (x.getNext(i) != null && (x.getNext(i).getScore() < score || (x.getNext(i).getScore() == score && x.getNext(i).getKey().compareTo(key) < 0))) {
                x = x.getNext(i);
            }
        }
        x = x.getNext(0);
        if (x != null && x.getScore() == score && x.getKey().equals(key)) {
            return x.getValue();
        }else{
            return null;
        }
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        SkipListNode<K, V> p = head;
        while (p != null) {
            sb.append(p).append(" -> ");
            p = p.getNext(0);
        }
        sb.append("null");
        return sb.toString();
    }
}
 public class Main {
    public static void main(String[] args) {
        SkipList<String,Object> skipList = new SkipList<>(); 
        skipList.insert("Alice", "1",1.5);
        skipList.insert("Bob", "2",2.0);
        skipList.insert("Charlie", "3",3.5);
        skipList.insert("Diana", "4",2.5);


        System.out.println("SkipList: " + skipList);


        Object foundNode = skipList.find("Diana" ,2.5);
        if (foundNode != null) {
            System.out.println("Found Node: " + foundNode);
        } else {
            System.out.println("Node not found.");
        }


        boolean deleted = skipList.delete("Diana", 2.5);
        System.out.println("Deleted Diana: " + deleted);


        System.out.println("SkipList after deletion: " + skipList);
    }
    }
 }

6. 测试

SkipList: SkipListNode{key=null,value=null, score=0.0} -> SkipListNode{key=Alice,value=1, score=1.5} -> SkipListNode{key=Bob,value=2, score=2.0} -> SkipListNode{key=Diana,value=4, score=2.5} -> SkipListNode{key=Charlie,value=3, score=3.5} -> null
Found Node: 4
Deleted Diana: true
SkipList after deletion: SkipListNode{key=null,value=null, score=0.0} -> SkipListNode{key=Alice,value=1, score=1.5} -> SkipListNode{key=Bob,value=2, score=2.0} -> SkipListNode{key=Charlie,value=3, score=3.5} -> null

五、跳跃表优化

1. 层级概率

通过调整节点层级的概率分布，可以控制跳跃表的平均高度，从而减少内存消耗。

2. 压缩存储

对于整数分数的 ZSet，Redis 会使用整数集合（IntSet）来代替跳跃表，以减少内存占用。

3. 缓存机制

Redis 可能会在跳跃表中使用一些缓存机制，以减少频繁查找的开销。

4. 性能优化

ZSet 同时使用哈希表（dict）存储成员到分值的映射，实现 O(1) 的单元素查询（如 ZSCORE）。节点的 level 数组采用柔性数组，节省内存。

六、为什么选择跳跃表

Redis ZSet选择跳跃表而非红黑树等平衡树，主要基于以下考量：

实现简单：跳跃表的插入、删除和范围查询逻辑更易实现和维护。
范围查询高效：按层遍历比树的遍历更缓存友好。
并发友好：无复杂旋转操作，更易实现无锁并发（Redis 6.0 后的多线程模型未直接利用此点，但设计上留有空间）。

Redis 的跳跃表通过多层链表和随机层高，在保证高效操作（平均 O(log N)）的同时，简化了实现复杂度。结合哈希表，ZSet 在范围查询和单点查询间取得了平衡，成为支持排行榜、延迟队列等场景的理想数据结构。了解 Redis 中跳跃表的具体实现细节，可以帮助开发者更好地利用 Redis 的有序集合功能，为自己的应用程序提供高效的数据管理和排序服务。

redis

文章转载自老王两点中，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

跳跃表SkipList深度解析

评论