Basic data structure of redis

Redis The basic data structure

data structure

• string（ character string ）

  Redis The string of is a dynamic string , Is a string that can be modified , The internal structure is similar to Java Of ArrayList, Reduce the frequent allocation of memory by pre allocating redundant space

  When the string length is less than 1M when , Double the capacity , exceed 1M Every expansion 1M, Maximum length is 512M

  It can be used to cache user information

• list（ list ）

  Redis Medium list amount to Java Of LinkedList, Insert and delete as O(1) , Index positioning is slow , The time complexity is O(n)

  list Structure can be used as an asynchronous queue , Sequence the task structures that need to be delayed into strings and insert them into Redis A list of .

• hash（ Dictionaries ）

  amount to Java Of HashMap, It's an unordered Dictionary , Is the structure of array and linked list

  The difference is ：hash The value of can only be a string , And their rehesh Different ,HashMap When the dictionary is big ,rehash It's a time-consuming job , All at once rehash.Redis To prevent blocking services for high performance , Progressive rehash Strategy , That is to say rehash While preserving the old and new structures , Two will be queried at the same time hash structure , And then on the following scheduled tasks and hash Of the , Gradually replace the old hash A little bit of content migrated to the new hash In structure .

  shortcoming ：hash Structure consumes more storage than a single string

• set（ aggregate ）

  Redis The set of is equivalent to Java Linguistic HashSet, Internal key value pairs are unordered and unique , Equivalent to a special hash,value by NULL.

  Can be used to store the... Of the winning users in the event ID, Guarantee that the same user won't win twice

• zset（ Ordered list ）

  Be similar to Java Of SortedSet and HashMap The combination of , You can assign a sort weight to each value score. The internal implementation is implemented with a jump table or a compressed list

  Can be used to store Fans list value The value of is fans ID,score It's about time

Compressed list

When zset Saved elements are less than 128 And all elements are less than 64 Byte time , Encoded as ziplist

At this time, the ordered collection object uses the compressed list as the underlying implementation

Each collection element uses two packed list nodes next to each other to hold , The first node holds the members of the element , The second node holds the score of the element . And the set elements in the compressed list are arranged in the order of score from small to large , Place the small one near the meter head , Place the large one near the end of the watch . The dictionary key holds the value of the element , The dictionary value holds the score of the element .

Jump watch :

• The jump table is a randomized data structure , In fact, it is an ordered linked list that can be used for binary search ;

• Jump table in the original ordered list above the addition of multi-level index , Fast search by index

• Skipping tables not only improves search performance , It can also improve the performance of insert and delete operations O(log n)

• Jump table node object Property holds the members of the element , Jump table node score Attribute holds the score of the element .

• Share members and scores of the same element through pointers , So there will be no repetition , It's a waste of memory

Why use a jump table instead of a red black tree

redis Ordered set support

• Insert elements
• Remove elements
• Look for the element
• Output all elements in order
• Find all elements in the interval

The first four red and black trees can be completed , And the time complexity is the same as that of the skip table , But for the last item, the efficiency of red black tree is not as high as that of jump table .

In the jump table , To find the elements of an interval , We just need to locate the two interval endpoints at the bottom , Then traverse it , The red black tree can only locate the endpoint, and then start from the first position. Each time, it must find the subsequent nodes , It's relatively time-consuming

Besides , The implementation of jump table is relatively easy and readable , It is difficult to implement the red black tree , therefore Redis Choose to use a skip table to implement an ordered set