## 引言 二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。如果数据存储在链表中，就真的没法用二分查找算法了吗？实际上，只需要对链表稍加改造，就可以支持类似“二分”的查找算法。改造之后的数据结构叫作跳表。 ## 定义 **跳表**是一个随机化的数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(log n)，优于普通队列的O(n)。性能上和红黑树，AVL树不相上下，但跳表的原理非常简单，目前Redis和LevelDB中都有用到。 **跳表**是一种可以替代**平衡树**的数据结构。跳表追求的是概率性平衡，而不是严格平衡。因此，跟平衡二叉树相比，跳表的**插入**和**删除**操作要简单得多，执行也更快。  ## C++简单实现 下面实现过程主要是简单实现跳表的过程，不是多线程安全的，LevelDB实现的跳表支持多线程安全，用了std::atomic原子操作，本文主要是为了理解跳表的原理，所以采用最简单的实现。 ``` #ifndef SKIPLIST_H #define SKIPLIST_H #include <ctime> #include <initializer_list> #include <iostream> #include <random> template <typename Key> class Skiplist { public: struct Node { Node(Key k) : key(k) {} Key key; Node* next[1]; // C语言中的柔性数组技巧 }; private: int maxLevel; Node* head; enum { kMaxLevel = 12 }; public: Skiplist() : maxLevel(1) { head = newNode(0, kMaxLevel); } Skiplist(std::initializer_list<Key> init) : Skiplist() { for (const Key& k : init) { insert(k); } } ~Skiplist() { Node* pNode = head; Node* delNode; while (nullptr != pNode) { delNode = pNode; pNode = pNode->next[0]; free(delNode); // 对应malloc } } // 禁止拷贝构造和赋值 Skiplist(const Skiplist&) = delete; Skiplist& operator=(const Skiplist&) = delete; Skiplist& operator=(Skiplist&&) = delete; private: Node* newNode(const Key& key, int level) { /* * 开辟sizeof(Node) + sizeof(Node*) * (level - 1)大小的空间 * sizeof(Node*) * (level - 1)大小的空间是给Node.next[1]指针数组用的 * 为什么是level-1而不是level，因为sizeof(Node)已包含一个Node*指针的空间 */ void* node_memory = malloc(sizeof(Node) + sizeof(Node*) * (level - 1)); Node* node = new (node_memory) Node(key); for (int i = 0; i < level; ++i) node->next[i] = nullptr; return node; } /* * 随机函数，范围[1, kMaxLevel]，越小概率越大 */ static int randomLevel() { int level = 1; while (rand() % 2 && level < kMaxLevel) level++; return level; } public: Node* find(const Key& key) { // 从最高层开始查找，每层查找最后一个小于key的前继节点，不断缩小范围 Node* pNode = head; for (int i = maxLevel - 1; i >= 0; --i) { while (pNode->next[i] != nullptr && pNode->next[i]->key < key) { pNode = pNode->next[i]; } } // 如果第一层的pNode[0]->key == key，则返回pNode->next[0]，即找到key if (nullptr != pNode->next[0] && pNode->next[0]->key == key) return pNode->next[0]; return nullptr; } void insert(const Key& key) { int level = randomLevel(); Node* new_node = newNode(key, level); Node* prev[kMaxLevel]; Node* pNode = head; // 从最高层开始查找，每层查找最后一个小于key的前继节点 for (int i = level - 1; i >= 0; --i) { while (pNode->next[i] != nullptr && pNode->next[i]->key < key) { pNode = pNode->next[i]; } prev[i] = pNode; } // 然后每层将新节点插入到前继节点后面 for (int i = 0; i < level; ++i) { new_node->next[i] = prev[i]->next[i]; prev[i]->next[i] = new_node; } if (maxLevel < level) // 层数大于最大层数，更新最大层数 maxLevel = level; } void erase(const Key& key) { Node* prev[maxLevel]; Node* pNode = head; // 从最高层开始查找，每层查找最后一个小于key的前继节点 for (int i = maxLevel - 1; i >= 0; --i) { while (pNode->next[i] != nullptr && pNode->next[i]->key < key) pNode = pNode->next[i]; prev[i] = pNode; } // 如果找到key， if (pNode->next[0] != nullptr && pNode->next[0]->key == key) { Node *delNode = pNode->next[0]; // 从最高层开始，如果当前层的next节点的值等于key，则删除next节点 for (int i = maxLevel - 1; i >= 0; --i) { if (prev[i]->next[i] != nullptr && key == prev[i]->next[i]->key) prev[i]->next[i] = prev[i]->next[i]->next[i]; } free(delNode); // 最后销毁pNode->next[0]节点 } // 如果max_level>1且头结点的next指针为空，则该层已无数据，max_level减一 while (maxLevel > 1 && head->next[maxLevel] == nullptr) { maxLevel--; } } }; #endif ``` ## Redis和LevelDB选用跳表而弃用红黑树的原因 1. Skiplist的复杂度和红黑树一样，而且实现起来更简单。 1. 在并发环境下Skiplist有另外一个优势，红黑树在插入和删除的时候可能需要做一些rebalance的操作，这样的操作可能会涉及到整个树的其他部分，而skiplist的操作显然更加局部性一些，锁需要盯住的节点更少，因此在这样的情况下性能好一些。