欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Redis跳跃表实现原理(加快在有序链表中的查找速度)

程序员文章站 2024-02-29 20:50:52
...

Redis跳跃表实现原理

我们知道二叉搜索算法能够高效的查询数据,但是需要一块连续的内存,而且增删改效率很低。
跳表,是基于链表实现的一种类似“二分”的算法。它可以快速的实现增,删,改,查操作。
我们先来看一下单向链表如何实现查找

Redis跳跃表实现原理(加快在有序链表中的查找速度)

当我们要在该单链表中查找某个数据的时候需要的时间复杂度为O(n).
怎么提高查询效率呢?如果我们给该单链表加一级索引,将会改善查询效率。

Redis跳跃表实现原理(加快在有序链表中的查找速度)

如图所示,当我们每隔一个节点就提取出来一个元素到上一层,把这一层称作索引,其中的down指针指向原始链表。

当我们查找元素16的时候,单链表需要比较10次,而加过索引的两级链表只需要比较7次。当数据量增大到一定程度的时候,效率将会有显著的提升。

如果我们再加多几级索引的话,效率将会进一步提升。这种链表加多级索引的结构,就叫做跳表。

Redis跳跃表实现原理(加快在有序链表中的查找速度)

跳表的查询时间复杂度可以达到O(logn)

 

 

高效的动态插入和删除

跳表也可以实现高效的动态更新,定位到要插入或者删除数据的位置需要的时间复杂度为O(logn).
在插入的时候,我们需要考虑将要插入的数据也插入到索引中去。在这里使用的策略是通过随机函数生成一个随机数K,然后将要插入的数据同时插入到k级以下的每级索引中。

一般来说,如果要做到严格 O(logn) ,上层结点个数应是下层结点个数的 1/2 。但是这样实现会把代码变得十分复杂,就失去了它在 OI 中使用的意义。

此外,我们在实现时,一般在插入时就确定数值的层数,而且层数不能简单的用随机数,而是以1/2的概率增加层数。

用实验中丢硬币的次数 K 作为元素占有的层数。显然随机变量 K 满足参数为 p = 1/2 的几何分布,K 的期望值 E[K] = 1/p = 2. 就是说,各个元素的层数,期望值是 2 层。

同时,为了防止出现极端情况,设计一个最大层数MAX_LEVEL。c语言中如果使用非指针版,定义这样一个常量会方便许多,更能节省空间。如果是指针版,可以不加限制地任由它增长。

Redis跳跃表实现原理(加快在有序链表中的查找速度)

 

跳表具有如下性质:

(1) 由很多层结构组成

(2) 每一层都是一个有序的链表

(3) 最底层(Level 1)的链表包含所有元素

(4) 如果一个元素出现在 Level i 的链表中,则它在 Level i 之下的链表也都会出现。

(5) 每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。

 

查找

从最上层开始,如果key小于或等于当层后继节点的key,则平移一位;如果key更大,则层数减1,继续比较。最终一定会到第一层。

Redis跳跃表实现原理(加快在有序链表中的查找速度)

 

插入

先确定该元素要占据的层数 K(采用丢硬币的方式,这完全是随机的)。

然后在 Level 1 ... Level K 各个层的链表都插入元素。

用Update数组记录插入位置,同样从顶层开始,逐层找到每层需要插入的位置,再生成层数并插入。

例子:插入 119, K = 2

Redis跳跃表实现原理(加快在有序链表中的查找速度)

 

如果 K 大于链表的层数,则要添加新的层。

例子:插入 119, K = 4

Redis跳跃表实现原理(加快在有序链表中的查找速度)

 

 

跳表的删除

在各个层中找到包含 x 的节点,使用标准的 delete from list 方法删除该节点。

例子:删除 71

Redis跳跃表实现原理(加快在有序链表中的查找速度)

 

redis基本数据结构之ZSet

ZSet数据结构类似于Set结构,只是ZSet结构中,每个元素都会有一个分值,然后所有元素按照分值的大小进行排列,相当于是一个进行了排序的链表。

如果ZSet是一个链表,而且内部元素是有序的,在进行元素插入和删除,以及查询的时候,就必须要遍历链表才行,时间复杂度就达到了O(n),这个在以单线程处理的Redis中是不能接受的。所以ZSet采用了一种跳跃表的实现。

这种跳跃表的实现,其实和二分查找的思路有点接近,只是一方面因为二分查找只能适用于数组,而无法适用于链表,所以为了让链表有二分查找类似的效率,就以空间换时间来达到目的。

跳跃表因为是一个根据分数权重进行排序的列表,可以再很多场景中进行应用,比如排行榜,搜索排序等等。

跳跃表的实现

Redis跳跃表实现原理(加快在有序链表中的查找速度)

Redis的跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个结构定义,其中zskiplistNode结构用于表示跳跃表节点,而zskiplist结构则用于保存跳跃表节点的相关信息,比如节点的数量,以及指向表头节点和表尾节点的指针等等。

上图展示了一个跳跃表示例,位于图片最左边的是zskiplist结构,该结构包含以下属性:

header:指向跳跃表的表头节点
tail:指向跳跃表的表尾节点
level:记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)
length:记录跳跃表的长度,也即是,跳跃表目前包含节点的数量(表头节点不计算在内)

 

位于zskiplist结构右方的是四个zskiplistNode结构,该结构包含以下属性:

层(level):节点中用L1、L2、L3等字样标记节点的各个层,L1代表第一层,L2代表第二层,依次类推。每个层都带有两个属性:前进指针和跨度。前进指针用于访问位于表尾方向的其他节点,而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中,连线上带有数字的箭头就代表前进指针,而那个数字就是跨度。当程序从表头向表尾进行遍历时,访问会沿着层的前进指针进行。

后退(backward)指针:节点中用BW字样标记节点的后退指针,它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。

分值(score):各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中,节点按各自所保存的分值从小到大排列。

成员对象(obj):各个节点中的o1、o2和o3是节点所保存的成员对象。

 

注意表头节点和其他节点的构造是一样的:表头节点也有后退指针、分值和成员对象,不过表头节点的这些属性都不会被用到,所以图中省略了这些部分,只显示了表头节点的各个层。

 

命令操作

添加元素,zadd zsetName score1 value1 score2 value2 score3 value3 .....

Redis跳跃表实现原理(加快在有序链表中的查找速度)

查看所有元素,zrange zsetName 0 -1

Redis跳跃表实现原理(加快在有序链表中的查找速度)

查看所有元素,按score逆序排列, zrevrange zsetName 0 -1

Redis跳跃表实现原理(加快在有序链表中的查找速度)

元素数量,zcard zsetName

Redis跳跃表实现原理(加快在有序链表中的查找速度)

获取指定value的分数, zscore zsetName value

Redis跳跃表实现原理(加快在有序链表中的查找速度)

获取指定value的排名,zrank zsetName value(从0开始)

Redis跳跃表实现原理(加快在有序链表中的查找速度)

获取指定分值区间中的元素, zrangebyscore zsetName scoreStart scoreEnd(包含上下区间)(注意inf表示无穷大,-inf表示服务券大)

Redis跳跃表实现原理(加快在有序链表中的查找速度)

获取指定分值区间中的元素,并且返回分数, zrangebyscore zsetName scoreStart scoreEnd withscores

Redis跳跃表实现原理(加快在有序链表中的查找速度)

删除元素,zrem zsetName value

Redis跳跃表实现原理(加快在有序链表中的查找速度)

 

 

跳表实现代码(Java)

package cc.wsyw126.java.algorithm;

/**
 * @author yangjunpeng
 * @version $Id: SkipList.java, v 0.1 2020年04月18日 下午10:09 yangjunpeng Exp $
 */
import java.util.Random;

public class SkipList {
    private static final int MAX_LEVEL  = 16;
    private int              levelCount = 1;
    private Node             head       = new Node();
    private Random           random     = new Random();

    /**
     * 查找value
     *
     * @param value
     * @return
     */
    public Node find(int value) {
        Node p = head;
        //下沉一个层次
        for (int i = levelCount - 1; i >= 0; i--) {
            //如果同层次下一个节点的值大于要找的值,则下沉一层。反之:同层次往后遍历。
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
        }
        //find
        if (p.forwards[0] != null && p.forwards[0].data == value) {
            return p.forwards[0];
        }

        return null;
    }

    /**
     * 构建跳表,插入value
     *
     * @param value
     */
    public void insert(int value) {
        Node p = head;
        int level = randomLevel();
        Node node = new Node();
        node.data = value;
        node.maxLevel = level;
        // 用update数组记录插入位。
        // 例子:a.forwards[i]指向b。
        // 开始时状态:a->b,此时记录下a,后面for循环会将这里改为a->value->b。
        Node[] update = new Node[level];
        for (int i = level - 1; i >= 0; i--) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
            //用update数组记录插入位。
            update[i] = p;
        }
        //for循环会将value,插入到待插入的位置:a->b改为a->value->b。
        for (int i = 0; i < level; i++) {
            node.forwards[i] = update[i].forwards[i];
            update[i].forwards[i] = node;
        }
        //如果新的层次更高,那么就更新。
        if (levelCount < level) {
            levelCount = level;
        }

    }

    /**
     * 删除value
     *
     *
     * @param value
     */
    public void delete(int value) {
        Node[] deleteNode = new Node[MAX_LEVEL];
        Node p = head;
        //同insert
        for (int i = levelCount - 1; i >= 0; i--) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
            deleteNode[i] = p;
        }
        //存在value对应的节点
        if (p.forwards[0] != null && p.forwards[0].data == value) {
            //for循环会将value删除。a->value->b修改为:a->b。
            for (int i = levelCount - 1; i >= 0; i--) {
                if (deleteNode[i] != null && deleteNode[i].forwards[i] != null
                    && deleteNode[i].forwards[i].data == value) {
                    deleteNode[i].forwards[i] = deleteNode[i].forwards[i].forwards[i];
                }
            }
        }
    }

    /**
     * 顺序输出链表中的数据
     */
    public void printAll() {
        Node p = head;
        while (p.forwards[0] != null) {
            System.out.print(p.forwards[0] + " ");
            p = p.forwards[0];
        }
        System.out.println();
    }

    /**
     * 随机生成层次
     * 用实验中丢硬币的次数 K 作为元素占有的层数。
     * 显然随机变量 K 满足参数为 p = 1/2 的几何分布,K 的期望值 E[K] = 1/p = 2.
     * 就是说,各个元素的层数,期望值是 2 层。
     *
     * @return
     */
    private int randomLevel() {
        int level = 0;
        for (int i = 0; i < MAX_LEVEL; i++) {
            if (random.nextInt() % 2 == 1) {
                level++;
            }
        }
        return level;
    }

    class Node {
        /** 存放数据 */
        private int    data;
        /** forwards[i] 表示这个结点在第 i 层的下一个结点编号。*/
        private Node[] forwards = new Node[MAX_LEVEL];
        /** 该节点最高层次 */
        private int    maxLevel;

        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("{data: ");
            sb.append(data);
            sb.append("; level: ");
            sb.append(maxLevel);
            sb.append(" }");
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        SkipList skipList = new SkipList();
        for (int i = 0; i < 5; i++) {
            skipList.insert(i);
        }

        int value = 16;
        Node node = skipList.find(value);
        System.out.println("node = " + node);

        skipList.printAll();

        skipList.delete(value);
        skipList.printAll();
        node = skipList.find(value);
        System.out.println("node = " + node);
    }

}

Docker 安装 Redis

https://www.runoob.com/docker/docker-install-redis.html

 

参考资料:
https://www.jianshu.com/p/43039adeb122
https://blog.csdn.net/belalds/article/details/93876483
https://blog.csdn.net/u010694337/article/details/52550593
https://www.cnblogs.com/*zuokan/p/11108417.html
备注:
转载请注明出处:https://blog.csdn.net/WSYW126/article/details/105611088
作者:WSYW126