Redis advantages and data structure related knowledge

1、Redis Do you understand

Redis (remote dictionary server） It is a distributed database based on memory storage , Support persistent operations and multiple data types , Because it is based on memory storage, it runs very fast ,Redis It also supports transactions , The commands in the transaction will be serialized and executed in order , Will not be interrupted by commands sent by other clients ;

---

2、 Why use Redis,Redis What are the advantages of

1、 Extremely high performance
Redis The speed at which you can read is 110000 Time /s, The speed of writing is 81000 Time /s.

2、 Rich data types
Redis It's not just about supporting simple key-value Data of type , It also provides list,set,zset,hash Such as data structure storage .

3、 Atomicity
Redis All operations of are atomic , It means either successful execution or failure and no execution at all . Individual operations are atomic . Multiple operations also support transactions , Atomicity , adopt MULTI and EXEC Package the instructions .
Rich features - Redis And support publish/subscribe, notice , key Expiration and so on .

4、 Support data persistence
Redis Support data persistence , The data in memory can be saved on disk , When you restart, you can load it again for use .

5、 Support data backup
Redis Support data backup , namely master-slave Mode data backup .

---

redis Basic data structure

1.string

Use a simple dynamic string （SDS） Data type to implement .

/* *  Save the structure of the string object  */  
struct sdshdr {  
    int len;  // buf  Length of occupied space in  
    int free;  // buf  Length of free space remaining in 
    char buf[];  //  Data space  
};

SDS comparison C The advantages of strings ：

SDS Save the length of the string , and C String does not save length , You need to traverse the entire array （ find ’\0’ until ） To get the string length .
modify SDS when , Check the given SDS Is there enough space , If it is not enough, it will expand first SDS Space , Prevent buffer overflow .C The string does not check whether the string space is sufficient , It is easy to cause buffer overflow when calling some functions （ such as strcat String concatenation function ）.
SDS The mechanism of pre allocating space , You can reduce the number of times you reallocate space for Strings .

---

2.list

Use a two-way linked list to achieve .

---

3.hash

hash The structure is actually a dictionary , There are many key value pairs （ Be similar to python Of dict type ）.

redis The hash table is a dictht Structure ：

typedef struct dictht {
   dictEntry **table;// Hash table array  
   unsigned long size;// Hash table size  
   unsigned long sizemask;// Hash table size mask , Used to calculate index values 
   unsigned long used;// The number of existing nodes in the hash table 
}

The structure of the hash table node is as follows ：

typeof struct dictEntry{  
   void *key;// key 
   union{  // The types of values corresponding to different keys may be different , Use union To deal with this problem 
      void *val;
      uint64_tu64;
      int64_ts64;
   }
   struct dictEntry *next;
}

The method to solve hash conflict is zipper method .

In order to keep the load factor of hash table within a reasonable range , You need to expand or shrink the size of the hash table , It's called rehash. There are two hash tables in the dictionary dictht Structure ,ht[0] Used to store key value pairs ,ht[1] be used for rehash Temporary storage of data during , Usually, the hash table it points to is empty , Need to expand or shrink ht[0] Only allocate space for the hash table .

For example, expand the hash table , Is to ht[1] Allocate a block of size ht[0] Twice the space , And then put ht[0] The data from rehash All the way to ht[1], Final release ht[0], send ht[1] Become ht[0], Again ht[1] Allocate an empty hash table . Shrink hash table is similar to .

Progressive type rehash：redis It's not about finding time to do it all at once rehash, But gradually ,rehash The period does not affect the external impact on ht[0] The interview of , It is required to synchronize the corresponding data to ht[1] in , When all data transfer is complete ,rehash end .

---

4.set

set It can be used intset Or dictionary implementation .

intset： Only if the data are all integer values , And the number is less than 512 Time , Only use intset,intset Is an ordered set of integers , You can do a binary search .

Dictionaries

dissatisfaction intset Use a dictionary when using conditions （ Zipper method ）, When using a dictionary, put value Set to null.

---

5.zset

zset Each element in contains the data itself and a corresponding score (score).

Classic example ： One zset Of key yes "math", Represents the result of mathematics class , Then you can go to this key Insert a lot of data into . When entering data , Each time you need to enter a name and a corresponding grade . Then the name is the data itself , Achievement is its score.

zset The data itself cannot be duplicated , however score Allow repetition .

zset Underlying implementation principle ：

1. When there is little data , Use ziplist：ziplist Occupy continuous memory , Each element is （ data +score） Continuous storage , according to score Sort from small to large .ziplist To save memory , The space occupied by each element can be different , For big data （long long）, Just use more bytes to store , And for small data （short）, Use fewer bytes to store . Therefore, when searching, you need to traverse in order .ziplist Save memory, but search efficiency is low .

2. Long time data , Using dictionaries + Jump watch ：

A dictionary is used to look up score, The jump table is used to jump according to score Find data （ High search efficiency ）.

In theory , lookup 、 Insert 、 Delete and iterate to output the ordered sequence , Red and black trees can also be done , The time complexity is the same as the jump table .

redis The reason for using jump tables instead of red and black trees ：

1. The operation of finding data according to interval , The efficiency of red and black trees is not as high as that of jump table . Jump watch can be used in O(logn) Time complexity locates the starting point of the interval , Then you can query backward in order in the original linked list .

2. Compared with red and black trees , Jump tables also have code that is easier to implement 、 Good readability 、 Not easy to make mistakes 、 More flexible and other advantages .

3. Insert 、 When deleting the jump table, only a few nodes need to be adjusted , Red and black trees need color repainting and rotation , It's expensive .

Time complexity ： Time complexity = Number of levels of index * The number of elements traversed by each layer of index .

First, look at the index layers , Suppose that one of every two nodes is selected as the node of the upper index , And the highest level index has 3 Nodes , Then the index level is log2(n).

Then see how many elements are traversed by each layer , First, the highest level traverses at most 3 Nodes , You can go down , Empathy , The second level also traverses up to three nodes , Can go down . After averaging , It can be considered that each layer traverses 2 Nodes .

So time complexity =2log2(n), Empathy , If it's every k Take one index from each node , Namely klogk(n)

Spatial complexity ： Take an index of every two nodes as an example , first floor n Nodes , The second floor n/2, third time n/4, Sum of proportional sequences , Or take the limit , It can be considered that the number of inodes is infinitely close to n, So the space complexity is zero O(n).