Redis原理篇(SkipList)

一.概述

本质是双端链表，只不过在正向遍历时可以不一个一个遍历，而是可以跳着遍历。

怎么实现的呢，下面是SkipList源码

二.源码

1. zskiplist

意义：跳表

zskiplist里面有头指针和尾指针，节点数量，最大索引层级

2.zskiplistNode

意义：跳表的每个节点

zskiplistNode 里面有ele(节点存储的值，sds是动态字符串类型)

2.1 score

每个节点有个score权值，用来排序和查找，查找的时候将要查找的值先用与生成score一样的算法生成待查的score值，然后再根据每个节点的score值来查找该值

2.2 *backward

指向前一个节点的指针，注意，在倒序遍历时不能跳表

2.3 zskiplistLevel

zskiplistLevel是索引层级结构体数组，有level[1],level[2],level[15]等，每个结构体记录了该索引层级下的下一个节点的指针以及从当前节点按照该索引层级跳到下一节点的跨度

下面是一个结构图

?level数组里面的元素的forwad指向的是下一个节点的地址，而不是途中显示的level的地址。

三.总结