A list,

Skip table is called skip table, skip table for short. Skip table is a randomized data structure, in essence is a binary search ordered linked list. Skip table in the original ordered list above the increase of multi-level index, through the index to achieve fast search. Skip tables not only improve search performance, but also insert and delete performance.

Skip List, a random data structure, can be regarded as a variation of binary tree, which is very similar to red-black tree and AVL tree in performance. However, Skip List is much easier to implement than the previous two. The current Redis zSet implementation uses Skip List(LevelDB and others also use Skip List).

A simple comparison between RBT red-black trees and Skip List: RBT red-black trees

  1. Insert and query time complexity O(logn)
  2. Natural order of data
  3. Realize complex, design discoloration, left – right rotation balance and other operations
  4. Need to lock

Skip List Skip List

  1. Insert and query time complexity O(logn)
  2. Natural order of data
  3. Simple implementation, linked list structure
  4. Don’t need to lock

Ii. Skip List algorithm analysis

2.1 Skip List papers

The Skip List paper is posted here. Please refer to the paper for detailed study. Some formulas, codes and pictures below are from the paper. Skip Lists: A Probabilistic Alternative to Balanced Trees

www.cl.cam.ac.uk/teaching/20…

2.2 Skip List dynamic diagram

To understand the process of inserting node elements in Skip List, use a GIF from Wikipedia. \

2.3 Skip List algorithm performance analysis

2.3.1 Algorithm for computing random layers

The first analysis is the process of calculating random numbers during the insertion operation, which involves the calculation of layers, so it is very important. It has the following features for nodes:

  • Each node has a pointer to the first layer
  • The node has a pointer to layer I, so the probability of occurrence of layer I +1 is P
  • The node has a maximum layer limit, MaxLevel

Pseudo-code for computing random layers: examples in the paper \

Java version

public int randomLevel(){ int level = 1; While (random() < p && level < MaxLevel){level += 1;} return level;}Copy the code

The code contains two variables P and MaxLevel. In Redis, the values of these two parameters are respectively:

p = 1/4
MaxLevel = 64
Copy the code
2.3.2 Average number of Pointers to a node

Skip List belongs to the data structure of space for time. The space here refers to the number of Pointers contained in each node. This part is the extra internal memory overhead, which can be used to measure the space complexity. Random () is a random number, so the higher the number of node layers generated, the lower the probability (the promotion rate data in Redis standard source code is 1/4, and the structure of Skip List is relatively flat with relatively low floors). Its quantitative analysis is as follows:

  • Level = 1 probability 1-p
  • Level >=2 probability p
  • Level = 2 probability p(1-p)
  • Level >= 3 with probability P ^2
  • Level = 3 probability p^2(1-p)
  • Level >=4 with probability P ^3
  • Level = 4 probability p^3(1-p)
  • …

Get the average number of layers of a node (the average number of Pointers a node contains) : \

2195619-b17ca123586244cc.webp

Therefore, the average number of Pointers calculated by P =1/4 in Redis is 1.33

2.3.3 Time complexity Calculation

The following extras from the paper assume that p=1/2, in the skip list of 16 elements generated with p=1/2, we might happen to have 9 elements, 1 level 3 elements, 3 elements at level 3 and 1 element at level 14 (unlikely, but it could happen). How do we deal with this situation? If we used the standard algorithm and started our search at level 14, we would be doing a lot of useless work. So where should we start searching? At this point we assume that there are n elements in SkipList and the expected number of LTH elements is 1/ P. The probability of each element appearing at level L is P ^(L-1), so the expected number of elements at level L is n * (p^L-1); So you get 1 over p is equal to n times p to the L minus 1.

1 / p = n * (p^L-1)
n = (1/p)^L
L = log(1/p)^n
Copy the code

Definition: MaxLevel = L(n) = log(1/p)^n

To calculate the time complexity of Skip List, we can use reverse thinking to start from node X with the number of layers I and return to the starting point to trace the time complexity. There are two situations at node X:

  • Node X has a (I +1) layer pointer, so climb up one level with probability P, which corresponds to Situation C in the following figure.
  • Node X does not have a (I +1) layer pointer, so climb one level to the left with a probability of 1-p, corresponding to Situation B below.

Suppose C(k) = the expected cost (i.e. length) of climbing k levels of the search path in an infinite list, then the deduction is as follows:

C (0) = 0 C (k) = (1 - p) x search length (b) + p * (to find the length of condition C) C (k) = (1 - p) (C (k) + 1) + p (C (k - 1) + 1) C (k) = 1 / p + C (k - 1) C (k) = k/pCopy the code

According to the above deduction, the expected length of climbing k levels is K/P, and the length of climbing one level is 1/ P.

Since MaxLevel = L(n), C(k) = k/p, the expected value is :(L(n) — 1)/p; L(n) = log(1/p)^n = (log(1/p)^ n-1) /p; Substituting p = 1/2 yields: 2 * log2^n – 2, the time complexity of O(logn).

Skip List feature and its implementation

2.1 Skip List feature

Skip Lists typically have the following features

  1. Skip List contains multiple layers, each of which is called a level, and the level increases from 0
  2. Skip List 0, the lowest level, should contain all the elements
  3. Each level/ level is an ordered list
  4. X>Z>=0; X>Z>=0; X>Z>=0
  5. Each node element consists of a node key, a node value, and an array of Pointers to the level of the current node

2.2 Skip List Query

Assuming these elements already exist in the initial Skip List Skip List, their distribution is structured as follows: \

Query node 88, whose query route is as follows: \

  1. Start from level3 at the top level of Skip List, then query to 10 < 88&& the value of subsequent nodes is null && there is level2 at the bottom level
  2. Level2 10 iterate back, 27 < 88 && subsequent node value is null && there is a lower level1
  3. Level1 27 iterate, 88 = 88, query hit

2.3 Skip List Insertion

The initial structure of Skip List is the same as that in 2.3. At this time, it is assumed that the value of the new node element is 90, and the insertion route is as follows:

  1. The insertion position is queried in the same way as the Skip List query, where the position of the first node larger than 90 needs to be queried and inserted before the node, 88 < 90 < 100
  2. Create a new Node Node(90) and calculate a random level for the inserted Node(90). The probability of the number of layers is roughly calculated as (1/x)^level. If level is greater than the current maximum Level3, head and tail nodes need to be added
  3. Insert Node(88). Next = Node(90); Node(90).prev = Node(80); Node(90).next = Node(100); Node(100).prev = Node(90);

2.4 Delete Skip List

The process of deletion is to query the node, then delete it, and re-combine the nodes on the left and right sides of the deleted node in the form of a linked list. No diagrams are drawn here

Four, handwriting to achieve a simple Skip List

Implementing a Skip List is relatively simple and consists of two steps:

  1. Node, which defines Skip List, is stored in the form of linked List among nodes. Therefore, Node holds Pointers of adjacent nodes. Prev and next are Pointers of nodes before and after the same level, and down and up are Pointers of nodes above and below multiple levels of the same Node
  2. The implementation class of Skip List is defined, including node insertion, deletion and query. The query operation is divided into ascending query and descending query (backward and forward query). The default elements of Skip List implemented here are ascending linked List \

3.1 Defining a Node

The Node class contains the following important attributes:

  1. Score -> The weight of the node, which is the same as score in Redis, used for sorting node elements
  2. Value -> The node stores real data. Only String data can be stored
  3. Prev -> Drives of the current node at the same level
  4. Next -> Next node of the current node, with the same level
  5. Down -> The lower level of the current node, different levels of the same node
  6. Up -> Upper layer node of the current node, different levels of the same node
package com.liziba.skiplist; / * * * < p > * * jump table node element < / p > * * @ Author: Liziba * @ the Date: 2021/7/5 21:01 */ public class Node {** * public Double score */ public Double score; /** Real data stored in the node */ public String value; Public Node prev, next, down, up; public Node prev, next, down, up; public Node(Double score) { this.score = score; prev = next = down = up = null; } public Node(Double score, String value) { this.score = score; this.value = value; }}Copy the code

3.2 Action classes for SkipList node elements

SkipList includes the following important attributes:

  1. Head -> the uppermost head node in SkipList. This node does not store elements and is used to build lists and start queries, as described in 2.3
  2. Tail -> The uppermost tail node of SkipList. This node also does not store elements and is the termination flag of a query for a particular level
  3. Level -> Total number of layers
  4. Size -> Number of node elements in Skip List
  5. Random.nextdouble () < 1/2 add the level of the current node. If the level of the current node exceeds the total level, add head and tail(total level).
package com.liziba.skiplist; import java.util.Random; /** * <p> ** @author: Liziba */ public class SkipList {/** * public Node head; /** public Node tail; Public int level; /** number of elements */ public int size; public Random random; public SkipList() { level = size = 0; head = new Node(null); tail = new Node(null); head.next = tail; tail.prev = head; } @param score * @return */ public Node fidePervNode(Double score) {Node p = head; for(;;) While (p.ext.value == null && p.priv.score <= score) p = p.ext.score; // Iterate over the next level of the rightmost node (level) if (p.own! = null) p = p.down; else break; } return p; } /** * Insert node, * * @param score * @param value */ public void insert(Double score, String value) {// Front-end Node of the current Node Node preNode = fidePervNode(score); // Node curNode = new Node(score, value); // If (curnode. value! = null && preNode.value ! = null && preNode.value.equals(curNode.value) && curNode.score.equals(preNode.score)) { return; } preNode.next = curNode; preNode.next.prev = curNode; curNode.next = preNode.next; curNode.prev = preNode; int curLevel = 0; While (random.nextdouble () < 1/2) {// Insert the level of the node is greater than or equal to the level of the node, If (curLevel >= level) {Node newHead = new Node(null); Node newTail = new Node(null); newHead.next = newTail; newHead.down = head; newTail.prev = newHead; newTail.down = tail; head.up = newHead; tail.up = newTail; // Head = newHead; // Head = newHead; tail = newTail; ++level; } while (preNode.up == null) preNode = preNode.prev; preNode = preNode.up; Node copy = new Node(null); copy.prev = preNode; copy.next = preNode.next; preNode.next.prev = copy; preNode.next = copy; copy.down = curNode; curNode.up = copy; curNode = copy; ++curLevel; } ++size; } @param score @return */ public Node search(double score) {Node p = head; for (;;) { while (p.next.score ! = null && p.next.score <= score) p = p.next; if (p.down ! = null) p = p.down; If (p.score.equals(score)) return p; return null; */ public void dumpAllAsc() {Node p = head; / / Public void dumpAllAsc() {Node p = head; while (p.down ! = null) { p = p.down; } while (p.next.score ! = null) { System.out.println(p.next.score + "-->" + p.next.value); p = p.next; }} /** * public void dumpAllDesc() {Node p = tail; while (p.down ! = null) { p = p.down; } while (p.prev.score ! = null) { System.out.println(p.prev.score + "-->" + p.prev.value); p = p.prev; Public void delete(Double score) {Node p = search(score); while (p ! = null) { p.prev.next = p.next; p.next.prev = p.prev; p = p.up; }}}Copy the code