图解redis中的9种数据结构（图解Redis-六大数据结构）
图解redis中的9种数据结构（图解Redis-六大数据结构）跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目的。跳表的负载平均在、最坏为，其效率可以和平衡树相媲美，详见：跳表和平衡树对比。跳跃表链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表长度。作为一种常用的数据结构，在众多语言中出现，C语言本身没有该结构，对此Redis构建了自己的实现。字典字典又称符号表、关联数组或映射，是一种用于保存键值对的抽象数据结构。Redis字典使用hash表作为底层存储，一个hash表中包含多个hash表节点。
Redis支持多种类型的数据结构，如基本数据结构：字符串（string）、 散列（hash）、 列表（list）、 集合（set）、有序集合（sorted set）等 ，复杂数据结构：bitmaps、 hyperloglogs 、 geo等。
Redis 6大基本数据结构简单字符串sds
简单字符串sds
sds作为Redis存储结构的基石，其由C字符串演变而来。作为一个最底层的数据结构，在性能和空间上有非常细致的设计。
- 空间预分配：利用预分配空间的策略减少字符串修改时带来的内存重分配问题，同时也防止了空间溢出问题
- 惰性空间释放：在SDS需要缩容时，程序不会立即释放多于空间，这些空间可以在将来释放或者重复使用
- 二进制安全：以字节数组的形式保存数据，使用len来判断结束位置，这使得SDS可以存储任意二进制数据
- 常数复杂度获取SDS长度：本身在header记录字符长度，相较于C字符串获取len的时间复杂度提升至
- 兼容C字符串的部分函数：兼容了C字符串的部分API，易用性大幅提升
链表
链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表长度。作为一种常用的数据结构，在众多语言中出现，C语言本身没有该结构，对此Redis构建了自己的实现。
- 双端：链表节点带有prev和next指针，获取某节点的前置或者后继节点的复杂度为
- 无环：表头节点的prev和next指针都指向NULL，对链表的访问以NULL为终点
- 结构中有head与tail指针：list结构中有head与tail指针，获取链表的头或尾节点的复杂度为
- 结构中有链表长度：有链表长度len，获取节点数复杂度为
- 多态：listNode节点使用了void*指针可以用来保存不同类型的节点值
字典
字典又称符号表、关联数组或映射，是一种用于保存键值对的抽象数据结构。Redis字典使用hash表作为底层存储，一个hash表中包含多个hash表节点。
- Hash函数：MurmurHash算法，算法详情参见：MurmurHash算法
- Hash冲突解决办法：链地址法，通过dictEntry next指针构成单向链表
- rehash：哈希表的负载因子需要维持在一个合理的范围内，扩容或者缩容时需要执行rehash操作
跳跃表
跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目的。跳表的负载平均在、最坏为，其效率可以和平衡树相媲美，详见：跳表和平衡树对比。
- 主要用途：实现有序结合、用作集群节点的内部数据结构
- 分值作用：跳表节点按照各自所对应的分值从小到大排列的
- 跳跃表层高：每个跳跃表节点的层高都是1至32之间的随机数
- 跳表工作原理：跳表的插入与遍历
整数集合
整数集合是集合键的底层实现之一，当一个集合值只包含整数值元素，且这个集合的元素比较少时，Redis会采用该结构实现集合键。
- 编码类型：编码类型表示集合内数字类型，int16_t到int64_t
- 数组升级：当向一个int16_t集合中插入int64_t数字时就会产生升级，会将所有的int16_t转换为int64_t，会涉及空间重新分配
- 数组降级：整数集合不支持降级
压缩列表
压缩列表是列表键和哈希键的底层实现方式之一，当列表键（或哈希键）只包含少量的列表项，并且每个列表项（或键值）要么是小整数，要么是短字符串，那么Redis就会使用压缩表作为其底层存储。
- 设计目的：压缩表是为了节约内存而开发的内存紧凑顺序型数据结构，其本质是一个双向链表，可以倒着遍历
- 连锁更新：新增节点或者删除节点需要重新申请内存，在列表中插入或删除一个节点后引发的每个后继节点都要更新prevrawlen，可能产生大规模的级联更新，所以压缩表不适合存储太多的元素
以上就是Redis内部数据结构介绍，如果各位还想了解更多，欢迎评论 关注[飞吻]，Redis图解系列专栏持续更新中。
