LevelDB源碼解析(2) SkipList(跳躍表)

你也可以通過我的獨立部落格 —— www.huliujia.com 擷取本篇文章

背景

SkipList是LevelDB的MemTable使用的底層存儲結構，LevelDB實作了一個支援泛型的跳躍表。本文不會具體介紹跳躍表的資料結構，如果讀者不了解跳躍表的原理、實作，可以先看一下跳躍表（Skiplist）從原理到實作

SkipList的對外接口

Level對外隻提供了3個接口，構造、插入、查找。沒有提供删除接口，這個主要是因為LevelDB不會對SkipList的元素進行删除操作，整個SkipList的存儲會在MemTable被釋放時一起銷毀。這裡可以先不管MemTable，隻要知道SkipList最後會被整體删除就夠了。此外因為LevelDB的SkipList是用于存儲使用者寫入的key和value的，是以LevelDB的SkipList中不會也不允許有重複的元素。

下面是SkipList的部分代碼，隻展示了和對外接口相關的代碼

template<typename Key, class Comparator>
class SkipList
{
public:
  explicit SkipList(Comparator cmp, Arena* arena);
  void Insert(const Key& key);
  bool Contains(const Key& key) const;
}
           

模闆參數

template<typename Key, class Comparator>
           

SkipList有兩個模闆參數，Key和Comparator。Key是SkipList要儲存的元素類型，Comparator是一個函數對象類型，用于比較兩個Key的大小。

構造函數

explicit SkipList(Comparator cmp, Arena* arena);
           

第一個參數cmp是一個Comparator函數對象的執行個體，用于比較大小。第二個參數arena是一個記憶體配置設定器，SkipList會使用arena來申請記憶體。Arena記憶體配置設定器我們在前面的文章 —— LevelDB源碼解析之Arena記憶體配置設定器介紹過。如果不了解的話，可以簡單了解為malloc。SkipList将從arena申請記憶體，而不是直接調用malloc申請記憶體。

Insert 和 Contains

void Insert(const Key& key);
           

字如其人，插入key，不解釋了。

bool Contains(const Key& key) const;
           

判斷SkipList是否包含key，包含就傳回true，反之傳回false。

Iterator

LevelDB還實作了一個Iterator，用于對SkipList進行尋址、周遊等操作。下面是具體的接口和作用。

class Iterator
    {
    public:
      // 構造函數，構造後iterator指向的是一個無效節點。
      explicit Iterator(const SkipList* list);

      // 判斷目前節點（iterator指向的節點）是否是一個有效節點
      bool Valid() const;

      // 傳回目前節點的值。
      const Key& key() const;

      // 指向目前節點的下一個節點
      void Next();

      // 指向目前節點的前一個節點。
      void Prev();
      
      // 指向滿足 key >= target的最小節點
      void Seek(const Key& target);
        
      // 指向第一個有效節點（即不含頭結點的第一個節點）
      void SeekToFirst();

      // 指向最後一個有效節點
      void SeekToLast();

    private:
      //Iterator所述的SkipList
      const SkipList* list_;
      //指向Iterator目前節點。
      Node* node_;
    };
           

SkipList的内部實作。

因為LevelDB的SkipList是結合LevelDB的使用場景，進行了簡化的SkipList，相當于是一個丐版SkipList。本文不會介紹具體的實作邏輯，關于SkipList的完整實作邏輯，可以看跳躍表（Skiplist）從原理到實作。這篇文章的跳躍表實作參考了LevelDB的實作，但是支援插入重複元素和删除元素。

LevelDB的SkipList通過next指針數組的方式來建構整個連結清單結構，避免了複制節點帶來的記憶體開銷和實踐開銷，也讓連結清單管理變得更為簡單。

此外，LevelDB在讀、寫next數組時，引入了原子變量用于同步，是線程安全的，可以支援多線程場景。

記憶體配置設定器

LevelDB的SkipList的記憶體管理使用了LevelDB自己開發的Arena記憶體配置設定器，以提高性能。Arena記憶體配置設定器的詳細介紹可以看這篇文章LevelDB源碼解析之Arena記憶體配置設定器

源碼版本

https://github.com/google/leveldb/releases/tag/1.22