跳表

跳表

多层有序链表，每个节点以概率 p（通常 0.25）晋升到上一层。第 0 层是包含所有元素的基础链表，上层是几何级数稀疏的子集。

核心操作

1. 查找：从最高层左端出发；向右走直到超过目标，下移一层，重复直到第 0 层
2. 插入：在每一层找到插入位置；通过抛硬币确定最高层数；更新各层前向指针
3. 删除：在每一层找到节点；更新各层前向指针绕过该节点

复杂度

// Skip list with fixed seed for deterministic level assignment
// p = 0.5, maxLevel = 16
struct SkipNode {
    int key;
    vector<SkipNode*> forward;
    SkipNode(int k, int lvl) : key(k), forward(lvl, nullptr) {}
};

class SkipList {
    static const int MAXLVL = 16;
    SkipNode* head;
    int level;
    mt19937 rng{42};

    int randomLevel() {
        int lvl = 1;
        while (lvl < MAXLVL && (rng() & 1)) lvl++;
        return lvl;
    }
public:
    SkipList() : head(new SkipNode(INT_MIN, MAXLVL)), level(1) {}
    void insert(int key) {
        vector<SkipNode*> update(MAXLVL, head);
        SkipNode* cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur->forward[i] && cur->forward[i]->key < key)
                cur = cur->forward[i];
            update[i] = cur;
        }
        int newLvl = randomLevel();
        if (newLvl > level) {
            for (int i = level; i < newLvl; i++) update[i] = head;
            level = newLvl;
        }
        SkipNode* n = new SkipNode(key, newLvl);
        for (int i = 0; i < newLvl; i++) {
            n->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = n;
        }
    }
    bool search(int key) {
        SkipNode* cur = head;
        for (int i = level - 1; i >= 0; i--)
            while (cur->forward[i] && cur->forward[i]->key < key)
                cur = cur->forward[i];
        return cur->forward[0] && cur->forward[0]->key == key;
    }
    void remove(int key) {
        vector<SkipNode*> update(MAXLVL, head);
        SkipNode* cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur->forward[i] && cur->forward[i]->key < key)
                cur = cur->forward[i];
            update[i] = cur;
        }
        SkipNode* target = cur->forward[0];
        if (!target || target->key != key) return;
        for (int i = 0; i < level; i++) {
            if (update[i]->forward[i] != target) break;
            update[i]->forward[i] = target->forward[i];
        }
        delete target;
    }
};

对比其他有序结构

应用场景

• Redis 有序集合（ZSET）——跳表 + 哈希表，支持 O(log n) 排名查询
• Java ConcurrentSkipListMap / ConcurrentSkipListSet——无锁并发使用
• LevelDB MemTable——用跳表作为内存有序结构

概率均衡：p=0.25、maxLevel=32 时，期望层高 = log₄(n)。跳表不保证平衡，只是期望均衡。对于内存中的工作负载，这种方差完全可以接受。

Redis ZSET 范围查询

Redis 有序集合使用跳表支持范围查询（ZRANGEBYSCORE、ZRANGE BY RANK），同时维护哈希表实现 O(1) 分数查找（ZSCORE）。ZRANGEBYSCORE lo hi 时间复杂度为 O(log n + k)，k 为结果数。

Redis ZSET 命令

ZRANGEBYSCORE 实现

1. 从最高层向右找到第一个分数 >= lo 的节点
2. 在第 0 层向右遍历，收集所有分数 <= hi 的节点
3. 按升序分数返回收集到的成员

// Simplified ZSET: skip list ordered by score + hash map for O(1) score lookup
// Implements ZADD, ZSCORE, ZRANGEBYSCORE
struct ZNode {
    double score; string member;
    vector<ZNode*> forward;
    ZNode(double s, const string& m, int lvl) : score(s), member(m), forward(lvl, nullptr) {}
};

class ZSet {
    static const int MAXLVL = 16;
    ZNode* head;
    int level;
    unordered_map<string, double> scores; // member -> score
    mt19937 rng{42};

    int randomLevel() { int l=1; while(l<MAXLVL&&(rng()&1))l++; return l; }
    bool less(ZNode* a, double s, const string& m) {
        return a->score < s || (a->score == s && a->member < m);
    }
public:
    ZSet() : head(new ZNode(-1e18, "", MAXLVL)), level(1) {}
    void zadd(double score, const string& member) {
        if (scores.count(member)) { /* simplified: remove then re-insert */ }
        scores[member] = score;
        vector<ZNode*> upd(MAXLVL, head);
        ZNode* cur = head;
        for (int i = level-1; i >= 0; i--) {
            while (cur->forward[i] && less(cur->forward[i], score, member))
                cur = cur->forward[i];
            upd[i] = cur;
        }
        int lv = randomLevel();
        if (lv > level) { for(int i=level;i<lv;i++) upd[i]=head; level=lv; }
        ZNode* n = new ZNode(score, member, lv);
        for (int i = 0; i < lv; i++) { n->forward[i]=upd[i]->forward[i]; upd[i]->forward[i]=n; }
    }
    vector<pair<string,double>> zrangebyscore(double lo, double hi) {
        vector<pair<string,double>> res;
        ZNode* cur = head;
        for (int i = level-1; i >= 0; i--)
            while (cur->forward[i] && cur->forward[i]->score < lo)
                cur = cur->forward[i];
        cur = cur->forward[0];
        while (cur && cur->score <= hi) {
            res.push_back({cur->member, cur->score});
            cur = cur->forward[0];
        }
        return res;
    }
};

实际应用模式

• 排行榜：ZADD game:scores [score] [user]，ZRANGE game:scores 0 9 WITHSCORES REV
• 延迟任务队列：ZADD tasks [unix_timestamp] [task_id]，ZRANGEBYSCORE tasks 0 [now]
• 限流：ZADD key [timestamp] [request_id]，ZREMRANGEBYSCORE key 0 [cutoff]

ZSET 编码：当 ZSET 元素数量少（<=128）且成员字符串短（<=64字节）时，Redis 使用紧凑的 listpack（原 ziplist）存储。超过任一阈值后自动转换为跳表 + 哈希表。