For those who are familiar with pre-2.6 Redis code, there used to be something called zipmap, but it was deprecated in favor of ziplist.
For those who are familiar with pre-2.6 Redis code, there used to be something called zipmap, but it was deprecated in favor of ziplist.
A ziplist is a list of compact varying length integers (or strings) where only the bits that make a difference are stored (I contributed the 24-bit version to Redis[1]). The argument is that a sequential search over a small data structure always wins over more complex things like hash tables, skiplists, etc.
As you get more data, Redis will switch to using skiplists or whatever - there is a config setting for that (-max-ziplist-entries and -max-ziplist-value).
[1] https://github.com/antirez/redis/commit/5a86ab47995586f0a0ef...
Interestingly, Redis lists are implemented as a double linked list of ziplists, where the size of each ziplists is bounded. This gives you good caching as the quicklist is being traversed, while limiting the cost of an insertion. Redis will also compress ziplists not near the edge in order to save space.