1. Basic concepts

  • Why is Redis fast?

    • All operations are memory based and memory access is fast
    • Excellent data structure

  • Basic data structure of Redis

    • string

      • string

    • list

      • List of compression
      • Two-way linked list

    • hash\

      • List of compression
      • Hash table

    • set\

      • Hash table
      • An integer array

    • zset

      • List of compression
      • Jump table

  • The problem

    • What structure is used to organize keys and values
    • Why do you need so many data structures
    • Dynamic strings are different from ordinary strings

2. Data structure of Redis

  • Redis uses a hash table to hold all key-value pairs (global hash table)

    • Hash table = array + Hash function

    • The Hash bucket does not store elements directly (because each element is of a different size), but Pointers to elements

    • Key is a string pointer and value is another type of pointer

    • Advantages:

      • The element can be found using the time complexity of o(1)

  • Why is the hash table operation slow

    • Hash conflict

      • Resolving hash collisions using chain addresses (hash buckets less than elements)
      • The disadvantage gradually turns into o (n) operations

    • rehash

      • If the query speed slows due to excessive hash conflicts, use Rehash to expand the number of data buckets

      • Redis uses two hash tables for incremental expansion

      • Rehash process

        • Allocate more space to hash table 2
        • Copy hash table 1 data to Hash table 2
        • Free the space of hash table 1

  • Progressive hash

    • If hash table 1 is migrated all at once, the Redis thread will block
    • Redis normally processes the client request, and copies it from the first index position in hash table 1 to hash table 2 when no request is processed
    • Copy a set of hash tables into a new table without processing a single request
    • The overhead of making a large number of copies at once is spread over multiple processing requests, ensuring no blocking

3. Efficiency of collection data operation

  • String operations are ideally o (1)

  • Collection operations are relatively complex

    • Hash tables are more efficient than linked lists to implement access
    • Reading and writing one element is more efficient than reading and writing all elements

  • What are the underlying data structures

    • An integer array

      • Step by step, speaking, reading and writing
      • Element by element by subscript and pointer, operation complexity O(N)

    • Two-way linked list

      • Step by step, speaking, reading and writing
      • Element by element by subscript and pointer, operation complexity O(N)

    • Hash table

    • List of compression

      • It’s like an array

      • record

        • The length of the list of
        • The offset at the end of the list
        • Number of entries in the list

      • operation

        • The first last element operation is o (1)
        • Other elements O (n)

    • Jump table

      • Multiple indexes are added on the basis of skip table to realize fast data location through the jump of index position
      • Jump: Jumps only in different index tables
      • The search complexity is order logN.

4. To summarize

  • Use scan instead of mass element operations
  • Lists are good for pop and push operations, never read or write randomly