1. What are skip lists?
A linked list with a forward pointer is called a skip list. Skip lists are called skip lists. Skip list is a random data structure, which is a kind of ordered linked list which can carry out binary search in essence. In order to achieve fast search by index, a multilevel index is added to the original list. Skip tables can not only improve the performance of search, but also improve the performance of insert and delete operations. (From Baidu Encyclopedia)
For more information on skip lists, read: What are Skip Lists
2. Data structure of skip list in Redis
//zskiplistNode: a node of the skiplist
typedef struct zskiplistNode {
// Layers: Each node contains many layers, each pointing to the same object
struct zskiplistLevel {
// Forward pointer
struct zskiplistNode *forward;
// Span: refers to the distance between two nodes in the current layer. For example, the L3 layer of O1 and O3 nodes in the figure above crosses the O2 node in the middle, so the span is 2
unsigned int span;
} level[];
// Back pointer
struct zskiplistNode *backward;
// Score: used for sorting. All nodes in the skip list are sorted by their score
double score;
// Member objects: the actual objects to be stored in the list
robj *obj;
} zskiplistNode;
//zskiplist: skiplist
typedef struct zskiplist {
// The header node and the tail node
structz skiplistNode *header, *tail;
// Number of nodes in the table
unsigned long length;
// The number of layers of the node with the largest number of layers in the table
int level;
} zskiplist;
Copy the code3. Summary
Skip lists are one of the underlying implementations of ordered collections (Zsets).
-
Redis’ skiplist implementation consists of zskiplist and zskiplistNode. Zskiplist is used to save skiplist information (such as table head node, table tail node and length), while zskiplistNode is used to represent skiplist node.
-
Each skip list node is a random number between 1 and 32.
-
In the same skip list, multiple nodes can contain the same score value, but each node’s member object must be unique.
-
The nodes in the skip list are sorted according to the size of the score. When the score is the same, the nodes are sorted according to the size of the member objects.
4. Addendum: Java implementation of skip list
SkipList.java
import java.util.Random;
/ * * *@author DengWeiPing
* @version 1.0
* @date2021/5/16 10:00 * /
public class SkipList<T> {
private SkipListNode<T> head, tail;
private int nodes;// Total number of nodes
private int listLevel;/ / layer
private Random random;// Used to flip a coin
private static final double PROBABILITY = 0.5;// The probability of ascending by one
public SkipList(a) {
// TODO Auto-generated constructor stub
random = new Random();
clear();
}
/**
* 清空跳跃表
*/
public void clear(a) {
head = new SkipListNode<T>(SkipListNode.HEAD_KEY, null);
tail = new SkipListNode<T>(SkipListNode.TAIL_KEY, null);
horizontalLink(head, tail);
listLevel = 0;
nodes = 0;
}
public boolean isEmpty(a) {
return nodes == 0;
}
public int size(a) {
return nodes;
}
/** * in the bottom layer, find the key */ in front of the insert position
private SkipListNode<T> findNode(int key) {
SkipListNode<T> p = head;
while (true) {
while(p.right.key ! = SkipListNode.TAIL_KEY && p.right.key <= key) { p = p.right; }if(p.down ! =null) {
p = p.down;
} else {
break; }}return p;
}
/** * find out if there is a key, return it, otherwise return null */
public SkipListNode<T> search(int key) {
SkipListNode<T> p = findNode(key);
if (key == p.getKey()) {
return p;
} else {
return null; }}/** * Add key-value */ to the skip list
public void put(int k, T v) {
SkipListNode<T> p = findNode(k);
// If the key values are the same, replace the original vaule
if (k == p.getKey()) {
p.value = v;
return;
}
SkipListNode<T> q = new SkipListNode<>(k, v);
backLink(p, q);
int currentLevel = 0;// The current level is 0
// Flip a coin. If less than 0.5, insert q in the upper layer as well
while (random.nextDouble() < PROBABILITY) {
// If this is still the front and the current number of layers to be inserted exceeds the height, a new top layer needs to be built
if (currentLevel >= listLevel) {
listLevel++;
SkipListNode<T> p1 = new SkipListNode<>(SkipListNode.HEAD_KEY, null);
SkipListNode<T> p2 = new SkipListNode<>(SkipListNode.TAIL_KEY, null);
horizontalLink(p1, p2);
vertiacallLink(p1, head);
vertiacallLink(p2, tail);
head = p1;
tail = p2;
}
// Find the layer above p, or if p has no upper layer, find the layer above the node to its left
while (p.up == null) {
p = p.left;
}
p = p.up;// In this case, p is the node of the previous layer
SkipListNode<T> e = new SkipListNode<T>(k, null);// Save only the key and ok
backLink(p, e);// Insert e to the right of p in the previous layer
vertiacallLink(e, q);// Connect e and q up and down
q = e;// We insert q on the upper layer and connect it to the node on the left and the node below
currentLevel++;
}
nodes++;// Number of nodes +1
}
// Insert node2 after node1
private void backLink(SkipListNode<T> node1, SkipListNode<T> node2) {
node2.left = node1;
node2.right = node1.right;
node1.right.left = node2;
node1.right = node2;
}
/** * Horizontal bidirectional connection */
private void horizontalLink(SkipListNode<T> node1, SkipListNode<T> node2) {
node1.right = node2;
node2.left = node1;
}
/** * Vertical bidirectional connection */
private void vertiacallLink(SkipListNode<T> node1, SkipListNode<T> node2) {
node1.down = node2;
node2.up = node1;
}
/** * Print the original data */
@Override
public String toString(a) {
// TODO Auto-generated method stub
if (isEmpty()) {
return "Skip list is empty!";
}
StringBuilder builder = new StringBuilder();
SkipListNode<T> p = head;
while(p.down ! =null) {
p = p.down;
}
while(p.left ! =null) {
p = p.left;
}
if(p.right ! =null) {
p = p.right;
}
while(p.right ! =null) {
builder.append(p);
builder.append("\n");
p = p.right;
}
returnbuilder.toString(); }}Copy the codeSkipListNode.java
/ * * *@author DengWeiPing
* @version 1.0
* @date2021/5/16 he said * /
public class SkipListNode<T> {
public int key;
public T value;
public SkipListNode<T> up, down, left, right; // There are four Pointers
public static final int HEAD_KEY = Integer.MIN_VALUE; / / minus infinity
public static final int TAIL_KEY = Integer.MAX_VALUE; / / is infinite
public SkipListNode(int k, T v) {
// TODO Auto-generated constructor stub
key = k;
value = v;
}
public int getKey(a) {
return key;
}
public void setKey(int key) {
this.key = key;
}
public T getValue(a) {
return value;
}
public void setValue(T value) {
this.value = value;
}
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null) {
return false;
}
if(! (oinstanceofSkipListNode<? >)) {return false;
}
SkipListNode<T> ent;
try {
ent = (SkipListNode<T>) o; // Check type
} catch (ClassCastException ex) {
return false;
}
return (ent.getKey() == key) && (ent.getValue() == value);
}
@Override
public String toString(a) {
// TODO Auto-generated method stub
return "key-value:" + key + "-"+ value; }}Copy the codetest.java
public static void main(String[] args) {
// TODO Auto-generated method stub
SkipList<String> list = new SkipList<String>();
System.out.println(list);
list.put(2."ping");
list.put(1."deng");
list.put(3."wei");
list.put(1."d");// Test the same key
list.put(4."Deng");
list.put(6."Who");
list.put(5."Flat");
System.out.println(list);
System.out.println(list.size());
}
Copy the code