Redis数据类型
Redis支持的数据类型及其底层实现
| 数据类型 |
名称 |
底层实现方式 |
string |
字符串 |
long类型的整数/简单动态字符串 |
list |
列表 |
压缩列表/双端链表 |
hash |
哈希 |
压缩列表/字典 |
set |
集合 |
整数集合/字典 |
zset |
有序集合 |
压缩列表/跳跃表和字典 |
底层实现
简单动态字符串
- 简单动态字符串（SDS）是Redis键和
string类型值的底层实现方式之一。
- 每个SDS对象由三部分组成：记录字符串长度的
len，char类型的数组buf[]，和记录buf[]中未使用的字节数量的free。
- 当SDS需要被修改时，先检查char数组空间是否满足修改后的需求，如不满足会先扩容，防止溢出。
- 当需要缩短SDS保存的字符串时，不会立即释放掉多余的内存空间，而是把未使用的字节数保存在
free中，以便以后可能的内存空间增长，在有需要时才进行内存释放。
- SDS的优势为：获取字符串长度的时间复杂度为O(1)；杜绝缓冲区溢出；减少修改字符串长度时所需的内存重分配次数；二进制安全；兼容部分C字符串函数。
压缩列表
- 压缩列表是
list和hash的底层实现之一，当一个列表键只包含少量列表项，并且每个列表项要么是小整数值，要么是长度比较短的字符串，就会使用压缩列表作为实现方式。
- 一个压缩列表包含其内存字节数、内存偏移量、节点数量等信息；一个压缩列表节点包含其前一个节点的长度、数据类型和长度、节点的值。
zset对象满足元素数量小于128个、所有元素成员的长度小于64个字节时，会使用压缩列表作为底层实现方式。
字典
- Redis字典使用哈希表作为底层实现，使用
table数组保存哈希表，table中每一个元素指向一个键值对dictEntry。
- 哈希表使用链地址法解决hash冲突，链表使用头插法将新节点添加到链表的头部。
- 一个字典包含两个哈希表，一般情况下只使用其中一个，另一个在扩容时会用到。
跳跃表
- 跳跃表是
zset的底层实现方式之一，跳跃表基于有序单链表，在链表的基础上，有多个层，每层也都是有序链表，每个结点不只包含向同层下一个节点的指针，还可能包含指向下一层具有相同值的节点的指针，最底层包含全部元素。
- 跳跃表的优点：范围查找更方便；插入删除只需要修改相邻节点的指针，无需旋转；内存占用小；实现难度简单。
- 相比红黑树，插入速度快不需要旋转等操作，更容易实现，支持无锁操作。