LevelDB_02: 某科学的跳跃索引

Memtable 是 LSM-Tree 中的一个重要组件，它是一个驻留在内存中的数据结构，用于暂时存储写入的数据。当 MemTable 达到一定大小时，它会被转换成一个不可变的 SSTable，并写入磁盘。

因为 LevelDB 是 KV 存储引擎，显然的我们需要一个针对序集优化的结构

因此，选择一个高效的查找算法，就是在尽可能少的步骤内获取足够的信息，将系统的不确定性降为零。 元素之间不存在相关关系的情况下，遍历元素，此时相等的真值是

$P(true) = \frac {1} {N} \quad P(false) = \frac {N-1} {N}$

于是得到信息熵

$H_{step} = -\frac{1}{N} \log_2 \left(\frac{1}{N}\right) - \frac{N-1}{N} \log_2 \left(\frac{N-1}{N}\right)$

根据本法则由洛必达独家赞助播出的伯努利法则，当$N \to \infty$时，信息熵趋近于零。 真是可喜可贺呀。

既然每一次比对获得的信息量都无限趋近于零，那么如果我们用这套$O(N)$的方法来查找森林里的熊， 可能工程上最完美的$O(1)$优化方案，是直接让靠近遍历起点的兔子承认自己是 U. thibetanus。

当然，世界上没有人在乎被刑讯逼供的兔子，大家都只在乎自己的业务😢。

我们需要一种数据结构，来保卫我们的全序生活。

二叉树是一种和法兰西大革命一样，划分左右的结构。

在 0x06FD 年的二叉树上，对于任何一个作为基准的节点，比它小的元素统统去左子树（Left Child），比它大的元素统统去右子树（Right Child）。

难道你们不感觉，小的元素很像“无套裤汉”吗（笑）

在理想的黄金时代，如果数据是随机且均匀到达的，这棵树会生长得十分匀称。 每一次我们站在一个节点上进行比较，就如同站在历史的十字路口：向左走或向右走，都能稳稳抛弃掉另一半的异见分子。 我们完美地实现了前文所述的——单步榨取 $1 \text{ bit}$ 的信息量。

然而，就像大革命最终往往会滑向雅各宾派的极端专政一样，朴素的二叉搜索树也有一个致命的缺陷：它无法抵抗极端数据的输入。

在数据库的真实业务中，我们经常会遇到顺序写入的场景（比如自增主键、时间戳日志）。当数据以 1, 2, 3, 4, 5... 的递增顺序进入二叉树时，所有的元素都会不约而同地选择“向右走”。 于是，这棵本该枝繁叶茂的大树，绝望地向右无限延伸，最终退化成了一条单向链表。

你以为你在进行高贵的 $O(\log N)$ 二分查找，但实际上你单步获取的信息熵又跌回了那个悲惨的极限：

$\lim_{N \to \infty} H_{step} = 0 \text{ (bits)}$

最后我们可怜的保皇派，只能请普鲁士进来殴打兔子了。

They Might be Trees

这种时候我们不得不引入一种威权主义的结构，来尽量保证树是平衡的。

简单来说，自平衡二叉树会在每次插入或删除节点后，检查树的平衡状态，并通过旋转等操作来调整树的结构，确保它不会退化成链表。

另外的，随着我们进入 20 世纪，non-binary 的非二元树结构也开始流行起来。B-Tree 和 B+Tree 就是其中的代表，它们通过增加每个节点的子节点数量，来减少树的高度，从而进一步优化查找效率。

然而，这些树理论上非常好，因为其结构维稳机制过于复杂，每一次进行结构修改，都要求程序员进行一次 Sanity Check，大大降低了程序员的使用年限。

• Alice：我要在多线程环境下，对这个非二元的 B树 节点进行一次由于插入塞满而导致的节点分裂与向父节点提拔的操作。
• KP：好的。当你凝视着连环嵌套的父子指针、深不见底的递归调用，以及旁边虎视眈眈随时准备读写同一块内存的其他线程时，一种不可名状的恐怖攫住了你的心脏。请进行一次 理智检定，成功损失 1 点理智，失败损失 1d6 点。
• Alice：掷出 1d100 = 95！糟了，我的当前理智值只有 60，检定失败。
• KP：暗骰 1d6 = 5。你失去了 5 点理智值。由于单次理智损失达到 5 点，触发了对底层的凝视。请再进行一次 灵感检定。
• Alice：掷骰通过了……
• KP：很不幸。正因为你过人的智力，你彻底理解了如果在分裂时触发了 CPU 的指令重排，那个断裂的野指针究竟通向哪个虚空深渊。你陷入了 临时疯狂，症状为「躁狂/妄想」：接下来的 1d10 个小时内，你拒绝写任何树结构，并企图用暴力的全表扫描跑完所有业务。

Alice in Chains

为了保护大家的理智，我们需要一种更简单、更稳定的结构来替代那些复杂的树。

一个朴素的想法就是，我们给单链表加几个next指针。每隔 N 个元素，我们就设置 node[N] 的 next 指针，指向 node[2N]，直到某一层只有一个元素。

恭喜你，你刚刚发明了平衡二叉树

显然，这玩意对有序的要求和树是一样的，我们重新发明了一个二叉树。

绝对的秩序，必然伴随着高昂的维稳成本。 无论是树的旋转、B树的分裂，还是多重索引的等差重排，皆是如此。

就在多重索引即将被扫进历史垃圾堆时，1989 年，一位名叫 William Pugh 的天才计算机科学家，决定向宇宙中最伟大的自然法则借取力量——

显然 William 是个 DnD 玩家，他想要做的事情只有丢他的骰子了。

如果我们让node车卡的时候，投骰子决定有几层，会不会好起来？

William Pugh 的规则异常简单粗暴。当一个新节点进入系统时，它不需要看周边节点的眼色，不需要计算复杂的等差数列，更不需要像红黑树那样做极其复杂的“着色/旋转”检定。

它只需要做一件事：疯狂地过幸运检定。

规定投1d100要求$result \le 50$ 就算成功

1. 节点投出一次成功，它就为自己建一层向上的额外指针
2. 既然成功了，那就乘胜追击，继续投！
3. 如果再次成功，升入第 3 层！
4. 以此类推，直到某一次投出了失败，它的总层高就此固定。

为了纪念上文伯努利法则的弟弟，我们称每次这样的投骰为一次伯努利试验

$P(N = k) = (0.5)^k \quad \text{for } k \ge 1$

非常巧合的是，如果我们统计平衡二叉树的层高的概率分布，我们会发现它和这个伯努利试验的分布完全一样！

太伟大了大数定律！跳表就这样诞生了。

看看跳表节点的结构定义，相比于红黑树那堆充满威权气息的 left, right, color, parent，它简直朴实无华到了极点

pub fn SkipListNode(K: type, V: type) type {
    return struct {
        // 众生平等，只不过有些节点比其他节点更平等
        next: [16]?*SkipListNode(K, V),
        key: K,
        value: V,
    };
}

pub fn SkipList(K: type, V: type) type {
    return struct {
        const Self = @This();
        const Node = SkipListNode(K, V);

        head: *Node,
        rng: *std.Random.DefaultPrng,
        allocator: std.mem.Allocator,
        comparator: *const fn (a: K, b: K) bool,

        pub fn init(allocator: std.mem.Allocator, rng: *std.Random.DefaultPrng, comparator: *const fn (a: K, b: K) bool) !*Self {
            const list = try allocator.create(Self);
            const head = try allocator.create(Node);
            head.* = Node{ .next = [_]?*Node{null} ** 16, .key = undefined, .value = undefined };
            list.* = .{ .head = head, .rng = rng, .allocator = allocator, .comparator = comparator };
            return list;
        }

        pub fn deinit(self: *Self) void {
            var current: ?*Node = self.head;
            while (current) |node| {
                const next = node.next[0];
                self.allocator.destroy(node);
                current = next orelse null;
            }
            self.allocator.destroy(self);
        }
...

跳表的结构非常简单，每个节点都有一个固定大小的 next 数组，数组的长度等于跳表的最大层数 MaxLevel。每个元素都是一个可选的指针，指向同一层级的下一个节点。

跳表的查找过程就像在多层高速公路上行驶一样。我们从最高层开始，沿着 next 指针向前移动，直到找到一个节点的 next 指针指向的节点的 Key 大于目标 Key。 此时，我们就下降到下一层，继续这个过程，直到我们到达最底层。最终，我们要么找到了目标 Key，要么确定了它不存在。

跳表的平均层高是 $O(\log N)$，因为每个节点升层的概率是 0.5，所以大约每隔两层就会有一个节点。跳表的平均查找时间复杂度也是 $O(\log N)$，因为我们在每一层都能排除掉大约一半的节点。

所以我们的查找

pub fn find(self: *Self, key: K) ?*Node {
    var current = self.head;
    var level: i32 = 15;
    while (level >= 0) : (level -= 1) {
        while (current.next[@intCast(level)]) |next| {
            if (self.comparator(next.key, key)) {
                current = next;
            } else break;
        }
    }

    const target = current.next[0] orelse return null;
    if (!self.comparator(target.key, key) and !self.comparator(key, target.key)) {
        return target;
    }
    return null;
}

在这个 find 方法里，没有任何回溯，没有任何 Sanity Check。 我们乘坐直升机在第 15 层的高空巡视，一旦发现前方的基准点比目标大，立马毫不犹豫地拉绳索降（level -= 1），直到踩到坚实的第 0 层地面。 就是这么单向的、不可阻挡的降维打击，轻轻松松拿下了 $O(\log N)$。

插入时我们需要先找到合适的位置，然后按照前面描述的伯努利试验来决定新节点的层数。

pub fn insert(self: *Self, key: K, value: V) !void {
    // update 数组保存每一层插入点的前一个节点
    var update: [16]*Node = [_]*Node{self.head} ** 16;
    var current = self.head;

    var level: i32 = 15;
    while (level >= 0) : (level -= 1) {
        while (current.next[@intCast(level)]) |next| {
            if (self.comparator(next.key, key)) {
                current = next;
            } else break;
        }
        update[@intCast(level)] = current;
    }

    var new_level: usize = 0;
    while (new_level < 15 and self.rng.random().boolean()) {
        new_level += 1;
    }

    const new_node = try self.allocator.create(Node);
    new_node.* = Node{ .key = key, .value = value, .next = [_]?*Node{null} ** 16 };

    for (0..new_level + 1) |i| {
        new_node.next[i] = update[i].next[i];
        update[i].next[i] = new_node;
    }
}

没有复杂的平衡因子计算，不需要检查红黑着色。 大数定律在这一刻剥夺了算法的威权，把命运交给了 CPU 的热噪声。新节点能爬多高，全看 self.rng.random().boolean() 这一下造化。

然后，不出所料的，你就拥有了一个跳表，现在你可以在简历上写精通Redis和LevelDB了。