What is the time complexity of the redis command?? (the actual question is about the underlying structure of redis)

redis It's open source C language-written k-v The storage system , He supported String、List、Set、ZSet、hash Five data structures , How are the underlying layers of each data structure implemented ？ What is the data structure ？

1. String

1.1 Conclusion

The underlying structure ： The pointer + A character array Time complexity ：O(1)

1.2 form

1.3 Underlying principle

Redis yes C Language development , But in C Not in language character string type , Only use The pointer and A character array To save a string . therefore Redis Designed a simple dynamic string (SDS [Simple Dynamic String]) As the underlying implementation .

struct sdshdr{
  // Record buf Length of bytes used in the array 
   int len;
  // Record buf The length of the remaining space in the array 
   int free;
  // Byte array , Used to store strings 
  char buf[];
}

Copy

• The time to get the length of the string is complex O(1), because len The current string length is saved .
• SDS It will automatically expand capacity ,SDS After splicing , If at this time len Less than 1MB, Will be more allocated to len Same unused space , Use free Express ; if ken Greater than 1MB, Will be allocated more 1MB Space .
• Inert release , When the string is shortened , The program does not immediately reclaim space , It's recorded in free in , To facilitate the use of subsequent splicing .

2. LIST

2.1 Conclusion

The underlying structure ： Double linked list Time complexity ： The query efficiency is O(n). But the time complexity of accessing the elements at both ends O(1)

1. lRange Time complexity O(n);
2. lpop Time complexity O(1);
3. lpush key value1 value2 value3... valueN from list Add one or more elements to the left of the Time complexity O(1~n);

2.2 form

2.3 Underlying principle

The underlying structure ：quicklist

A linked list structure can orderly store multiple strings , Have, for example ：lpush、lpop、rush、rpop Wait for the operation . stay 3.2 Before the release , List uses ziplist and linkedlist To achieve . And in the 3.2 After the version , Reintroduced a quicklist Data structure of , The bottom layer of the list is composed of quicklist Realized , It is a combination of ziplist and linkedlist The advantages of . According to the original explanation is ：【A doubly linked list of ziplist】. save .

In the old version , When the list object satisfies both of the following conditions , The list will use ziplist code ：

1. All string elements stored in the list object are less than 64 byte ;
2. The list object holds fewer elements than 512 individual ;

When one condition is not satisfied, transcoding will be performed once , Use linkedlist.

ziplist

ziplist It's a specially encoded two-way linked list , It is designed to improve storage efficiency . A common two-way linked list , Each item in the linked list takes up a separate piece of memory , Use address pointer between items （ Or quote ） Connect , But this method will cause a lot of memory fragmentation , And address pointers take up extra memory .

ziplist Instead, the Each item is stored in a contiguous address space , One ziplist It takes up a large amount of memory . It's a watch （list）, But it's not a list （linked list）

• ziplist effect ： Save memory ;
• ziplist characteristic ： Data is stored in contiguous address spaces ;

linkedlist

Two way list , Insert and delete efficiently , But the efficiency of queries does O(n)

quicklist

【A doubly linked list of ziplist】ziplist A bidirectional linked list . It is macroscopically a linked list structure , But each node is represented by ziplist To store data , and ziplist There are many entry. It can also be said that quicklist The node holds a piece of data

• On the whole quicklist It's a two-way linked list structure , And ordinary linked list operation is the same , Its insertion and deletion efficiency is high , But query efficiency does O(n), however , In this way, the time complexity of accessing the elements at both ends of the linked list is O(1), So yes list Most operations are poll and push.
• Every quicklist A node is a ziplist, Features of compressed list .

stay redis.conf In profile , There are two parameters that can be optimized ：

1. list-max-ziplist-size Represent each quicklist The byte size of the node , The default is -2, Express 8kb.
2. list-compress-depth： Express quicklist Whether the node wants to compress ,0 Means never compress .

3.HASH

3.1 Conclusion

The underlying structure ：ziplist perhaps hashtable Time complexity ：O(1)

3.2 form

3.3 principle

redis Can store mappings between multiple key-value pairs .hash There are actually two ways to implement the underlying data structure ：

• One is ziplist（ Press the key and value into the linked list ）, When the stored data exceeds the configured threshold, it will be converted to hashtable structure , This conversion is time consuming , We should try to avoid this kind of conversion , This structure is only used when the following two conditions are met at the same time ：
  • When the number of keys is less than hash-max-ziplist-entries（ Default 512）
  • When all values are less than hash-max-ziplist-value （ Default 64）
• The other way is hashtable, The time complexity of this structure is O(1), But it will consume more memory space .

4. SET

4.1 Conclusion

The underlying structure ： Set of integers （intset） Or a dictionary （hashtable） Time complexity ：O(1)

4.2 form

4.3 principle

typedef struct intset{
  // Encoding mode 
  uint32_t encoding;
  // Element quantity 
  uint32_t length;
  // Array of storage elements 
  int8_t contents[];
}

Copy

Every element in the set of integers is contents Array An array item of , The items are ordered in the array according to the size of the values , And does not contain duplicate items .contents The element types in the array are defined by encoding decision , When new elements are added , If the encoding of the element is greater than contents Encoding of array elements , The array elements will be upgraded as a whole , Note that degradation does not occur .

5. ZSET

The underlying structure ：ziplist perhaps skiplist（ Jump watch ） Time complexity ：O(log(n))

5.1 What is jump Watch

Power button ——1206. Design jump table

The design idea of jump table is similar to that of linked list , There are many layers in the jump table , Each layer is a short linked list . Under the action of the first layer , The time complexity of adding, deleting and querying does not exceed O(n). The average time complexity of each operation of the skip table is O(log(n)), The space complexity is O(n).

A skip table is an ordered data structure , It passes through Each node maintains multiple pointers to other nodes , So as to achieve the purpose of fast access to nodes . The expected space complexity of the jump table is O(n)O(n), Jump table query , The expected time complexity of both insert and delete operations is O(logn)O(logn).

Redis Jump table for detailed explanation of internal data structure (skiplist)

A jump table is a randomized data structure , Based on parallel linked list .

5.2 Time complexity of common commands