建站公司排名 中企动力利尔化学股票最新消息
SkipList
ZipList和QuickList的共同特点是节省内存。在遍历元素时，只能从头到尾或从尾到头，所以在查找头尾元素性能还是不错的，但是中间元素查询的性能就会差。
**SkipList（跳表）**首先是链表，但与传统链表相比有几点差异：
- 元素按照升序排列存储
- 节点可能包含多个指针，指针跨度不同
// t_zset.c
typedef struct zskiplist {// 头尾节点指针struct zskiplistNode *header, *tail;// 节点数量unsigned long length;// 最大的索引层级，默认是1int level;
} zskiplist;
// t_zset.c
typedef struct zskiplistNode {sds ele; // 节点存储的值double score;// 节点分数，排序、查找用struct zskiplistNode *backward; // 前一个节点指针struct zskiplistLevel {struct zskiplistNode *forward; // 下一个节点指针unsigned long span; // 索引跨度} level[]; // 多级索引数组
} zskiplistNode;
一级指针：
二级指针：
三级指针：
SkipList的特点：
- 跳跃表是一个双向链表，每个节点都包含score和ele值
- 节点按照score值排序升序，score值一样则按照ele字典排序
- 每个节点都可以包含多层指针，层数是1到32之间的随机数
- 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
- 增删改查效率与红黑树基本一致，实现却更简单