Implementation principle of redis string and sorted set

character string
yes Redis The most common type of data storage in , Its underlying implementation is a simple dynamic string sds(simple dynamic string), Is a string that can be modified .
It uses pre allocation of redundant space to reduce the frequent allocation of memory .
When the string length is less than 1M when , Expansion is to double the existing space , If exceeded 1M, When expanding, it will only expand more at one time 1M Space .( The maximum length of the string is 512M)
So when more than 512M When an error

 Every sds.h/sdshdr The structure represents a SDS Value  
struct sdshdr{
     
// Record buf Number of bytes used in the array  
// be equal to sds The length of the saved string  
int len; 
 
// Record buf Unused data in  
int free; 
 
// A character array , To hold strings  
char buf[];
}

That is, every time you create one sds, Will perform the above operations , Will apply for additional 8 Only bytes are saved len(4 byte ) and free（4 byte ） Information .

sorted set Ordered set

The bottom layer is a jump table , Jump list will maintain multiple index linked lists and original linked lists ,

Constantly improve new key nodes to form a new ordered linked list , Change time through space .
The simplest example

Insert logic
Insert new elements into the linked list , Just compare the value of the new element with the key list , This will reduce the number of comparisons .（ Similar index ）

Key node extraction logic
Because in the jump table , Use space for time , There will be multiple levels of index linked lists , Each level of the index linked list is half of the previous level , When the amount of data is large , It can easily reduce the performance of linked list query .

As for the limit of extraction , There are only two nodes in the same layer *
Extract new inodes
Jump table adopts random method , After insertion, it will determine whether the newly inserted element has become a new key
Skip the process of inserting a node
1. The new node is compared with each layer index node one by one , Determine the insertion position of the original list O(logN)
2. Insert the node into the original linked list ,O(1)
3. Using the random way of flipping a coin , Decide whether the new node is promoted to the next level index .O(logN)
Overall, the time complexity of jump table insertion is O(logN), The space complexity is O(N)
Process of node deletion
1. Find the corresponding node in the index layer and delete , Delete the same node of each layer O(logN)
3. If there is only one node left in a layer after deleting nodes , Then the linked list can be deleted .O(logN)
The time complexity of jump table deletion is O(logN)

SortedSet Typical usage scenarios
Ranking List