Redis设计与实现第五章笔记
date
Jul 20, 2021
slug
Redis设计与实现第五章笔记
status
Published
tags
读书笔记
summary
跳表
type
Post
跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找。
跳表在Redis 的用途：
- 实现有序集合键
- 在集群节点中用作内部数据结构
5.1 跳表的实现
属性：
- header：指向跳表的表头节点
- tail：指向跳表的表尾节点
- level：记录目前跳表内，层数最大节点的层数
- length：跳表包含的节点数量
zskiplistNode属性：
- level：节点中用L1、L2、L3等字样标记节点的各个层。L1代表第一层等等。
- 前进指针：访问表尾方向的节点
- 跨度：记录前进指针指向的节点和当前节点的距离
- backward：后退指针。节点中用BW字样标识的。用于程序从表尾向表头遍历时使用
- score：分值，节点按各自保存的分值从小到大排列
- obj：成员对象。保存的具体数据
5.1.1 跳跃表节点
层
每次创建新节点时，程序会根据幂次定律（越大的数出现的概率越小）随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层数
前进指针
遍历跳表时使用
跨度
- 节点间的跨度越大，相距越远
- 指向NULL的所有前进指针的跨度都为0，因为没有指向任何节点
用来计算节点的排位：查找某个节点过程中，将沿途访问的所有层的跨度累计起来，就能得到该节点的排位
后退指针
由于每个节点只有一个后退指针，每次只能后退至前一个节点
分值和成员
score属性是一个double。
obj属性指向一个字符串对象，字符串对象保存着一个SDS值
各个节点保存的对象必须唯一，但是多个节点的分值可以一样：分值相同的节点按照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在前面（靠近表头的方向）。
5.1.2 跳表
