Last time we shared Redis The underlying principle of strings , Today, let's take a look at Redis
List The underlying principle of lists .
Redis List command
List The list supports more related instructions , For example, a single element is added 、 Delete operation , Multiple element range operations are also supported .
List List supports the insertion of list header elements / eject ( LPUSH/LPOP ), It also supports the insertion of tail elements / eject ( RPUSH/RPOP ).
in addition Redis
List The list also supports indexing ( LINDEX ) Get elements , It also supports covering elements according to their subscripts ( LSET ).
List List also supports range operations , For example, get all the elements in the specified range ( LRANGE ), Remove all elements in the specified range ( LTRIM ).
That's all Redis Related instructions , Let's see Redis
List How to implement the list at the bottom , Two data structures are used ：
- Compressed list (ziplist)
- Two way list (linkedlist)
ps: This article is based on Redis 3.2 Start to explain
Two way list (linkedlist)
Above we know
List Lists support headers / Insertion of tail elements / eject , This kind of operation uses linked list, which is very efficient , The time complexity is O(1).
Redis Two way list (linkedlist) It consists of two structures ：
The structure is as follows ：
list The header node is saved in the structure , The number of tail nodes and the number of nodes in the linked list , Because of this, the operation of the header / Insertion of tail elements / eject , The calculation of list length will be very efficient , The time complexity is O(1) .
listnode In addition to saving the value of the node in the structure , It also saves pointers to the front and back nodes , In this way, if you need to get the front node and post node of a node, it will be very efficient , The time complexity is O(1) .
In addition, if you need to specify the position to insert / Remove elements , Then you just need to change the front and back pointers of the current position node , This insertion / The complexity of delete operation is O(1) .
But be careful , Insert / Delete action premise we need to find the specified location , We can only traverse the linked list , The complexity is O(N) , So insert / The complexity of deletion is O(N) .
Two way list (linkedlist) Besides being used as a key in the list , It's also widely used for publishing / subscribe , Slow query and other internal operations .
Since the two-way list (linkedlist) Can satisfy the list key operation , What then? Redis The list also uses other data structures ？
In fact, it is mainly because of the memory consumption problem , Double linked lists use two structures , And both of these structures need to hold some necessary information , This is bound to take up part of the memory .
And when there are very few elements , If you use a double linked list directly , Memory is still a waste . therefore Redis Introduce compressed list .
The compressed list is Redis Developed to save memory , It's made up of a series of specially coded Continuous memory block Sequential data structure composed of , The overall structure is as follows ：
You can see from the above structure that , Compressed lists are actually similar to the arrays we use , Each element in the array holds one data .
But unlike arrays , There are three fields in the header of the compressed list
In addition, there is a field at the end of the compressed list ,
zlend A special value is stored in it ,
OXFE , Used to mark the end of a compressed list .
A compressed list can be made up of multiple nodes , Each node can hold integer values or byte arrays , The structure is as follows ：
Use compressed lists , If you look for and locate the header element , We just need to compress the length of the header field with three starting points , Search is very fast , Complexity is O(1).
And the last element of the compressed list , It's also very easy to find , We use the compressed list starting address plus
zltail The included length can be directly pointed to , Search is also very fast , Complexity is O(1).
As for the other elements in the list , It's not so good luck , We can only start with the first element or the last element , Traverse the list to find , The complexity here is O(N) 了 .
In addition, the addition of compressed list 、 Remove elements , Will result in reallocation of memory , The efficiency is not high , The average complexity is O(N), The worst-case complexity is O(N^2).
When we create a Redis List key , If the following two conditions are satisfied at the same time , The list object will use the compressed list as the underlying data structure
- The length of all string elements saved by the list object is less than 64 byte
- The number of elements saved in the list object is less than 512 individual
If these two conditions cannot be met at the same time , By default, the bidirectional list will be used as the underlying data structure .
Redis Two data structures are used at the bottom of the list , Compressed list and double linked list .
Compressed list due to the use of contiguous blocks of memory , Less memory usage , And memory utilization is high , But new 、 Delete because it involves reallocation of memory , The efficiency is not high .
Two way list , newly added 、 It's very convenient to delete elements , But because each node is independent, the memory is fast , High memory footprint , And memory fragmentation is serious .
These two data structures are in the header / Inserting and deleting elements at the end of a table , It's very efficient . But other operations , Maybe it's inefficient .
So we use Redis list , We must adjust measures to local conditions , Think of it as FIFO queue , This only uses POP/PUSH , It's going to be very efficient .
original text ：www.tuicool.com/articles/N7nQ73r
- Redis Design and implementation
After reading three things ️
If you think this is helpful for you , I'd like to invite you to do me three little favors ：
give the thumbs-up , forward , There's your 『 Praise and comment 』, That's what motivates me to create .
Official account 『 Java Doudi 』, Share original knowledge from time to time .
At the same time, we can look forward to the following articles ing