directory

  • Arrays and linked lists
  • The list
  • contrast
  • conclusion

Arrays and linked lists

Arrays: Arrays create a contiguous chunk of memory for storing data, which has both advantages and disadvantages. When data is obtained, the corresponding element can be obtained directly through the subscript value, and the time complexity is O(1). However, if data is added or deleted, a large amount of data will be moved, and the time complexity is O(n). If the array space is insufficient, a new space address will be created and the original array will be copied into the new array.

Linked lists: Linked lists do not require contiguous memory space; they are connected by Pointers. When adding or deleting, you only need to change the address pointed to by the pointer, and the time complexity is O(1). But the time complexity of the query is O(n).

2, list

2.1. Bidirectional linked lists

A bidirectional list is a logical relationship between nodes that is bidirectional.

The nodes in a bidirectional list are:The prior:Points to the front node of the current node,Data:Data stored on the current node.Next:A post-node that points to the current node.

2.2. Compress linked lists

  • Compressed linked lists were developed to save memory.
  • Ziplist is a special bidirectional linked list that does not maintain bidirectional Pointers prev Next; Instead, it stores the length of the previous entry and the length of the current entry, and calculates where the next element is based on the length.
  • Read performance is sacrificed for efficient storage space, because storing Pointers takes more memory than storing entry length, which is a typical time swap.

2.3. Quicklist

  • About the official website:
    A doubly linked list of ziplists
    A generic doubly linked quicklist implementation
Copy the code
  • Introduction:

Quicklist is a bidirectional linked list, and a bidirectional linked list of Ziplist, which is itself a list that maintains the order of items, and the items are stored in a contiguous block of memory.

3, contrast

3.1. Bidirectional linked lists

  • Double-ended linked lists are easy to push and pop on both ends of the table, but they are expensive in memory.
  • In addition to the data to be stored on each node of a double-ended list, two Pointers are also stored.
  • Each node of a double-ended linked list is a separate memory block, the address is not continuous, more nodes will easily generate memory fragmentation.

3.2. Compress lists

  • Because ziplist is a contiguous piece of memory, storage efficiency is high.
  • Ziplist is not conducive to modification operations; each data change causes a realLOC in memory.
  • When the Ziplist length is very long, one realloc may result in a large number of data copies, further degrading performance.

3.3. Quicklist

  • A compromise between space efficiency and time efficiency.
  • Combines the advantages of double-endian lists and compressed lists.

4, summarize

Before Redis 3.2, two types of linked lists were used: bidirectional and compressed linked lists. Because bidirectional linked lists take up more memory than compressed linked lists, compressed linked lists are first created when creating linked lists, which will be converted to bidirectional linked lists when appropriate. After Redis 3.2, quickList lists are used.