redis各类型数据结构和底层实现源码分析( 二 ) _redis

惰性释放空间：当执行sdstrim（截取字符串）之后，SDS不会立马释放多出来的空间，如果下次再进行拼接字符串操作，且拼接的没有刚才释放的空间大，则那些未使用的空间就会排上用场。通过惰性释放空间避免了特定情况下操作字符串的内存重新分配操作。
杜绝缓冲区溢出：使用C字符串的操作时，如果字符串长度增加（如strcat操作）而忘记重新分配内存，很容易造成缓冲区的溢出；而SDS由于记录了长度，相应的操作在可能造成缓冲区溢出时会自动重新分配内存，杜绝了缓冲区溢出。
四、List
List对象的底层实现是quicklist（快速列表，是ziplist 压缩列表和linkedlist 双端链表的组合）。Redis中的列表支持两端插入和弹出，并可以获得指定位置（或范围）的元素，可以充当数组、队列、栈等。
???????typedefstructlistNode{ // 前置节点 structlistNode* prev; // 后置节点 structlistNode* next; // 节点的值 void*value; } listNode;typedefstructlist{ // 表头节点listNode *head;// 表尾节点listNode *tail;// 节点值复制函数void*(*dup)( void*ptr); // 节点值释放函数void(* free)( void*ptr); // 节点值对比函数int(*match)( void*ptr, void*key); // 链表所包含的节点数量unsignedlonglen; } list;
rpush: listAddNodeHead ---O(1)
lpush: listAddNodeTail ---O(1)
push: listInsertNode ---O(1)
index : listIndex ---O(N)
pop: ListFirst/listLast ---O(1)
llen: listLength ---O(N)
4.1 linkedlist（双端链表）
此结构比较像Java的LinkedList，有兴趣可以阅读一下源码。

文章插图
从图中可以看出Redis的linkedlist双端链表有以下特性：节点带有prev、next指针、head指针和tail指针，获取前置节点、后置节点、表头节点和表尾节点的复杂度都是O（1）。len属性获取节点数量也为O（1）。
与双端链表相比，压缩列表可以节省内存空间，但是进行修改或增删操作时，复杂度较高；因此当节点数量较少时，可以使用压缩列表；但是节点数量多时，还是使用双端链表划算。
4.2 ziplist（压缩列表）
当一个列表键只包含少量列表项，且是小整数值或长度比较短的字符串时，那么redis就使用ziplist（压缩列表）来做列表键的底层实现。

文章插图
ziplist是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块(而不是像双端链表一样每个节点是指针)组成的顺序型数据结构；具体结构相对比较复杂，有兴趣读者可以看Redis 哈希结构内存模型剖析。在新版本中 list链表使用 quicklist 代替了 ziplist和 linkedlist：

文章插图
quickList 是 zipList 和 linkedList 的混合体。它将 linkedList 按段切分，每一段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来。因为链表的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。

文章插图
quicklist 默认的压缩深度是 0，也就是不压缩。为了支持快速的 push/pop 操作，quicklist 的首尾两个 ziplist 不压缩，此时深度就是 1 。为了进一步节约空间，Redis 还会对 ziplist 进行压缩存储，使用 LZF 算法压缩。
五、Hash
Hash对象的底层实现可以是ziplist（压缩列表）或者hashtable（字典或者也叫哈希表）。

文章插图
Hash对象只有同时满足下面两个条件时，才会使用ziplist（压缩列表）：1.哈希中元素数量小于512个；2.哈希中所有键值对的键和值字符串长度都小于64字节。
hashtable哈希表可以实现O(1)复杂度的读写操作，因此效率很高。源码如下：
???????typedefstructdict{ // 类型特定函数dictType *type;// 私有数据void*privdata; // 哈希表dictht ht[ 2]; // rehash 索引// 当 rehash 不在进行时，值为 -1intrehashidx; /* rehashing not in progress if rehashidx == -1 */// 目前正在运行的安全迭代器的数量intiterators; /* number of iterators currently running */} dict;typedefstructdictht{ // 哈希表数组dictEntry **table;// 哈希表大小unsignedlongsize; // 哈希表大小掩码，用于计算索引值// 总是等于 size - 1unsignedlongsizemask; // 该哈希表已有节点的数量unsignedlongused; } dictht;typedefstructdictEntry{ void*key; union{ void*val; uint64_tu64; int64_ts64;} v; // 指向下个哈希表节点，形成链表structdictEntry* next; } dictEntry;typedefstructdictType{ // 计算哈希值的函数unsignedint(*hashFunction)( constvoid*key) ; // 复制键的函数void*(*keyDup)( void*privdata, constvoid*key); // 复制值的函数void*(*valDup)( void*privdata, constvoid*obj); // 对比键的函数int(*keyCompare)( void*privdata, constvoid*key1, constvoid*key2); // 销毁键的函数void(*keyDestructor)( void*privdata, void*key); // 销毁值的函数void(*valDestructor)( void*privdata, void*obj); } dictType;上面源码可以简化成如下结构：