std::atomic<int> max_height_; // Node的最大高度
std::atomic<Node*> next_[1]; // Node中每层的next节点

Node* Next(int n) {
    assert(n >= 0); // 1
      // 使用acquire load保证访问的是初始化了的node
    return next_[n].load(std::memory_order_acquire); // 2
  }
void SetNext(int n, Node* x) {
    assert(n >= 0); // 3
      // 使用release store保证使用这个函数
    // 来进行next的插入的都是已经初始化了的node
    next_[n].store(x, std::memory_order_release); // 4
}

Node* NoBarrier_Next(int n) {
    assert(n >= 0);
    return next_[n].load(std::memory_order_relaxed);
  }
  void NoBarrier_SetNext(int n, Node* x) {
    assert(n >= 0);
    next_[n].store(x, std::memory_order_relaxed);
  }

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();
  if (height > GetMaxHeight()) {
    for (int i = GetMaxHeight(); i < height; i++) {
      prev[i] = head_;
    }
    // It is ok to mutate max_height_ without any synchronization
    // with concurrent readers.  A concurrent reader that observes
    // the new value of max_height_ will see either the old value of
    // new level pointers from head_ (nullptr), or a new value set in
    // the loop below.  In the former case the reader will
    // immediately drop to the next level since nullptr sorts after all
    // keys.  In the latter case the reader will use the new node.
    max_height_.store(height, std::memory_order_relaxed);
  }
  
  x = NewNode(key, height);
  for (int i = 0; i < height; i++) {
    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i)); // x->next = prev->next
    prev[i]->SetNext(i, x); // prev->next = x
  }
}