Cavill's Blog
Go back

Implementing a Skip List from Scratch

Edit page

Table of contents

Open Table of contents

Intro

我第一次知道 Skip List 这种数据结构在学习 CMU 15-445 这门课程之后，在 Project 0 里要求实现一个 Skip List。完成之后才知道原来数据结构不只有那些在课堂里面讲的那些(e.g. linked list、stacks、queues、binary trees)，不过也可能是因为我一切靠自学，也许本科主修 CS 的知道？Anyway，我想这个数据结构对 coding 水平的提升还有 modern C++的理解都有相当的好处，所以我会在这篇 Blog 里面讲解如何从零开始实现一个 Skip List。Maybe 这会对你学习 CMU-15445 有帮助？我希望如此。不过现在这门课程在 26 年改成实现 Count-min sketch 了。
By the way，我非常推荐这门优质的 Database System 课程，Professor Andy Pavlo 很有个性，虽然没什么机会去现场上他的课程，但是在 youtube 或 bilibili 上面都有课程的视频。我想你看到这个视频的开头就会忍不住继续观看的：

同时，我也非常推荐去 课程主页 看看他们提供的资料和思路，我觉得是非常优质的内容。不同的是，我们会选择从零开始实现，而课程只是让你补足一部分模块。

what is Skip List?

简而言之，这是一种类似 Linked List 的数据结构，它常常与 Red-Black Tree 或 B+ Tree 来作比较。因为这几个数据结构在解决某些问题上可以提供相同的作用。你可以看 Why are skip lists not preferred over B+-trees for databases? 和 Skip List Data Structure: A Faster Alternative to Trees 这两篇 Blog 来了解相关信息。而我们选择实现 Skip List 的原因就在于：

  1. 这不属于最为常见的数据结构。
  2. 它的实现相对而言更简洁优雅。
  3. 并不那么容易实现

基于上述特征，我觉得它非常适合作为学习的内容。所以，让我们开始设计这种数据结构吧！

To DESCRIBE the structure of Skip List

国内很多大学在学习数据结构的时候，常常上来就是讲解代码。我觉得这个问题是挺严重的，因为数据结构首先是一种结构，认识一种结构的关键还是要先勾勒出它具体的样子。否则通过高度抽象的代码很难在大脑里面描摹具体的 structure。

Skip List structure
Figure 1,link:https://15445.courses.cs.cmu.edu/spring2025/project0/

我们可以定义出 Node 的结构：

struct Node {
    Node(std::size_t level, const Key& key, const Value& value)
        : key(key), value(value), forward(level, nullptr) {}

    Key key;                    // 当前节点保存的 key
    Value value;                // 对应的数据

    std::vector<Node*> forward; // 不同层的后继指针
};

Node 是 Skip List 的基本组成单元。我们可以看 Key 为 6 的这个 Node，它的 forward 数组里存放了 4 个元素：

节点拥有的 forward 元素数量决定了这个节点的最高层数。
于此同时，我们可以发现出现了一个新的变量 Level。从而我们知道，仅仅定义 Node 并不足以实现这个数据结构应该要有的功能，我们还需要维护一些全局的状态变量。

std::size_t maxLevel_;
double probability_;
Node* head_;
std::size_t level_;
std::size_t size_ = 0;
Compare comp_;
mutable std::mt19937 rng_;
mutable std::uniform_real_distribution<double> distribution_;
Figure 2

这张图并没有完整展示 Node，因为一个节点既有 Key 也有 Value。但是因为我们查询遍历的时候主要依据是 Key，所以我们没有画出 Value。

Operations on Skip List

在有了直观的认知之后，我们会实现一个数据结构最基本的几个操作。

我们基于 Figure 2 展示的这个 Skip List 形态开始。那么我在实现数据结构操作的时候，一般会先区分实现成功或者失败的状态。
在这里，我们认为成功就是找到了我们需要 Key 值的节点，返回这个节点的地址，也就是一个指针。如果没有找到，则返回 nullptr。
根据我们的设想，我们可以写出这个函数的框架：

[[nodiscard]] Node* findNode(const Key& key) const {
        {
            kind of search operation...
        }
        return nullptr;
    }

然后我们会往里面补充具体操作，我们之前提到过 Skip List 是一种类似 Linked List 的数据结构，而在 Linked List 里面如需便利，我们会引入一个 current 指针，在这里也是一样。
Again，我们是基于 Figure 2 的状态进行讲解。所以此时：

我们会让 current 指针指向这个 Sentinel Node，即 Node* current = head_;。
假定我们传入的 Key 为 9，那么我们需要经历如下过程：
我们会让 current 自上而下，依次指向 forward 数组保存的元素。通过判断这个这个元素是否为 nullptr 以及元素的 Key 值是否小于要寻找的值来判断 current 是否需要移动，最终我们会得到一个小于目标 Key 的最大节点。此时，我们并没有直接找到目标节点，而是定位到了它应该出现的位置。因此，只需要访问 current->forward[0]，检查下一个节点的 Key 是否与目标 Key 相等即可。

[[nodiscard]] Node* findNode(const Key& key) const {
    Node* current = head_;
    for (std::size_t i = level_; i > 0; --i) {
        while (current->forward[i - 1] != nullptr &&
                comp_(current->forward[i - 1]->key, key)) {
            current = current->forward[i - 1];
        }
    }

    current = current->forward[0];
    // 我们会在之前实现这个isEqual函数。
    if (current != nullptr && isEqual(current->key, key)) {
      return current;
    }
    return nullptr;
}

这样，我们就成功实现了 Search 功能。

跳表搜索中 current 的移动过程

跳表搜索中 current 的移动过程XHead3679121719212526NILi = 5current
for (std::size_t i = level_; i > 0; --i) {while (current->forward[i - 1] != nullptr && comp_(current->forward[i - 1]->key, key)) {current = current->forward[i -1];}}current = current->forward[0];if (current !=nullptr &&isEqual(current->key, key)) {return current;}

条件不成立：current 保持不动（head 的 forward[4] 是 nullptr）。

Insert

上一节中，我们已经了解了如何在 Skip List 中查找一个节点。接下来，我们将实现插入操作。
与普通链表不同，Skip List 的插入不仅需要修改底层链表，还需要维护更高层的索引结构。因此，插入操作主要包含两个步骤：

  1. 找到新节点在每一层中的插入位置；
  2. 随机决定新节点的高度，并更新对应层的 forward 指针。

在第一步中，我们可以复用 Search 的思想，通过从最高层开始向下搜索，找到每一层中位于新节点之前的节点。不同的是，这一次我们不仅需要找到位置，还需要保存这些前驱节点，因为后续插入时需要修改它们的指针。
在实现第二步之前，我们需要先实现一个随机层数生成函数。Skip List 的核心思想之一就是通过随机化决定节点的高度，从而使整个数据结构在概率意义上保持平衡。
在 C++ 中，我们可以使用标准库提供的 std::mt19937 和 std::uniform_real_distribution，不需要自己造轮子。

第一步

由于已经知道如何实现 Search，我们就可以选择复用写过的代码。

bool insert(const Key& key, const Value& value) {
        std::vector<Node*> update(maxLevel_, nullptr);
        Node* current = head_;

        for (std::size_t i = level_; i > 0; --i) {
            while (current->forward[i - 1] != nullptr &&
                   comp_(current->forward[i - 1]->key, key)) {
                current = current->forward[i - 1];
            }
            update[i - 1] = current;
        }

        current = current->forward[0];
        if (current != nullptr && isEqual(current->key, key)) {
            current->value = value;
            return false;
        }

这部分代码与 Search 的过程非常相似。不同之处在于，我们额外维护了一个 update 数组，用于记录每一层中位于目标位置之前的节点。
这是因为插入操作不仅需要找到新节点的位置，还需要知道后续应该修改哪些节点的 forward 指针。

Tip

current = current->forward[0]; 这一行代码，在这里的作用不同于 Search，它将 current 指针移动到下一层的节点。也就是将 current 指向大于目标 Key 值的最小节点。

不过，到这里我们实际上还没有真正执行插入操作。搜索完成后，我们首先需要检查目标 Key 是否已经存在。
如果后继节点的 Key 与待插入的 Key 相等，由于本实现不允许重复 Key 出现，我们会直接更新后继节点的 value，并返回 false，表示插入操作未成功，因为该 Key 已经存在。

第二步

如果目标 Key 不存在，那么我们就可以正式创建新的节点。
首先，需要决定新节点的高度。由于 Skip List 使用随机化决定节点层数，新节点可能拥有比当前 Skip List 更高的层级。

const std::size_t newLevel = randomLevel();
        if (newLevel > level_) {
            for (std::size_t i = level_; i < newLevel; ++i) {
                update[i] = head_;
            }
            level_ = newLevel;
        }

        Node* newNode = new Node(newLevel, key, value);
        for (std::size_t i = 0; i < newLevel; ++i) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }

        ++size_;
        return true;
    }

我们仍通过 Figure 2 来理解这个过程。假设我们要插入的节点的 Key 为 10，並且随机生成的层数为 3。我们会在 update 数组里面存入这样一组数据：

又因为我们的层数并没有超过原来的层数(level = 5)，所以我们直接进入：

    Node* newNode = new Node(newLevel, key, value);
    for (std::size_t i = 0; i < newLevel; ++i) {
        newNode->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = newNode;
    }      
    ++size_;
    return true;

这段代码非常类似于链表的插入操作。我们首先将新节点的 forward 指针指向大于目标 Key 值的最小节点。然后将前驱节点的 forward 指针更新为指向新节点。这样，新节点就被成功插入到 Skip List 中。

因为这种操作是类似的，因此我只展示当 i=0 时的情况：

实际上是Key=9的节点的forward[0]指向Key=10的节点

之后的循环情况都可以以此类推。最后增加节点个数，并返回 True，整个插入过程就结束了。

Erase

Erase 操作与 Insert 操作恰好相反，找到前驱节点后，我们需要 forward 直接跳过目标节点，并指向目标节点的后继节点。这样就完成了删除操作。

bool erase(const Key& key) {
        std::vector<Node*> update(maxLevel_, nullptr);
        Node* current = head_;

        for (std::size_t i = level_; i > 0; --i) {
            while (current->forward[i - 1] != nullptr &&
                   comp_(current->forward[i - 1]->key, key)) {
                current = current->forward[i - 1];
            }
            update[i - 1] = current;
        }

        current = current->forward[0];
        if (current == nullptr || !isEqual(current->key, key)) {
            return false;
        }

        for (std::size_t i = 0; i < level_; ++i) {
            if (update[i]->forward[i] != current) {
                break;
            }
            update[i]->forward[i] = current->forward[i];
        }

        delete current;
        --size_;

        while (level_ > 1 && head_->forward[level_ - 1] == nullptr) {
            --level_;
        }

        return true;
    }

我想看懂了 insert,erase 的实现应该是非常容易理解的。我们同样会维护一个 update 数组，记录每一层中位于目标节点之前的节点。然后，我们检查目标节点是否存在，如果存在，就将前驱节点的 forward 指针直接跳过目标节点，指向目标节点的后继节点。最后，我们删除目标节点，并更新 Skip List 的层数和大小。因此在这里不再赘述。

Initialization

在实现了基本的操作之后，我们还需要对整个 Skip List 进行初始化。初始化主要包括设置最大层数、概率因子、创建头节点以及初始化随机数生成器。好在，我们已经把最困难的部分解决了。而剩下的这些内容显然不是我们的重点，所以我把实现的内容放在了这个 repository 里面，你可以直接去看源码。

Hope this Helps!

Footnotes

  1. 图中的 NIL，我猜想是为了致敬提出 Skip List 的原始论文：Skip Lists: A Probabilistic Alternative to Balanced Trees ↩

Edit page
Share this post:
Share this post on WhatsappShare this post on FacebookShare this post on XShare this post on TelegramShare this post on PinterestShare this post via email
Previous Post
Chasing the Golden Snitch
Next Post
Monty Hall problem