Redis跳表

Redis跳表

  • 跳表是一种有序数据结构,它通过在每个节点维持多个指向其他节点的指针,从而达到快速访问节点的目的

  • 跳表支持平均O(logN),最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点

  • 大部分人时候,跳表的效率可以和平衡树媲美,而且跳表的实现更方便简单

  • redis只在两个地方使用到了跳表,一个是实现有序集合键,另一个实在集群节点中用作内部数据结构

  • 跳表的实现:

    • 跳表由zskiplistNode和zskiplist两个结构定义

    -在这里插入图片描述

    • zskiplist:

      • header表示表头节点

      • tail表示表尾节点

      • level表示节点的最大层数

      • length:跳表的节点数量(不包含表头节点)

      • typedef struct zskiplist {
            //表头节点和表尾节点
            struct zskiplistNode *header, #tail;
            //表中节点数量
            unsigned long lenth;
            //最大的层数
            int level;
            
        } zskiplist
        
    • zskiplistNode:

      • level(层):每层都带有两个属性:前进指针和跨度。节点用L1、L2标记各个层

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

      • score(分值):各个节点中的1.0、2.0是节点所保存的分值。在跳表中,各个节点按各自的分值从小到大排列,若分值相同,会比较成员对象在字典序中的大小来进行排序,小的排前面。所以说节点对象是不能重复的

      • obj(成员对象):各个节点中的O1,O2是节点所保存的成员对象

      • typedef struct zskiplistNode {
            //后退指针
            struct zskiplistNode *backward;
            //分值
            double score;
            //成员对象
            robj *obj;
            //层
            struct zskiplistLevel {
                //前进指针
                struct zskiplistNode *forward;
                //跨度
                umsigned int span;
            } level;
              
        } zskiplistNode
        

相关推荐

  1. golang实现skiplist

    2024-06-13 23:50:01       28 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-06-13 23:50:01       18 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-06-13 23:50:01       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-06-13 23:50:01       18 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-06-13 23:50:01       20 阅读

热门阅读

  1. 为什么要选择AWS?AWS的优势有哪些?

    2024-06-13 23:50:01       6 阅读
  2. 【C++学习笔记 1】C++程序是怎样运行的

    2024-06-13 23:50:01       4 阅读
  3. 【无标题】计算机网络 4.2同轴电缆

    2024-06-13 23:50:01       6 阅读
  4. Spring Boot 的启动原理、Spring Boot 自动配置原理

    2024-06-13 23:50:01       7 阅读
  5. roles安装wordpress

    2024-06-13 23:50:01       5 阅读
  6. Kafka中的RPC:Server端代码流程简单概述

    2024-06-13 23:50:01       9 阅读
  7. React 事件函数传播及捕获

    2024-06-13 23:50:01       6 阅读