SkipList的原理與實現

簡介

SkipList(跳錶)這種數據結構是由William Pugh於1990年在在 Communications of the ACM June 1990, 33(6) 668-676 發表了Skip lists: a probabilistic alternative to balanced trees，在其中詳細描述了他的工作。由論文標題可知，SkipList的設計初衷是作為替換平衡樹的一種選擇。

我們都知道，AVL樹有著嚴格的O(logN)的查詢效率，但是由於插入過程中可能需要多次旋轉，導致插入效率較低，因而才有了在工程界更加實用的紅黑樹。

但是紅黑樹有一個問題就是在並發環境下使用不方便，比如需要更新數據時，Skip需要更新的部分比較少，鎖的東西也更少，而紅黑樹有個平衡的過程，在這個過程中會涉及到較多的節點，需要鎖住更多的節點，從而降低了並發性能。

SkipList還有一個優勢就是實現簡單，SkipList的實現只花了2個小時，而紅黑樹，我可能得2天。

時隔將近三十多年，SkipList這種數據結構仍在許多途徑有用武之地，比如Redis, 還有Google的著名項目Bigtable.

原理及實現

其實跳錶就是在普通單向鏈表的基礎上增加了一些索引，而且這些索引是分層的，從而可以快速地查的到數據。如下是一個典型的跳錶:

查找

查找示意圖如下:

比如我們要查找key為19的結點，那麼我們不需要逐個遍歷，而是按照如下步驟:

• 從header出發，從高到低的level進行查找，先索引到9這個結點，發現9 < 19,繼續查找(然後在level==2這層)，查找到21這個節點，由於21 > 19, 所以結點不往前走，而是level由2降低到1
• 然後索引到17這個節點，由於17 < 19, 所以繼續往後，索引到21這個結點，發現21>19, 所以level由1降低到0
• 在結點17上，level==0索引到19,查找完畢。
• 如果在level==0這層沒有查找到，那麼說明不存在key為19的節點，查找失敗

既然演算法都有了，實現也不在話下，如下是C++實現:

template<typename K, typename V>Node<K, V> *SkipList<K, V>::search(const K key) const { Node<K, V> *node = header; for (int i = level; i >= 0; --i) { while ((node->forward[i])->key < key) { node = *(node->forward + i); } } node = node->forward[0]; if (node->key == key) { return node; } else { return nullptr; }};

其中Node的定義如下:

//forward declarationtemplate<typename K, typename V>class SkipList;template<typename K, typename V>class Node { friend class SkipList<K, V>;public: Node() {} Node(K k, V v); ~Node(); K getKey() const; V getValue() const;private: K key; V value; Node<K, V> **forward; int nodeLevel;};template<typename K, typename V>Node<K, V>::Node(const K k, const V v) { key = k; value = v;};template<typename K, typename V>Node<K, V>::~Node() { delete[]forward;};template<typename K, typename V>K Node<K, V>::getKey() const { return key;}template<typename K, typename V>V Node<K, V>::getValue() const { return value;}

插入

如下是插入結點示意圖:

其實插入節點的關鍵就是找到合適的插入位置，即從所有小於待插入節點key值的節點中，找出最大的那個，所以插入節點的過程如下:

• 查找合適的插入位置，比如上圖中要插入key為17的結點，就需要一路查找到12,由於12 < 17,而12的下一個結點19 > 17,因而滿足條件
• 創建新結點，並且產生一個在1~MAX_LEVEL之間的隨機level值作為該結點的level
• 調整指針指向

插入的代碼如下:

template<typename K, typename V>bool SkipList<K, V>::insert(K key, V value) { Node<K, V> *update[MAX_LEVEL]; Node<K, V> *node = header; for (int i = level; i >= 0; --i) { while ((node->forward[i])->key < key) { node = node->forward[i]; } update[i] = node; } //首個結點插入時，node->forward[0]其實就是footer node = node->forward[0]; //如果key已存在，則直接返回false if (node->key == key) { return false; } int nodeLevel = getRandomLevel(); if (nodeLevel > level) { nodeLevel = ++level; update[nodeLevel] = header; } //創建新結點 Node<K, V> *newNode; createNode(nodeLevel, newNode, key, value); //調整forward指針 for (int i = nodeLevel; i >= 0; --i) { node = update[i]; newNode->forward[i] = node->forward[i]; node->forward[i] = newNode; } ++nodeCount;#ifdef DEBUG dumpAllNodes();#endif return true;};

移除

移除結點的示意圖如下:

移除結點其實很簡單,就分以下3步:

• 查找到指定的結點，如果沒找到則返回
• 調整指針指向
• 釋放結點空間

代碼如下:

template<typename K, typename V>bool SkipList<K, V>::remove(K key, V &value) { Node<K, V> *update[MAX_LEVEL]; Node<K, V> *node = header; for (int i = level; i >= 0; --i) { while ((node->forward[i])->key < key) { node = node->forward[i]; } update[i] = node; } node = node->forward[0]; //如果結點不存在就返回false if (node->key != key) { return false; } value = node->value; for (int i = 0; i <= level; ++i) { if (update[i]->forward[i] != node) { break; } update[i]->forward[i] = node->forward[i]; } //釋放結點 delete node; //更新level的值，因為有可能在移除一個結點之後，level值會發生變化，及時移除可避免造成空間浪費 while (level > 0 && header->forward[level] == footer) { --level; } --nodeCount;#ifdef DEBUG dumpAllNodes();#endif return true;};

完整代碼

已經把完整代碼放到github上，地址為 https://github.com/HiWong/SkipListPro