• bearophile (9/19) May 20 2012 A stackoverflow site question: "What are the underlying data

"bearophile" <bearophileHUGS lycos.com> writes:

A stackoverflow site question: "What are the underlying data 
structures used for Redis?":

An answer:


A part of the answer:
But when lists, sets, and sorted sets are small in number of 
items and size of the largest values, a different, much more 
compact encoding is used. This encoding differs for different 
types, but has the feature that it is a compact blob of data 
that often forces an O(N) scan for every operation. Since we use 
this format only for small objects this is not an issue; 
scanning a small O(N) blob is cache oblivious so practically 
speaking it is very fast, and when there are too many elements 
the encoding is automatically switched to the native encoding 
(linked list, hash, and so forth).<

It reminds us of the usefulneess of having "small AA" (and small 
set, small linked list) optimizations.

Bye,
bearophile