### 2.4.1 跳跃表的结构
跳跃表由 `server.h/zskiplist` 和 `server.h/zskiplistNode` 定义:
```c
// 跳跃表结点
typedef struct zskiplistNode {
sds ele; // 成员对象
double score; // 结点按照各自的分值从小到大排序
struct zskiplistNode *backward; // 后退指针,用于从表尾向头遍历
struct zskiplistLevel { // 层
struct zskiplistNode *forward; // 前进指针
unsigned long span; // 跨度
} level[];
} zskiplistNode;
// 跳跃表
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 表头表尾结点
unsigned long length; // 结点长度
int level; // 最大层数
} zskiplist;
```
- 层:level数组包含多个元素,每个元素包含指向其他结点的指针
- 理论上层的数量越多,访问其他结点的速度越快
- 每次创建一个新结点时,程序都根据幂次定律(越大的数出现的概率越小)随机生成一个介于1到32的数作为level数组的大小
- 前进指针:用于从头到尾遍历
- 跨度:记录两个结点之间的距离,用于计算排位(rank)
- 跨度越大,相距越远
- 指向NULL的所有前进指针跨度都是0
- 后退指针:用于从后向前遍历
- 分值和成员:
- 表中所有结点都按照分值(score)进行从小到大的排序
- 成员对象(ele)是一个SDS类型,必须唯一
- 空白目录
- 精简版Spring的实现
- 0 前言
- 1 注册和获取bean
- 2 抽象工厂实例化bean
- 3 注入bean属性
- 4 通过XML配置beanFactory
- 5 将bean注入到bean
- 6 加入应用程序上下文
- 7 JDK动态代理实现的方法拦截器
- 8 加入切入点和aspectj
- 9 自动创建AOP代理
- Redis原理
- 1 Redis简介与构建
- 1.1 什么是Redis
- 1.2 构建Redis
- 1.3 源码结构
- 2 Redis数据结构与对象
- 2.1 简单动态字符串
- 2.1.1 sds的结构
- 2.1.2 sds与C字符串的区别
- 2.1.3 sds主要操作的API
- 2.2 双向链表
- 2.2.1 adlist的结构
- 2.2.2 adlist和listNode的API
- 2.3 字典
- 2.3.1 字典的结构
- 2.3.2 哈希算法
- 2.3.3 解决键冲突
- 2.3.4 rehash
- 2.3.5 字典的API
- 2.4 跳跃表
- 2.4.1 跳跃表的结构
- 2.4.2 跳跃表的API
- 2.5 整数集合
- 2.5.1 整数集合的结构
- 2.5.2 整数集合的API
- 2.6 压缩列表
- 2.6.1 压缩列表的结构
- 2.6.2 压缩列表结点的结构
- 2.6.3 连锁更新
- 2.6.4 压缩列表API
- 2.7 对象
- 2.7.1 类型
- 2.7.2 编码和底层实现
- 2.7.3 字符串对象
- 2.7.4 列表对象
- 2.7.5 哈希对象
- 2.7.6 集合对象
- 2.7.7 有序集合对象
- 2.7.8 类型检查与命令多态
- 2.7.9 内存回收
- 2.7.10 对象共享
- 2.7.11 对象空转时长
- 3 单机数据库的实现
- 3.1 数据库
- 3.1.1 服务端中的数据库
- 3.1.2 切换数据库
- 3.1.3 数据库键空间
- 3.1.4 过期键的处理
- 3.1.5 数据库通知
- 3.2 RDB持久化
- 操作系统
- 2021-01-08 Linux I/O 操作
- 2021-03-01 Linux 进程控制
- 2021-03-01 Linux 进程通信
- 2021-06-11 Linux 性能优化
- 2021-06-18 性能指标
- 2022-05-05 Android 系统源码阅读笔记
- Java基础
- 2020-07-18 Java 前端编译与优化
- 2020-07-28 Java 虚拟机类加载机制
- 2020-09-11 Java 语法规则
- 2020-09-28 Java 虚拟机字节码执行引擎
- 2020-11-09 class 文件结构
- 2020-12-08 Java 内存模型
- 2021-09-06 Java 并发包
- 代码性能
- 2020-12-03 Java 字符串代码性能
- 2021-01-02 ASM 运行时增强技术
- 理解Unsafe
- Java 8
- 1 行为参数化
- 1.1 行为参数化的实现原理
- 1.2 Java 8中的行为参数化
- 1.3 行为参数化 - 排序
- 1.4 行为参数化 - 线程
- 1.5 泛型实现的行为参数化
- 1.6 小结
- 2 Lambda表达式
- 2.1 Lambda表达式的组成
- 2.2 函数式接口
- 2.2.1 Predicate
- 2.2.2 Consumer
- 2.2.3 Function
- 2.2.4 函数式接口列表
- 2.3 方法引用
- 2.3.1 方法引用的类别
- 2.3.2 构造函数引用
- 2.4 复合方法
- 2.4.1 Comparator复合
- 2.4.2 Predicate复合
- 2.4.3 Function复合
- 3 流处理
- 3.1 流简介
- 3.1.1 流的定义
- 3.1.2 流的特点
- 3.2 流操作
- 3.2.1 中间操作
- 3.2.2 终端操作
- 3.3.3 构建流
- 3.3 流API
- 3.3.1 flatMap的用法
- 3.3.2 reduce的用法
- 3.4 collect操作
- 3.4.1 collect示例
- 3.4.2 Collector接口