FantasticMao 技术笔记
BlogGitHub
  • README
  • C & Unix
    • C
      • 《C 程序设计语言》笔记
      • C 语言中的陷阱
      • CMake 示例
      • GNU make
      • LLVM Clang
      • Nginx 常用模块
      • Vim 常用命令
    • Unix-like
      • 《深入理解计算机系统》笔记
      • 《UNIX 环境高级编程》笔记 - UNIX 基础知识
      • 《UNIX 环境高级编程》笔记 - 文件 IO
      • 《UNIX 环境高级编程》笔记 - 标准 IO 库
      • 《鳥哥的 Linux 私房菜》笔记 - 目录配置
      • 《鳥哥的 Linux 私房菜》笔记 - 认识与学习 bash
      • 《鳥哥的 Linux 私房菜》笔记 - 任务管理
      • OpenWrt 中的陷阱
      • iptables 工作机制
  • Go
    • 《A Tour of Go》笔记
    • Go vs C vsJava
    • Go 常用命令
    • Go 语言中的陷阱
  • Java
    • JDK
      • 《Java 并发编程实战》笔记 - 线程池的使用
      • 设计模式概览
      • 集合概览
      • HashMap 内部算法
      • ThreadLocal 工作机制
      • Java Agent
    • JVM
      • 《深入理解 Java 虚拟机》笔记 - Java 内存模型与线程
      • JVM 运行时数据区
      • 类加载机制
      • 垃圾回收算法
      • 引用类型
      • 垃圾收集算法
      • 垃圾收集器
    • Spring
      • Spring IoC 容器扩展点
      • Spring Transaction 声明式事务管理
      • Spring Web MVC DispatcherServlet 工作机制
      • Spring Security Servlet 实现原理
    • 其它
      • 《Netty - One Framework to rule them all》演讲笔记
      • Hystrix 设计与实现
  • JavaScript
    • 《写给大家看的设计书》笔记 - 设计原则
    • 《JavaScript 权威指南》笔记 - jQuery 类库
  • 数据库
    • ElasticSearch
      • ElasticSearch 概览
    • HBase
      • HBase 数据模型
    • Prometheus
      • Prometheus 概览
      • Prometheus 数据模型和指标类型
      • Prometheus 查询语法
      • Prometheus 存储原理
      • Prometheus vs InfluxDB
    • Redis
      • 《Redis 设计与实现》笔记 - 简单动态字符串
      • 《Redis 设计与实现》笔记 - 链表
      • 《Redis 设计与实现》笔记 - 字典
      • 《Redis 设计与实现》笔记 - 跳跃表
      • 《Redis 设计与实现》笔记 - 整数集合
      • 《Redis 设计与实现》笔记 - 压缩列表
      • 《Redis 设计与实现》笔记 - 对象
      • Redis 内存回收策略
      • Redis 实现分布式锁
      • Redis 持久化机制
      • Redis 数据分片方案
      • 使用缓存的常见问题
    • MySQL
      • 《高性能 MySQL》笔记 - Schema 与数据类型优化
      • 《高性能 MySQL》笔记 - 创建高性能的索引
      • 《MySQL Reference Manual》笔记 - InnoDB 和 ACID 模型
      • 《MySQL Reference Manual》笔记 - InnoDB 多版本
      • 《MySQL Reference Manual》笔记 - InnoDB 锁
      • 《MySQL Reference Manual》笔记 - InnoDB 事务模型
      • B-Tree 简述
      • 理解查询执行计划
  • 中间件
    • gRPC
      • gRPC 负载均衡
    • ZooKeeper
      • ZooKeeper 数据模型
    • 消息队列
      • 消息积压解决策略
      • RocketMQ 架构设计
      • RocketMQ 功能特性
      • RocketMQ 消息存储
  • 分布式系统
    • 《凤凰架构》笔记
    • 系统设计思路
    • 系统优化思路
    • 分布式事务协议:二阶段提交和三阶段提交
    • 分布式系统的技术栈
    • 分布式系统的弹性设计
    • 单点登录解决方案
    • 容错,高可用和灾备
  • 数据结构和算法
    • 一致性哈希
    • 布隆过滤器
    • 散列表
  • 网络协议
    • 诊断工具
    • TCP 协议
      • TCP 报文结构
      • TCP 连接管理
由 GitBook 提供支持
在本页
  • Java 中的跳跃表 - ConcurrentSkipListMap
  • 数据结构
  • Redis 中的跳跃表
  • 数据结构
  1. 数据库
  2. Redis

《Redis 设计与实现》笔记 - 跳跃表

Java 中的跳跃表 - ConcurrentSkipListMap

数据结构

/**
 * Nodes hold keys and values, and are singly linked in sorted
 * order, possibly with some intervening marker nodes. The list is
 * headed by a header node accessible as head.node. Headers and
 * marker nodes have null keys. The val field (but currently not
 * the key field) is nulled out upon deletion.
 */
static final class Index<K,V> {
    final Node<K,V> node;  // currently, never detached
    final Index<K,V> down;
    Index<K,V> right;
    Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
        this.node = node;
        this.down = down;
        this.right = right;
    }
}

/**
 * Index nodes represent the levels of the skip list.
 */
static final class Node<K,V> {
    final K key; // currently, never detached
    V val;
    Node<K,V> next;
    Node(K key, V value, Node<K,V> next) {
        this.key = key;
        this.val = value;
        this.next = next;
    }
}
+-+                 +-+
|1|---------------->|5|--> NULL
+-+                 +-+
 |                   |
 v                   v
+-+       +-+       +-+       +-+
|1|------>|3|-------|5|------>|7|--> NULL
+-+       +-+       +-+       +-+
 |         |         |         |
 v         v         v         v
+-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
|1|->|2|->|3|->|4|->|5|->|6|->|7|->|8|->|9|-> NULL
+-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
 |    |    |    |    |    |    |    |    |
 v    v    v    v    v    v    v    v    v
NULL NULL NULL NULL NULL NULL NULL NULL NULL

Redis 中的跳跃表

数据结构

zskiplistNoe

typedef struct zskiplistNode {

    // 后退指针
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成员对象
    robj *obj;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;
                                  +-------------+
                                  |zskiplistNode|
                                  |-------------|
                                  | level[4]    |
                 +-------------+  |-------------|
                 |zskiplistNode|  | level[3]    |
                 |-------------|  |-------------|
                 | level[2]    |  | level[2]    |
+-------------+  |-------------|  |-------------|
|zskiplistNode|  | level[1]    |  | level[1]    |
|-------------|  |-------------|  |-------------|
| level[0]    |  | level[0]    |  | level[0]    |
|-------------|  |-------------|  |-------------|
| backward    |  | backward    |  | backward    |
|-------------|  |-------------|  |-------------|
| score       |  | score       |  | score       |
|-------------|  |-------------|  |-------------|
| obj         |  | obj         |  | obj         |
+-------------+  +-------------+  +-------------+
+--------+                                          +--------+
|level[2]|----------------------------------------->|level[2]|--> NULL
|--------|                +--------+                |--------|                +--------+
|level[1]|--------------->|level[1]|--------------->|level[1]|--------------->|level[1]| --> NULL
|--------|   +--------+   |--------|   +--------+   |--------|   +--------+   |--------|   +--------+   +--------+
|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|--> NULL
|--------|   |--------|   |--------|   |--------|   |--------|   |--------|   |--------|   |--------|   |--------|
|backward|<--|backward|<--|backward|<--|backward|<--|backward|<--|backward|<--|backward|<--|backward|<--|backward|
|--------|   |--------|   |--------|   |--------|   |--------|   |--------|   |--------|   |--------|   |--------|
|score=1 |   |score=2 |   |score=3 |   |score=4 |   |score=5 |   |score=6 |   |score=7 |   |score=8 |   |score=9 |
|--------|   |--------|   |--------|   |--------|   |--------|   |--------|   |--------|   |--------|   |--------|
|obj1    |   |obj2    |   |obj3    |   |obj4    |   |obj5    |   |obj6    |   |obj7    |   |obj8    |   |obj9    |
+--------+   +--------+   +--------+   +--------+   +--------+   +--------+   +--------+   +--------+   +--------+

字段描述:

  1. zskiplistNode 的 level 数组可以包含多个元素,每个元素都包含一个指向其它节点的指针;

    1. zskiplistLevel 每层都有一个指向表尾方向的指针(level[i].forward),用于从表头向表尾访问节点;

    2. zskiplistLevel 每层都有一个跨度(level[i].span),用于记录两个节点之间的距离;

  2. zskiplistNode 的 backward 属性用于从表尾向表头方向访问节点,但每次只能后退一个节点;

  3. zskiplistNode 的 score 属性是一个 double 类型的浮点数,跳跃表中的所有节点都按分值的从小到大来排序;

  4. zskiplistNode 的 obj 属性是一个指向字符串对象的指针,字符串对象保存着一个 SDS 值。

zskiplistlist

typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;
+---------+
|zskiplist|       +--------+   +--------+                +--------+
|---------|       |level[1]|-->|level[1]|--------------->|level[1]|--> NULL
| head    |------>|--------|   |--------|   +--------+   |--------|
|---------|       |level[0]|-->|level[0]|-->|level[0]|-->|level[0]|--> NULL
| tail    |---+   +--------+   |--------|   |--------|   |--------|
|---------|   |        NULL <--|backward|<--|backward|<--|backward|
| level   |   |                |--------|   |--------|   |--------|
|---------|   |                |score=1 |   |score=2 |   |score=3 |
| length  |   |                |--------|   |--------|   |--------|
+---------+   |                |obj1    |   |obj2    |   |obj3    |
              |                +--------+   +--------+   +--------+
              |                                               ^
              +-----------------------------------------------+

最后更新于1年前