Understanding Redis Internal Data Structures: SDS, Hash Tables, Ziplist, Quicklist, and Skiplist

Redis stands out among databases because it operates entirely in memory and uses highly optimized data structures.

While most users know the high‑level types (String, List, Hash, Set, Sorted Set), Redis actually implements six underlying structures: Simple Dynamic String (SDS), hash table, ziplist, quicklist, skiplist, and integer set.

Simple Dynamic String

Redis strings are mutable and stored as byte arrays. The structure, called SDS (Simple Dynamic String), is a length‑aware byte array.

struct SDS
{
  T capacity; // array capacity
  T len;      // actual length
  byte flags; // special flags (ignored here)
  byte[] content; // actual string data
}

The content holds the real characters, while capacity and len allow efficient appends without frequent reallocations. Different length ranges use different struct variants to minimize memory overhead.

How Keys and Values Are Organized: Hash Table

All key‑value pairs are stored in a hash table, which is essentially an array of hash buckets. Each bucket contains a pointer to an entry that holds both the key and a pointer to the value, regardless of whether the value is a simple string or a collection.

This design enables O(1) lookup: the key’s hash determines the bucket, and the entry can be accessed directly.

When the table grows, Redis performs an incremental rehash . During each client request, it copies entries from the old table to a new, larger table one bucket at a time, spreading the copying cost over many operations.

Hash Collision Resolution

Collisions are handled with chaining: multiple entries that map to the same bucket are linked together via a next pointer, forming a hash‑collision chain.

If chains become long, lookup time degrades, so Redis periodically rehashes to increase the number of buckets and shorten chains.

Ziplist (Compressed List)

For small zset and hash objects, Redis uses a ziplist, a compact array‑like structure with three header fields ( zlbytes , zltail , zllen ) and a terminating zlend .

Accessing the first or last element is O(1) via the header, while searching other elements is O(N). The ziplist prioritizes memory efficiency over query speed.

Quicklist (Fast List)

Earlier Redis versions stored lists using either a ziplist or a traditional doubly‑linked list. To reduce per‑node overhead, Redis introduced the quicklist, which combines many small ziplists linked together.

// linked list node
struct listNode
{
  listNode* prev;
  listNode* next;
  T value;
}

// linked list
struct list {
  listNode* head;
  listNode* tail;
  long length;
}

Each quicklist node (a ziplist) holds up to 8 KB of data; when that limit is exceeded, a new ziplist node is created.

Skiplist

Ordered collections that require fast range queries use a skiplist, which adds multiple levels of forward pointers to a basic linked list. Each higher level skips more elements, allowing O(log N) search.

The diagram shows how a three‑level skiplist reduces the number of comparisons dramatically compared to a plain linked list.

Complexity comparison of various Redis data structures is illustrated in the accompanying image.

Further Reading

Performance comparison of ziplist, linked list, and quicklist: https://matt.sh/Redis-quicklist

Recruitment Notice

The Zero team at Zhengcai Cloud is hiring engineers across many domains, including cloud‑native, blockchain, AI, low‑code platforms, middleware, big data, and more. Interested candidates can contact zcy‑tc@cai‑inc.com.