c++ How to realize Skip table (skiplist)

The introduction

The bottom layer of 2-point lookup depends on the random access of array, so it can only be implemented by using array. Is it really impossible to use a two-point lookup algorithm if the data is stored in a linked list? In fact, with a little tweaking of the list, you can support something like a two-point lookup algorithm. The modified data structure is called a skip table.

define

A skip table is a randomized data structure. It allows you to quickly query a data linked list of 1 sequential element. The average lookup and insert time complexity of skip lists is O(log n), which is better than O(n) of ordinary queues. The performance is comparable to that of red black and AVL trees, but the principle of skipping tables is very simple and is currently used in both Redis and LevelDB.
A skip table is a data structure that can replace a balanced tree. The skipping table pursues probabilistic balance rather than strict balance. As a result, the insert and delete operations are much simpler and faster than balancing a two-tree.

C++ simple implementation

The following realization process is mainly simple to realize the process of skipping table, not multithreaded safety, LevelDB realization of skipping table support multithreaded safety, using std::atomic atomic operation, this paper is mainly to understand the principle of skipping table, so the most simple implementation.

#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 Flexible array technique in the language 
 };

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); //  The corresponding malloc
 }
 }

 //  Copy construction and assignment are prohibited 
 Skiplist(const Skiplist&) = delete;
 Skiplist& operator=(const Skiplist&) = delete;
 Skiplist& operator=(Skiplist&&) = delete;

private:
 Node* newNode(const Key& key, int level)
 {
 /*
 *  Open up sizeof(Node) + sizeof(Node*) * (level - 1) Size of space 
 * sizeof(Node*) * (level - 1) The size of the space is given Node.next[1] Pointer array 
 *  Why is it level-1 Rather than level Because the sizeof(Node) include 1 a Node* Pointer space 
 */ 
 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;
 }
 /*
 *  Random function, range [1, kMaxLevel] , the smaller the probability is 
 */ 
 static int randomLevel()
 {
 int level = 1;
 while (rand() % 2 && level < kMaxLevel)
  level++;

 return level;
 }

public:
 Node* find(const Key& key)
 {
 //  Start at the top and look at the end of each layer 1 A less than key Before the successor node, constantly narrowing the scope 
 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];
  }
 }

 //  If the first 1 Layer of the pNode[0]->key == key , the return pNode->next[0] , that is, to find 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;
 //  Start at the top and look at the end of each layer 1 A less than key Of the preceding relay node 
 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;
 }
 //  Each layer then inserts the new node after the preceding and subsequent nodes 
 for (int i = 0; i < level; ++i)
 {
  new_node->next[i] = prev[i]->next[i];
  prev[i]->next[i] = new_node;
 }

 if (maxLevel < level) //  The number of layers is greater than the maximum number of layers, update the maximum number of layers 
  maxLevel = level;
 }

 void erase(const Key& key)
 {
 Node* prev[maxLevel];
 Node* pNode = head;
 //  Start at the top and look at the end of each layer 1 A less than key Of the preceding relay node 
 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;
 }
 
 //  If you find key . 
 if (pNode->next[0] != nullptr && pNode->next[0]->key == key)
 {
  Node *delNode = pNode->next[0];
  //  Start at the top, if the current layer's next The value of the node is equal to key And then delete next node 
  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); //  Final destruction pNode->next[0] node 
 }
 
 //  if max_level>1 And the head node next If the pointer is null, there is no data in that layer, max_level Reduction of 1
 while (maxLevel > 1 && head->next[maxLevel] == nullptr)
 {
  maxLevel--;
 }
 }
};

#endif

Reasons why Redis and LevelDB chose skip lists instead of red black trees

Skiplist is as complex as a red-black tree, and easier to implement. In a concurrent environment, Skiplist has another advantage. The red-black tree may need to do some rebalance operations when inserting and deleting, which may involve other parts of the whole tree. However, skiplist's operation is obviously more local 1, with fewer nodes to be locked on, so it performs better in this case.

The above is c++ how to achieve the detailed content of the skip table, more information about c++ skip table please pay attention to other related articles on this site!