各位技术同仁，大家好！
今天，我们将深入探讨一个在高性能索引构建中，常常被低估但极其强大的数据结构——跳表（SkipList）。在我们的日常工作中，谈及高性能索引，脑海中首先浮现的往往是哈希表或各种平衡树，如红黑树、AVL树。它们无疑是久经考验的基石，但今天我将向大家展示，跳表如何在某些关键场景下，以其独特的优势，成为平衡树的有力替代者，尤其是在内存与速度的权衡，以及并发性能方面。
第一章：索引的基石与挑战——为何我们需要平衡树？
在讨论跳表之前，我们必须先理解索引的本质及其所面临的挑战。索引的根本目的是加速数据检索。在一个没有索引的数据库或内存数据结构中，查找特定数据项通常需要线性扫描，其时间复杂度为 O(N)，这对于大规模数据集来说是不可接受的。
为了实现 O(log N) 甚至 O(1) 的检索速度，我们引入了各种索引结构：
- 哈希表 (Hash Table):
- 优点: 平均
O(1)的查找、插入、删除速度。 - 缺点: 不支持范围查询（例如，查找所有大于X且小于Y的元素），哈希冲突处理复杂，需要良好的哈希函数，且内存利用率可能不稳定。
- 优点: 平均
- 平衡二叉搜索树 (Balanced Binary Search Trees):
- 代表: AVL树、红黑树 (Red-Black Tree)。
- 优点:
O(log N)的查找、插入、删除速度，支持范围查询，元素有序存储。 - 缺点: 实现复杂，内存开销相对较大，并发控制复杂。
在需要有序存储和范围查询的场景中，平衡二叉搜索树是不可或缺的。它们通过在每次插入或删除操作后，自动调整树的结构（旋转、颜色翻转等），来确保树的高度始终保持在对数级别，从而保证了 O(log N) 的最坏时间复杂度。
然而，正是这种“平衡”机制，引入了显著的复杂性。无论是AVL树的严格高度平衡，还是红黑树的颜色属性平衡，其内部操作都涉及精巧的逻辑判断和多指针的更新。这不仅增加了实现的难度，也使得并发环境下的正确性保证变得异常困难。每次修改都可能牵动树的多个节点，需要复杂的锁策略来维护数据一致性，这往往会成为并发性能的瓶颈。
第二章：深入剖析平衡树——以红黑树为例
红黑树是自平衡二叉搜索树的一种，在许多标准库和操作系统内核中都有广泛应用（例如C++ STL的 std::map 和 std::set，Linux内核的进程调度器）。它通过为每个节点引入“颜色”属性（红或黑），并遵循一系列规则来维持树的平衡。
红黑树的五条性质：
- 每个节点是红色或黑色。
- 根节点是黑色。
- 所有叶子节点（NIL节点）是黑色。
- 如果一个节点是红色，则它的子节点必须是黑色。
- 从任意节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。
这些性质确保了从根到叶子的最长路径不会超过最短路径的两倍，从而保证了树的高度是 O(log N)。
红黑树节点结构（概念性）：
template <typename Key, typename Value>
struct RedBlackTreeNode {
Key key;
Value value;
RedBlackTreeNode* left;
RedBlackTreeNode* right;
RedBlackTreeNode* parent; // 通常需要父指针
enum Color { RED, BLACK } color;
RedBlackTreeNode(Key k, Value v, Color c = RED,
RedBlackTreeNode* p = nullptr,
RedBlackTreeNode* l = nullptr,
RedBlackTreeNode* r = nullptr)
: key(k), value(v), color(c), parent(p), left(l), right(r) {}
};操作复杂度：
- 查找 (Search): 从根节点开始，根据键值大小向下遍历。平均和最坏情况都是
O(log N)。 - 插入 (Insert):
- 像普通二叉搜索树一样插入新节点，通常初始化为红色。
- 如果插入破坏了红黑树的性质（主要是性质4：红色节点不能有红色子节点），则需要进行一系列的修复操作：颜色翻转和树旋转。这些操作可能需要递归或迭代地向上调整。
- 平均和最坏情况都是
O(log N)。
- 平均和最坏情况都是
- 删除 (Delete):
- 找到要删除的节点。
- 如果节点有两个子节点，找到其后继节点，用后继节点的值替换待删除节点的值，然后删除后继节点（这简化了删除只有0或1个子节点的场景）。
- 删除节点后，如果破坏了红黑树的性质，同样需要复杂的颜色翻转和树旋转来恢复平衡。
- 平均和最坏情况都是
O(log N)。
- 平均和最坏情况都是
红黑树的优缺点总结：
| 特性 | 红黑树 优点: 平衡性保证了 O(log N) 的查找、插入、删除，且实现相对红黑树更简单。
- 缺点: 频繁的旋转操作可能导致较高的时间常数开销。
在某些场景下，平衡树的这些“缺点”并非致命，标准库中经过高度优化的实现通常能提供优秀的性能。然而，在需要构建自己定制化索引，特别是在高并发、低延迟的内存数据库或缓存系统中，平衡树的复杂性就凸显出来。
第三章：跳表登场——概率性平衡的优雅
现在，让我们把目光投向今天的主角——跳表 (SkipList)。跳表是由 William Pugh 在 1990 年提出的一种概率性数据结构，它通过引入多层索引来加速对有序链表的查找。
跳表的核心思想：
想象一下一个普通的有序链表，查找一个元素需要 O(N) 时间。如果我们在这条链表之上再构建一层“高速公路”，这条高速公路只包含原链表中的一部分元素，并且也是有序的。那么，我们就可以先在高速公路上快速定位到一个大致的范围，然后再下降到原始链表进行精确查找。跳表正是将这种思想推广到多层。
跳表的基本结构：
一个跳表由多个层级的有序链表组成。最底层（Level 0）包含所有元素，并且是一个完整的有序链表。每一层 i 的元素都是其下一层 i-1 元素的子集，并且也是有序的。一个元素是否被提升到上一层，是根据一个随机概率 p 来决定的。例如，如果 p=0.5，那么一个节点有50%的概率出现在Level 1，有25%的概率出现在Level 2，以此类推。
跳表节点结构：
与平衡树不同，跳表节点不需要存储父指针，也不需要颜色属性。它只需要一个键值对，以及一个指向多个下一层节点的指针数组。
#include <iostream>
#include <vector>
#include <string>
#include <random> // For random_level()
#include <limits> // For numeric_limits
#include <algorithm> // For std::max
// 定义最大层数
const int MAX_LEVEL = 32; // 经验值，对于N=2^32的元素，log2(N)大约是32
const double P_FACTOR = 0.25; // 概率因子，通常0.25或0.5
// 跳表节点
template <typename Key, typename Value>
struct SkipListNode {
Key key;
Value value;
// forward[i] 指向当前节点在 level i 的下一个节点
std::vector<SkipListNode<Key, Value>*> forward;
SkipListNode(Key k, Value v, int level)
: key(k), value(v) {
forward.resize(level + 1, nullptr); // 初始化为nullptr
}
// 哨兵节点构造函数，用于头部节点，其key和value不重要
SkipListNode(int level)
: key(Key()), value(Value()) { // 默认构造Key和Value
forward.resize(level + 1, nullptr);
}
};
// 跳表类
template <typename Key, typename Value, typename Comparator = std::less<Key>>
class SkipList {
private:
using Node = SkipListNode<Key, Value>;
Node* header; // 头部哨兵节点
int level; // 当前跳表的最大层数 (0-indexed)
std::mt19937_64 rng; // 随机数生成器
std::uniform_real_distribution<double> dist; // 均匀分布
Comparator comp; // 键比较器
// 随机生成新节点的层数
int random_level() {
int lvl = 0;
// 循环直到达到最大层数或随机数不满足概率条件
while (lvl < MAX_LEVEL - 1 && dist(rng) < P_FACTOR) {
lvl++;
}
return lvl;
}
public:
SkipList() : level(0), rng(std::random_device{}()), dist(0.0, 1.0) {
// header节点包含最大的可能整数键，确保所有实际键都小于它
// 或者，更常见的是使用一个虚拟的最小键来作为哨兵节点
// 这里为了简化，我们使用一个虚拟的key和value，不参与比较
header = new Node(MAX_LEVEL - 1); // header节点应有MAX_LEVEL-1层
}
~SkipList() {
Node* current = header->forward[0];
while (current != nullptr) {
Node* next = current->forward[0];
delete current;
current = next;
}
delete header;
}
// 查找操作
Value* search(const Key& searchKey) const {
Node* current = header;
// 从最高层开始向下查找
for (int i = level; i >= 0; --i) {
// 在当前层向右移动，直到找到一个键大于或等于 searchKey 的节点
// 或者到达当前层的末尾
while (current->forward[i] != nullptr && comp(current->forward[i]->key, searchKey)) {
current = current->forward[i];
}
}
// 到达最底层 (level 0)
current = current->forward[0];
// 检查找到的节点是否是我们要找的键
if (current != nullptr && !comp(current->key, searchKey) && !comp(searchKey, current->key)) {
return &(current->value); // 找到
} else {
return nullptr; // 未找到
}
}
// 插入操作
void insert(const Key& newKey, const Value& newValue) {
// update 数组用于存储在每个层级上，新节点应该插入到哪个节点之后
std::vector<Node*> update(MAX_LEVEL);
Node* current = header;
// 1. 查找插入位置，并填充 update 数组
for (int i = level; i >= 0; --i) {
while (current->forward[i] != nullptr && comp(current->forward[i]->key, newKey)) {
current = current->forward[i];
}
update[i] = current; // 记录当前层级的插入点
}
// 2. 检查键是否已存在
current = current->forward[0];
if (current != nullptr && !comp(current->key, newKey) && !comp(newKey, current->key)) {
// 键已存在，更新值并返回
current->value = newValue;
return;
}
// 3. 生成新节点的随机层数
int newLevel = random_level();
// 4. 如果新节点的层数高于当前跳表的最大层数，更新 header 的 forward 指针
// 并且 update 数组中超出当前 level 的部分，应该指向 header
if (newLevel > level) {
for (int i = level + 1; i <= newLevel; ++i) {
update[i] = header;
}
level = newLevel; // 更新跳表的当前最大层数
}
// 5. 创建新节点
Node* newNode = new Node(newKey, newValue, newLevel);
// 6. 调整指针，将新节点插入到各个层级中
for (int i = 0; i <= newLevel; ++i) {
newNode->forward[i] = update[i]->forward[i];
update[i]->forward[i] = newNode;
}
}
// 删除操作
bool erase(const Key& deleteKey) {
std::vector<Node*> update(MAX_LEVEL);
Node* current = header;
// 1. 查找要删除的节点，并填充 update 数组
for (int i = level; i >= 0; --i) {
while (current->forward[i] != nullptr && comp(current->forward[i]->key, deleteKey)) {
current = current->forward[i];
}
update[i] = current;
}
// 2. 检查要删除的键是否存在
current = current->forward[0];
if (current == nullptr || comp(current->key, deleteKey) || comp(deleteKey, current->key)) {
return false; // 未找到要删除的键
}
// 3. 调整指针，从各个层级中删除节点
for (int i = 0; i <= level; ++i) {
if (update[i]->forward[i] == current) { // 如果当前层的下一个节点是要删除的节点
update[i]->forward[i] = current->forward[i]; // 跳过当前节点
}
}
// 4. 删除节点
delete current;
// 5. 更新跳表的当前最大层数 (如果最高层变空了)
while (level > 0 && header->forward[level] == nullptr) {
level--;
}
return true;
}
// 打印跳表 (仅用于调试)
void print() const {
std::cout << "SkipList (Current Max Level: " << level << ")" << std::endl;
for (int i = level; i >= 0; --i) {
std::cout << "Level " << i << ": ";
Node* node = header->forward[i];
while (node != nullptr) {
std::cout << "(" << node->key << ", " << node->value << ") -> ";
node = node->forward[i];
}
std::cout << "nullptr" << std::endl;
}
std::cout << "--------------------" << std::endl;
}
// 范围查询（例如，获取所有键在 [startKey, endKey] 之间的元素）
std::vector<std::pair<Key, Value>> range_query(const Key& startKey, const Key& endKey) const {
std::vector<std::pair<Key, Value>> results;
Node* current = header;
// 定位到第一个大于或等于 startKey 的节点
for (int i = level; i >= 0; --i) {
while (current->forward[i] != nullptr && comp(current->forward[i]->key, startKey)) {
current = current->forward[i];
}
}
current = current->forward[0]; // 移动到 Level 0
// 遍历 Level 0，收集符合范围的元素
while (current != nullptr && !comp(endKey, current->key)) { // current->key <= endKey
if (!comp(current->key, startKey)) { // current->key >= startKey
results.push_back({current->key, current->value});
}
current = current->forward[0];
}
return results;
}
// 检查跳表是否为空
bool empty() const {
return header->forward[0] == nullptr;
}
// 获取跳表大小 (需要遍历，O(N)操作)
size_t size() const {
size_t count = 0;
Node* current = header->forward[0];
while (current != nullptr) {
count++;
current = current->forward[0];
}
return count;
}
};
// 示例用法
int main() {
SkipList<int, std::string> sl;
std::cout << "Inserting elements:" << std::endl;
sl.insert(10, "Apple");
sl.insert(20, "Banana");
sl.insert(5, "Cherry");
sl.insert(15, "Date");
sl.insert(25, "Elderberry");
sl.insert(7, "Fig");
sl.insert(12, "Grape");
sl.print();
std::cout << "Searching for 15: " << (sl.search(15) ? *sl.search(15) : "Not found") << std::endl;
std::cout << "Searching for 100: " << (sl.search(100) ? *sl.search(100) : "Not found") << std::endl;
std::cout << "nRange query [7, 20]:" << std::endl;
std::vector<std::pair<int, std::string>> range_res = sl.range_query(7, 20);
for (const auto& p : range_res) {
std::cout << "(" << p.first << ", " << p.second << ") ";
}
std::cout << std::endl;
std::cout << "nDeleting 15:" << std::endl;
sl.erase(15);
sl.print();
std::cout << "Searching for 15 after deletion: " << (sl.search(15) ? *sl.search(15) : "Not found") << std::endl;
std::cout << "nDeleting 5:" << std::endl;
sl.erase(5);
sl.print();
std::cout << "nInserting 10 (update existing):" << std::endl;
sl.insert(10, "New Apple");
sl.print();
std::cout << "Current size: " << sl.size() << std::endl;
return 0;
}跳表的操作原理：
-
查找 (Search):
- 从最高层（
level变量所指示的层）的header节点开始。 - 在当前层，沿着
forward指针向右移动，直到找到一个节点的键值大于或等于searchKey，或者到达当前层的末尾。 - 如果当前节点的下一个节点键值大于
searchKey，或者下一个节点是nullptr，则下降一层，继续查找。 - 重复此过程，直到下降到最底层 (Level 0)。
- 在 Level 0，当前节点的下一个节点就是我们要找的节点（如果存在且键值匹配）。
- 平均时间复杂度为
O(log N)。
- 从最高层（
-
插入 (Insert):
- 首先执行与查找类似的过程，找到新节点在每一层应该插入的位置。这些位置被记录在一个
update数组中。update[i]存储的是在 Leveli上，新节点应该插入到update[i]之后。 - 检查
update[0]->forward[0]是否与新键相同。如果相同，则表示键已存在，更新其值即可。 - 如果键不存在，通过
random_level()函数随机确定新节点的层数newLevel。 - 如果
newLevel大于当前跳表的level，则更新跳表的level，并将update数组中超出原level的部分指向header节点。 - 创建一个新节点。
- 遍历
0到newLevel，调整update[i]的forward[i]指针，使其指向新节点，并将新节点的forward[i]指向原update[i]->forward[i]。 - 平均时间复杂度为
O(log N)。
- 首先执行与查找类似的过程，找到新节点在每一层应该插入的位置。这些位置被记录在一个
-
删除 (Delete):
- 同样，先执行与查找类似的过程，找到要删除的节点在每一层的前驱节点，并记录在
update数组中。 - 检查
update[0]->forward[0]是否是要删除的节点。如果不是，则表示键不存在，返回false。 - 遍历
0到level，对于每一层i，如果update[i]->forward[i]指向要删除的节点，则将其更新为要删除节点的forward[i]，从而“跳过”该节点。 - 释放被删除节点的内存。
- 最后，检查是否需要降低跳表的
level。如果最高层的header->forward[level]变为空，则降低level。 - 平均时间复杂度为
O(log N)。
- 同样，先执行与查找类似的过程，找到要删除的节点在每一层的前驱节点，并记录在
随机层数生成：
random_level() 函数是跳表的灵魂。它决定了每个新节点能被提升到多高的层级。通常，我们设置一个概率 p（例如0.25或0.5）。每次抛硬币，如果正面朝上，就提升一层。
// 示例 random_level() 实现
int random_level() {
int lvl = 0;
while (lvl < MAX_LEVEL - 1 && dist(rng) < P_FACTOR) {
lvl++;
}
return lvl;
}这个概率 P_FACTOR 对跳表的性能和内存使用有重要影响。
p越大，节点提升的概率越高，跳表层数越高，查找速度理论上更快，但内存开销也越大。p越小，跳表层数越低，内存开销越小，但查找速度可能变慢。
通常，p=0.25是一个经验值，它能提供良好的平衡。
第四章：内存与速度的权衡——跳表 vs. 平衡树
现在，让我们来深入比较跳表和平衡树在内存和速度方面的权衡。
1. 内存使用分析
| 特性 | 平衡树 (如红黑树) | 优点 | 查找、插入、删除操作的平均时间复杂度为 O(log N)，最坏时间复杂度为 O(log N)。
| | 支持范围查询。 |
| 节点构成 | 键、值、左子节点指针、右子节点指针、父节点指针（可选）、颜色属性。每个节点通常有3-4个指针。 | 键、值、指向多个下一个节点的指针数组。每个节点有 level+1 个指针。 |
| 内存开销 | O(N)，每个节点开销相对固定（key大小 + value大小 + 3-4个指针大小 + color大小）。 | O(N * (1/(1-P)))，每个节点开销是可变的，平均而言是 key大小 + value大小 + (1/(1-P)) * 指针大小。通常会比平衡树多占用内存。 |
| 缓存局部性 | 树结构通常导致节点在内存中分散，遍历时可能产生较多缓存未命中。 | 链表结构在水平方向上连续性较好，但垂直方向的跳跃可能导致缓存未命中。std::vector 存储 forward 指针可能导致节点内部指针存储的连续性变差。但如果使用定制的内存池，可以优化。 |
对于跳表而言，内存开销的计算略复杂。假设每个节点有 k 个指针，那么总指针数是 N * (1/(1-P))。例如，如果 P=0.25，那么平均每个节点有 1/(1-0.25) = 1/0.75 = 1.33 个指针。如果 P=0.5，那么平均每个节点有 1/(1-0.5) = 2 个指针。这意味着跳表节点通常比平衡树节点占用更多内存，因为它需要存储多个 forward 指针。
2. 速度性能分析
| 特性 | 平衡树 (如红黑树) |
| 最坏情况 | O(log N) |
| 平均情况 | O(log N) |
| 特点 | 遵循严格的数学规则，以确保树的平衡，操作复杂。 | 依赖概率性选择，实现相对简单，并发性能优异。 |
| 并发性 | 复杂。 细粒度锁定困难，因为旋转操作可能改变树的结构，影响多个节点。通常需要更粗粒度的锁或复杂无锁算法。 | 简单。 由于节点更新通常只影响有限的指针，且各层之间相对独立，因此更容易实现无锁 (lock-free) 或读写锁 (RW-lock) 优化。 |
| 常数因子 | 平衡树的常数因子通常较高，因为每次操作可能涉及多次比较、指针修改以及复杂的旋转和颜色调整。 | 跳表的常数因子通常较低，因为每次操作主要涉及简单的指针遍历和更新。随机数生成可能带来少量开销。 |
| 最坏情况 | 严格 O(log N)。