Redis设实 - 04 跳跃表
《Redis设计与实现 黄建宏 著》第5章
该书基于Redis2.9，即Redis3.0开发版编写
跳跃表（skip list）
一种有序数据结构，通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的
支持平均O(logN)、最坏O(N)复杂度的节点查找
可通过顺序性操作批量处理节点
跳跃表数据结构
typedef structz skiplist{
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 节点的数量
unsigned long length;
// 层数最大的节点的层数，表头节点不计算在内
int level;
}zskiplist;
跳跃表节点数据结构
typedef struct zskiplistNode{
// 层
struct zskiplistLevel{
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
}level[];
// 后退指针
struct zskiplistNode *backward;
// 分值
double score;
//成员对象
robj *obj;
}zskiplistNode;
1. 层
层数量越多，访问其他节点的速度越快
创建新节点时，程序根据幂次定律（power law，越大的数出现的概率越小）随机生成1<=h<=32作为level数组大小，h就是层“高度”
2. 跨度
记录两节点间距离
节点间跨度越大，相距越远
指向NULL的前进指针的跨度为0
跨度实际上用来计算排位（rank）：查找某节点过程中，将沿途访问的所有层的跨度累加，得到的结果就是目标节点在跳跃表中的排位
3. 后退指针
后退时，每次只能后退至前一节点
4. 分值
所有节点都按分值从小到大排序
5. 成员对象
指向一个字符串对象，字符串对象则保存一个SDS值
同一个跳跃表中，各节点的成员对象必须唯一，但多个节点的分值可相同
分值相同的节点按照成员对象在字典序中的大小升序排序
例：
遍历过程
通过header访问第1个节点，然后依次访问跨度为1的前进节点，直到访问到NULL