跳跃表

1. 跳跃表原理

1.1 设计动机

有序链表查找 $O(n)$，跳跃表通过多层索引将查找降至 $O(\log n)$：

Level 3:  1 ─────────────────────────── 50
Level 2:  1 ────────── 25 ──────────── 50
Level 1:  1 ──── 13 ── 25 ──── 38 ──── 50
Level 0:  1  7  13  19  25  31  38  44  50

1.2 概率平衡

不同于 AVL/红黑树的严格平衡，跳跃表通过随机抛硬币决定节点层数：

每个节点以概率 p=1/2 晋升到更高层
层数 k 的概率: P(k) = (1/2)^k

期望层数: E = 1/(1-p) = 2（p=1/2时）
最大层数: O(log n)

2. 数据结构

2.1 节点定义

import random

class SkipNode:
    def __init__(self, key=None, level=0):
        self.key = key
        self.forward = [None] * (level + 1)  # 各层前向指针

class SkipList:
    MAX_LEVEL = 16

    def __init__(self):
        self.header = SkipNode(level=self.MAX_LEVEL)
        self.level = 0  # 当前最大层数

    def random_level(self):
        lvl = 0
        while random.random() < 0.5 and lvl < self.MAX_LEVEL:
            lvl += 1
        return lvl

3. 核心操作

3.1 查找

def search(self, key):
    current = self.header
    for i in range(self.level, -1, -1):
        while current.forward[i] and current.forward[i].key < key:
            current = current.forward[i]
    current = current.forward[0]
    if current and current.key == key:
        return current
    return None

3.2 插入

def insert(self, key):
    update = [None] * (self.MAX_LEVEL + 1)
    current = self.header

    # 从最高层向下查找插入位置
    for i in range(self.level, -1, -1):
        while current.forward[i] and current.forward[i].key < key:
            current = current.forward[i]
        update[i] = current

    new_level = self.random_level()
    if new_level > self.level:
        for i in range(self.level + 1, new_level + 1):
            update[i] = self.header
        self.level = new_level

    new_node = SkipNode(key, new_level)
    for i in range(new_level + 1):
        new_node.forward[i] = update[i].forward[i]
        update[i].forward[i] = new_node

3.3 删除

def delete(self, key):
    update = [None] * (self.MAX_LEVEL + 1)
    current = self.header

    for i in range(self.level, -1, -1):
        while current.forward[i] and current.forward[i].key < key:
            current = current.forward[i]
        update[i] = current

    target = current.forward[0]
    if not target or target.key != key:
        return False

    for i in range(self.level + 1):
        if update[i].forward[i] != target:
            break
        update[i].forward[i] = target.forward[i]

    while self.level > 0 and self.header.forward[self.level] is None:
        self.level -= 1
    return True

4. 复杂度分析

5. 与平衡树对比

Redis 选择跳跃表的原因：实现简单、范围查询方便、并发友好。