跳跃表 skiplist

示意图

[h] ----[ ] ---------------------------------------------------> [N]
 |       |             (a)
[h] --> [ ] --> [ ] ----------> [ ] ---------------------------> [N]
 |  (a)   |       |               |
[h] --> [ ] --> [ ] --> [ ] --> [ ] ----------> [ ] -----------> [N]
 |       |       |       |       |               |
[h] --> [ ] --> [ ] --> [ ] --> [ ] ----------> [ ] ---> [ ] --> [N]      
         |       |       |       |               |        |   
        [1] <=> [3] <=> [5] <=> [7] <=> [9] <=> [10] <=> [11]

// h: header 头指针
// N: NIL
// a: 长度（跨越几个节点）
// 1 ~ 11: 节点分数

特征：

• 多级链表
• 最底层为双向有序链表
• n 层元素会有概率 p（0 < p < 1），出现在 n + 1 层

indexable skiplist

当指针包含当前节点与下一个节点间的距离属性时，被称为 indexable skiplist

应用

Redis zset

• 在 O(N) 内实现区间范围操作，如，zrange
• 通过 indexable skiplist 在 O(N) 内确定一个节点在链表中的位置，如，zrank

Others

• 通常 skiplist + dict 实现 zset
• dict 支持在 O（1）时间内，根据 key 查找 score

Reference & Thanks

• skip list