redis设计与实现-数据结构.png

redis 是基于c语言开发的高效key-value键值类型数据库。为实现高效以及其它一些功能，redis扩展了c语言的数据类型。

简单动态字符串（sds）

• 优化长度计算，算法复杂度为O(1)。

  数据结构中添加长度变量，记录字符串的长度

• 杜绝缓冲区溢出

重新实现字符串空间分配，引入空闲空间等概念

• 减少修改字符串长度时所需的内存重分配次数。
• 二进制安全。
• 兼容部分C字符串函数。

hash

Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

同时提供了hash冲突,rehash等功能的实现。

链表

当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时。Redis就会使用链表作为列表键的底层实现。
包括了功能如下特性

• 双端
• 无环
• 多态

跳跃表

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

主要用于zset排序和集群概念中

整数集合

整数集合引入 encode、contents等概念。使用encode记录当前内容数据类型，根据实现数据类型会发生encode扩展。具体功能特性包括

• 有序
• 无重复
• 数据类型可升级，不可降级

压缩列表

为节约内存开发的顺序型数据结构

• 列表键和hash键的底层实现
• 压缩列表可以包括多个节点，每个几点可以保护一个字节数组或整数值
• 新增或删除节点可能引起连锁更新，但是这种操作概率并不高