跳表核心机制

跳表（Skip List）是一种概率性平衡的数据结构，通过在有序链表上建立多级索引，将线性查找的时间复杂度从 O(N) 优化至 O(log N)。其核心创新在于用随机化策略替代传统平衡树的复杂旋转操作，以空间换时间的方式实现高效的范围查询与顺序遍历。

分层索引的查询原理

跳表的查询过程采用"自上而下、自左而右"的搜索策略。以查找目标值 23 为例：

1. 从顶层索引出发，比较当前节点与后继节点的键值
2. 若后继节点值小于目标，则向右移动（跳过不可能包含结果的区间）
3. 若后继节点值大于目标，则下降一层（缩小搜索范围至当前区间）
4. 重复上述过程直至底层，确定目标是否存在

这种策略确保每次比较都能排除大量无效数据，形成类似二分查找的剪枝效果。

随机层级的生成策略

为避免插入删除导致结构退化，跳表采用概率控制节点高度。设晋升概率为 p，节点高度为 k 的概率为 p^(k-1)·(1-p)。Redis 采用 p=0.25、最大层数 64（新版为 32）的配置：

int generateLevel() {
    int lvl = 1;
    // 使用位运算优化随机数生成
    while ((random() & 0xFFFF) < (0xFFFF * _prob)) {
        ++lvl;
        if (lvl >= _maxHeight) break;
    }
    return lvl;
}

当 p=0.25 时，平均每个节点携带 1.33 个指针；p=0.5 时则为 2 个指针。较低的概率系数显著降低内存开销，同时保持对数级查询效率。

完整工程实现

template<typename K, typename V>
struct IndexNode {
    K key;
    V value;
    std::vector<IndexNode*> forward;
    IndexNode(K k, V v, int height) 
        : key(k), value(v), forward(height, nullptr) {}
};

template<typename K, typename V>
class SkipListMap {
    using Node = IndexNode<K, V>;
    Node* sentinel;
    double _prob = 0.25;
    int _maxHeight = 32;
    int _curHeight = 1;
    
    int randomHeight() {
        int h = 1;
        while (h < _maxHeight && (double)rand() / RAND_MAX < _prob) 
            ++h;
        return h;
    }
    
    std::vector<Node*> findPredecessors(const K& target) {
        std::vector<Node*> update(_curHeight);
        Node* curr = sentinel;
        for (int lvl = _curHeight - 1; lvl >= 0; --lvl) {
            while (curr->forward[lvl] && curr->forward[lvl]->key < target)
                curr = curr->forward[lvl];
            update[lvl] = curr;
        }
        return update;
    }
    
public:
    SkipListMap() {
        srand(time(nullptr));
        sentinel = new Node(K(), V(), 1);
    }
    
    bool contains(const K& key) {
        Node* curr = sentinel;
        for (int lvl = _curHeight - 1; lvl >= 0; --lvl) {
            while (curr->forward[lvl] && curr->forward[lvl]->key < key)
                curr = curr->forward[lvl];
        }
        return curr->forward[0] && curr->forward[0]->key == key;
    }
    
    void insert(const K& key, const V& val) {
        auto prev = findPredecessors(key);
        if (prev[0]->forward[0] && prev[0]->forward[0]->key == key) {
            prev[0]->forward[0]->value = val;
            return;
        }
        
        int newHeight = randomHeight();
        if (newHeight > _curHeight) {
            prev.resize(newHeight, sentinel);
            sentinel->forward.resize(newHeight, nullptr);
            _curHeight = newHeight;
        }
        
        Node* newbie = new Node(key, val, newHeight);
        for (int i = 0; i < newHeight; ++i) {
            newbie->forward[i] = prev[i]->forward[i];
            prev[i]->forward[i] = newbie;
        }
    }
    
    bool remove(const K& key) {
        auto prev = findPredecessors(key);
        Node* victim = prev[0]->forward[0];
        if (!victim || victim->key != key) return false;
        
        int victimHeight = victim->forward.size();
        for (int i = 0; i < victimHeight; ++i)
            prev[i]->forward[i] = victim->forward[i];
        
        delete victim;
        while (_curHeight > 1 && !sentinel->forward[_curHeight - 1])
            --_curHeight;
        return true;
    }
    
    // 范围查询：获取 [low, high] 区间内所有元素
    std::vector<std::pair<K,V>> rangeQuery(const K& low, const K& high) {
        std::vector<std::pair<K,V>> result;
        Node* curr = sentinel->forward[0];
        while (curr && curr->key < low) curr = curr->forward[0];
        while (curr && curr->key <= high) {
            result.emplace_back(curr->key, curr->value);
            curr = curr->forward[0];
        }
        return result;
    }
};

Redis 选型决策分析

Redis 选择跳表作为 ZSet 底层结构，核心考量在于：范围查询是 sorted set 的核心操作，跳表在此场景下代码简洁且性能优异；同时其实现比红黑树减少约 50% 的指针存储，在内存敏感的数据库场景中具有显著优势。