布鲁斯的技术小屋

leveldb(二) 跳表

首先从其对外暴露的接口开始

试想一下，跳表需要对外什么接口？增删查改

而LevelDB中，只提供了增查，Insert和Contain两个接口，没有改很好理解，因为leveldb本身就没有改操作（为什么没有删除？话说leveldb怎么实现删除的还需要继续查资料）

同时，skiplist只提供了构造函数，不提供拷贝构造和拷贝赋值函数

1
2
SkipList(const SkipList&) = delete;
 SkipList& operator=(const SkipList&) = delete;

在讨论这菜式具体怎么做之前，先看一下原材料

首先跳表本质上也是一个链表，基本组成单元是节点

Node

想一下Node需要包含什么

  1. key
  2. 一个可变长的Node*数组

提供什么接口？

  1. 获取第n层的下一个next节点
  2. 增加一层，其高度为n，且设置其后续节点为x

LevelDB就是这样子设计的（省去了线程安全部分，这部分后面再细讲）

1
2
3
4
5
6
7
8
9
struct Node {
  Node(const Key& k) : key(k) {}
  Key const key;
  Node* next(int n);
  void setNext(int n, Node* x);
  
  private:
  Node* next_[1];
}

迭代器

这里作者为了方便遍历，写了个iterator，适合我这种初学者看看迭代器是怎么写的，感觉没什么技术细节，就不细讲了

提供了以下接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class SkipList {
    private:
      const Skiplist* list_;
      Node* node_; // 遍历指针，实现的时候用了多处的assert(node_ != nullptr),俗话说的防御性编程
  public:
      Iterator(const Skiplist* list);
      
      bool Valid() const;
      const Key& key() const;
      void Next();
      void Prev();
      void Seek(const keY& key);
      void SeekToLast();
      void SeekToLast();
}

Insert

可以先想一下，插入需要完成什么步骤

  1. 找到插入的位置，prev
  2. 构造一个新的node
  3. 通过随机函数看节点取多高
  4. 将各层与prev和next相连
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template <typename Key, class Comparator>
void SkipList<Key, Comparator>::Insert(const Key& key) {
  // TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual()
  // here since Insert() is externally synchronized.
  Node* prev[kMaxHeight];
  Node* x = FindGreaterOrEqual(key, prev); // 找插入的位置

  // Our data structure does not allow duplicate insertion
  assert(x == nullptr || !Equal(key, x->key));

  int height = RandomHeight(); // 决定新node的高度
  if (height > GetMaxHeight()) {
    for (int i = GetMaxHeight(); i < height; i++) { // 如果高度大于目前最高，就设置prev为头节点
      prev[i] = head_; 
    }
    max_height_ = height; // 此处有改动
  }

  x = NewNode(key, height); // 创建新的node
  for (int i = 0; i < height; i++) {
    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
    prev[i]->SetNext(i, x);
  }
}

Contain

还是一样，先想想查找需要什么步骤

  1. 从头节点开始遍历

  2. 先在同一层找到满足key <= value && next->key > value的node

    1. 如果key == value，直接返回当前node

    2. 如果key < value，则令

      1
      p = p->next_[level - 1];

      继续往下一层找

实际代码实现就是差不多

  1. 主要是通过FindGreaterOrEqual找到第一个大于或等于的node
    1. 从头节点的最高层出发
    2. 在同一高度下找到一个node，next的值大于等于target值
    3. 查看高度是否为0，若不是，往下直到level = 0时返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node*
SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key,
                                              Node** prev) const {
  Node* x = head_; 
  int level = GetMaxHeight() - 1;
  while (true) {
    Node* next = x->Next(level);
    if (KeyIsAfterNode(key, next)) {
      // 如果key值比next大，就继续找
      x = next;
    } else {
      // 保存prev指针，insert函数需要
      if (prev != nullptr) prev[level] = x;
      // 当值等于目标值，且处于最底层，就返回
      if (level == 0) {
        return next;
      } else {
        // 继续往下一层找
        level--;
      }
    }
  }
}
1
2
3
4
5
6
7
8
9
template <typename Key, class Comparator>
bool SkipList<Key, Comparator>::Contains(const Key& key) const {
  Node* x = FindGreaterOrEqual(key, nullptr); // 找大于或等于的第一个node
  if (x != nullptr && Equal(key, x->key)) {
    return true;
  } else {
    return false;
  }
}

最后，可以去刷到leetcode体验一下完整过程~https://leetcode-cn.com/problems/design-skiplist/