1. 跳跃表的原理
-
传统有序链表查询节点需要遍历，复杂度为O(n)。
《Redis5设计语言与源码分析》 - 上图可理解为三层有序链表，每列都代表相同的元素值，当做冗余。
- 以上图为例当查询节点51时，开始从顶层左侧开始遍历，链表下个节点为21，小于结果51，则继续查询，后续为null，则向下移，到第一层21位置，判断下个节点，41继续判断下个，61大于51则下移到第0层41位置，再下个节点为就是51。
- 这种跳表方式比线性存遍历少了2次查询，元素数量多时更有效率。
2. 跳跃表结构
《Redis5设计语言与源码分析》
- 图中最左边红框的是
zskiplist辅助作用，右边每列都是一个zskiplistNode节点（重点），zskiplist header指向头结点，头结点高度默认64，初始化时默认生成，不代表具体数据。 - zskiplistNode结构：
typedef struct zskiplistNode {
sds ele; // 对应zset的字符串数据
double score; // 对应zset里的分值
struct zskiplistNode *backward; // 指向前一个节点
// 用柔性数组代表图上列的高度
struct zskiplistLevel {
struct zskiplistNode *forward; //指向本层的下个节点
unsigned long span; // 本层的下个节点跨了几个元素
} level[];
} zskiplistNode;
- zskiplist结构：
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 如图代表头结点、尾节点
unsigned long length; //表长
int level; // 表高
} zskiplist;
3. 跳跃表实现
- 创建：
- 确定节点高度：每个节点的高度是0~63里随机的，高度越高概率越低，初始化为1层，每次取随机数有25%的几率再加一层继续循环，直到没有命中就跳出，最终确定层数，所以层数高的几率还是比较小的。
- 上面说过初始化时就默认带头结点，所以需要初始化一个高度64的节点，分值为0，因为没有后续节点所以zskiplistLevel的forward都是null。
- 添加和删除操作没有太难理解的，维护跳跃表forward、backward等相关数据和表结构即可。
4. 跳跃表应用
- Redis中主要用于有序集合，是有序集合的一种实现方式，有两个相关配置，满足一条就会转化成跳跃表，根据结构可以得知跳跃表是空间换效率的方式，所以阈值过低会导致内存浪费。
- zset-max-ziplist-entries(128)：zset元素个数大于128时转化为跳跃表，否则是ziplist。
- zset-max-ziplist-value(64)：zset有元素长度大于64时转化为跳跃表，否则是ziplist。
