https://blog.csdn.net/u013536232/article/details/105476382

最近跟着黄健宏老师的《redis设计与实现》学习redis数据结构，看到跳跃表一节时，发现只有两节：

如此简略，应该是很简单吧，嘿嘿，抱着这种想法，我打开了redis源码，查看了下跳跃表的插入函数，结果，完全看不懂啊。。。

于是乎我又看了看网上的一些博文，虽然比起直接看源码更舒适了些，但还是不能完全理解。。。

最终，自己硬啃了大半天，终于是彻底搞明白了，在此记录一下，以免自己以后忘记，也希望能帮助其他初学者快速理解。

跳跃表数据结构

首先，我们要知道跳跃表的数据结构是什么样的，这里直接贴源码（黄健宏老师注释版本）：

typedef struct zskiplist {// 头节点，尾节点    struct zskiplistNode *header, *tail;// 节点数量    unsigned long length;// 目前表内节点的最大层数    int level;} zskiplist;

这里补充说一下节点个数，看下面这个图：

这个图里有几个节点呢？答案是3个，这里你可能有两个疑问：

• *为什么不算头节点呢？**因为头节点不存储数据
• *那为什么两个2算一个节点呢？**这个问题先记着，这里你看到我的图应该还会另一个问题，那就是我画的这个和你在其他地方看到的不一样，你看到的大多是这样的：

区别在于，我画的那个并没有高层到低层的指针，而是用一个虚线框把同一列框了起来，这又是为啥呢？接着看跳跃表节点的数据结构你就明白了。

跳跃表节点数据结构

还是先给源码：

typedef struct zskiplistNode {// member 对象    robj *obj;// 分值    double score;// 后退指针    struct zskiplistNode *backward;// 层    struct zskiplistLevel {// 前进指针        struct zskiplistNode *forward;// 这个层跨越的节点数量        unsigned int span;    } level[];} zskiplistNode;