Redis跳跃表原理

1）跳跃表由很多层构成。
2）跳跃表有一个头（header）节点，头节点中有一个64层的结构，每层的结构包含指向本层的下个节点的指针，指向本层下个节点中间所跨越的节点个数为本层的跨度（span）。
3）除头节点外，层数最多的节点的层高为跳跃表的高度（level）。
4）每层都是一个有序链表，数据递增。
5）除header节点外，一个元素在上层有序链表中出现，则它一定会在下层有序链表中出现。
6）跳跃表每层最后一个节点指向NULL，表示本层有序链表的结束。
7）跳跃表拥有一个tail指针，指向跳跃表最后一个节点。
8）最底层的有序链表包含所有节点，最底层的节点个数为跳跃表的长度（length）（不包括头节点），图3-3中跳跃表的长度为7。
9）每个节点包含一个后退指针，头节点和第一个节点指向NULL；其他节点指向最底层的前一个节点。

跳跃表每个节点维护了多个指向其他节点的指针，所以在跳跃表进行查找、插入、删除操作时可以跳过一些节点，快速找到操作需要的节点。归根结底，跳跃表是以牺牲空间的形式来达到快速查找的目的。跳跃表与平衡树相比，实现方式更简单，只要熟悉有序链表，就可以轻松地掌握跳跃表。