为何Redis使用跳表而非红黑树实现SortedSet

• 代码实现比红黑树好懂、好写多了，因为简单就代表可读性好，不易出错
• 跳表更灵活，可通过改变索引构建策略，有效平衡执行效率和内存消耗

因为红黑树比跳表诞生更早，很多编程语言中的Map类型（比如JDK 的 HashMap）都是通过红黑树实现的。业务开发时，直接从JDK拿来用，但跳表没有一个现成的实现，只能自己实现。

跳表的代码实现（Java 版）

数据结构定义

表中的元素使用结点来表示，结点的层数在它被插入时随机计算决定（与表中已有结点数目无关）。

一个i层的结点有i个前向指针（java中使用结点对象数组forward来表示），索引为从1到i。用MaxLevel来记录跳表的最大层数。

跳表的层数为当前所有结点中的最大层数（如果list为空，则层数为1）。

列表头header拥有从1到MaxLevel的前向指针：

public class SkipList {

    // 最高层数
    private final int MAX_LEVEL;
    // 当前层数
    private int listLevel;
    // 表头
    private SkipListNode listHead;
    // 表尾
    private SkipListNode NIL;
    // 生成randomLevel用到的概率值
    private final double P;
    // 论文里给出的最佳概率值
    private static final double OPTIMAL_P = 0.25;
    
    public SkipList() {
        // 0.25, 15
        this(OPTIMAL_P, (int)Math.ceil(Math.log(Integer.MAX_VALUE) / Math.log(1 / OPTIMAL_P)) - 1);
    }

    public SkipList(double probability, int maxLevel) {
        P = probability;
        MAX_LEVEL = maxLevel;

        listLevel = 1;
        listHead = new SkipListNode(Integer.MIN_VALUE, null, maxLevel);
        NIL = new SkipListNode(Integer.MAX_VALUE, null, maxLevel);
        for (int i = listHead.forward.length - 1; i >= 0; i--) {
            listHead.forward[i] = NIL;
        }
    }

    // 内部类
    class SkipListNode {
        int key;
        T value;
        SkipListNode[] forward;
        
        public SkipListNode(int key, T value, int level) {
            this.key = key;
            this.value = value;
            this.forward = new SkipListNode[level];
        }
    }
}

搜索算法

按key搜索，找到返回该key对应的value，未找到则返回null。

通过遍历forward数组来需找特定的searchKey。假设skip list的key按照从小到大的顺序排列，那么从跳表的当前最高层listLevel开始寻找searchKey。在某一层找到一个非小于searchKey的结点后，跳到下一层继续找，直到最底层为止。那么根据最后搜索停止位置的下一个结点，就可以判断searchKey在不在跳表中。

在跳表中找8的过程：

插入和删除算法

都是通过查找与连接（search and splice）：

维护一个update数组，在搜索结束之后，update[i]保存的是待插入/删除结点在第i层的左侧结点。

插入

若key不存在，则插入该key与对应的value；若key存在，则更新value。

如果待插入的结点的层数高于跳表的当前层数listLevel，则更新listLevel。

选择待插入结点的层数randomLevel：

randomLevel只依赖于跳表的最高层数和概率值p。

另一种实现方法为，如果生成的randomLevel大于当前跳表的层数listLevel，那么将randomLevel设置为listLevel+1，这样方便以后的查找，在工程上是可以接受的，但同时也破坏了算法的随机性。

删除

删除特定的key与对应的value。如果待删除的结点为跳表中层数最高的结点，那么删除之后，要更新listLevel。

public class SkipList {

    // 最高层数
    private final int MAX_LEVEL;
    // 当前层数
    private int listLevel;
    // 表头
    private SkipListNode listHead;
    // 表尾
    private SkipListNode NIL;
    // 生成randomLevel用到的概率值
    private final double P;
    // 论文里给出的最佳概率值
    private static final double OPTIMAL_P = 0.25;

    public SkipList() {
        // 0.25, 15
        this(OPTIMAL_P, (int)Math.ceil(Math.log(Integer.MAX_VALUE) / Math.log(1 / OPTIMAL_P)) - 1);
    }

    public SkipList(double probability, int maxLevel) {
        P = probability;
        MAX_LEVEL = maxLevel;

        listLevel = 1;
        listHead = new SkipListNode(Integer.MIN_VALUE, null, maxLevel);
        NIL = new SkipListNode(Integer.MAX_VALUE, null, maxLevel);
        for (int i = listHead.forward.length - 1; i >= 0; i--) {
            listHead.forward[i] = NIL;
        }
    }

    // 内部类
    class SkipListNode {
        int key;
        T value;
        SkipListNode[] forward;
        
        public SkipListNode(int key, T value, int level) {
            this.key = key;
            this.value = value;
            this.forward = new SkipListNode[level];
        }
    }

    public T search(int searchKey) {
        SkipListNode curNode = listHead;

        for (int i = listLevel; i > 0; i--) {
            while (curNode.forward[i].key [] update = new SkipListNode[MAX_LEVEL];
        SkipListNode curNode = listHead;

        for (int i = listLevel - 1; i >= 0; i--) {
            while (curNode.forward[i].key  newNode = new SkipListNode(searchKey, newValue, lvl);

            for (int i = 0; i [] update = new SkipListNode[MAX_LEVEL];
        SkipListNode curNode = listHead;

        for (int i = listLevel - 1; i >= 0; i--) {
            while (curNode.forward[i].key  0 && listHead.forward[listLevel - 1] == NIL) {
                listLevel--;
            }
        }
    }

    private int randomLevel() {
        int lvl = 1;
        while (lvl = 0; i--) {
            SkipListNode curNode = listHead.forward[i];
            while (curNode != NIL) {
                System.out.print(curNode.key + "->");
                curNode = curNode.forward[i];
            }
            System.out.println("NIL");
        }
    }

    public static void main(String[] args) {
        SkipList sl = new SkipList();
        sl.insert(20, 20);
        sl.insert(5, 5);
        sl.insert(10, 10);
        sl.insert(1, 1);
        sl.insert(100, 100);
        sl.insert(80, 80);
        sl.insert(60, 60);
        sl.insert(30, 30);
        sl.print();
        System.out.println("---");
        sl.delete(20);
        sl.delete(100);
        sl.print();
    }
}

本篇关于《为何Redis使用跳表而非红黑树实现SortedSet》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于数据库的相关知识，请关注golang学习网公众号！