Skip list
Definition ： Ordered data structure , Maintain multiple pointers to other nodes in each node , In order to achieve the purpose of fast access to nodes .
Use ：redis One of the implementations of ordered sets in is the jump table , When there are many nodes or members are long strings , We use the skip table as the underlying implementation of the ordered set key ;
Another place where jump tables are used is as the internal data structure of cluster nodes .
structure
The jump table has two parts Nodes and data structures that hold node information
On the left is ziplist structure , There are three on the right node level Record the maximum number of layers, which node level ,length, Record the number of nodes in the current table
Jump table node
typedef struct zskipListNode{
// Back pointer
struct zskipListNode *backward;
// The score is
double score;
// member object
robj *obj
// layer
struct zskipLIstLevel {
// Forward pointer
struct zskipListNode * forward;
// span
unsigned int span;
}level[];
}zskiplistNode;
adopt zskipList Structure to hold these nodes , It is more convenient to obtain node information and access nodes
typedef struct zskiplist{
// Header node and footer node
structz skipListNode *header ,*tail;
// The number of nodes in the table
unsigned long length;
// Hierarchy the level of the largest node
int level;
}characteristic
1 The layer height of each hop table node is 1 To 32 Random number between ;
2 In the same jump table , Multiple nodes can contain the same score , But each member object must be unique ;
3 The nodes are sorted according to the score , When the scores are the same , Nodes are sorted by member object size