1.简单动态字符串
每个sds.h/sdshdr结构表示一个SDS值，Redis是C语言写的。
image.png
与C字符串的区别：
-
常数复杂度获取字符串长度
-
杜绝缓冲区溢出
C字符串不记录长度，如果两个C字符串前后紧挨在一起，这时候扩展前字符串时，后字符串就会被覆盖。
- 减少修改字符串时内存重分配的次数
结构体的free，就是处理分配的空间大小，如果你要扩展的话，可以探索是否有足够空间，够的话直接修改free，不够再重分配，缩短一定不用重分配了，直接缩短就行了。
-
二进制安全
-
兼容部分C字符串函数
2.链表
链表广泛运用与Redis的各个功能，例如：列表键、发布与订阅、慢查询、监视器等。
image (1).png
3.字典
(1) 结构体
字典所使用的的哈希表结构：
image (2).png
我们存进去的hash键值对是哈希表的节点
image (1).png
字典的结构体：
d64ecd6c-f2f3-46ec-96b0-a16542c9b0e1.png
整个关系是：字典>哈希表>键值对
(2)存入过程
-
先计算键值对的哈希值，根据哈希值模哈希表的节点数，得出键值对存入哪个节点中。解决哈希冲突的方法是拉链法
-
当键值对越来越多的时候，为了维持负载因子在一定量，会进行rehash操作。rehash过程采用的是渐进式rehash
4.跳跃表
-
一种有序数据结构，它通过在每个节点中维持多个指向其他结点的指针，从而达到快速访问节点的目的。
-
跳跃表支持平均Ologn，最坏On复杂度的查找复杂度，跳表实现比平衡二叉树简单。
-
跳表只在有序集合键使用到了
(1)跳表的实现
f82d6ecc-593f-4588-909a-783fe7474dc2.png
跳表用了两个结构体定义，相对复杂的是节点的结构体定义。
跳跃表节点
3c0bcfbb-442c-4f39-bed9-829f8802760b.png
-
每个节点都有一个数组，我们称作层，每一层都可以直接指向其他节点，只要层越多，访问节点速度越快。
-
每层都有一个前进指针，还有个跨度，前进指针用来指向下一个节点，跨度记录前进指针跨了几个节点。
5.整数集合
数据结构如图：
2f76af1a-e7cd-4ed7-8aa3-679b7aaa2476.png
-
整数集合是个集合，所以不会有重复值，只存放整数int8、int32、int64；
-
整数集合底层实现是个数组contents，而且排好序的
-
contents的类型不是int8，真正的类型是由encoding的值决定的。
升级与降级
升级过程：
1）根据新元素的类型，扩展数组底层的空间大小，并为新元素分配空间；
2）将底层数组的所有元素换成对应的类型，并保证有序性的情况下放在正确的位置上；
3）将新元素放入底层数组中；
升级的好处：
-
提升灵活性
-
节约内存
降级：整数集合不支持降级操作，一旦升级就不会降级。
6.压缩列表
-
压缩列表是列表键与哈希键的底层实现之一；
-
压缩列表的结构包括：zlbytes、zltail、zllen、entrys；其中entrys是个列表，zlbyte表示整个压缩列表的大小，zltail是从压缩列表首地址到最后一个entry的地址偏移量；
-
entry由previous_entry_length、encoding、content组成，其中：
- previous_entry_length保存上一个entry的长度，大小有1字节或者5字节，可用这个值来计算上一个节点的首地址
-
encoding记录了content的类型以及长度
-
连锁更新：我们往一个压缩列表的首节点插入一个大于254字节的节点，这时，后面的那个节点的previous_entry_length就要从1字节编程5字节，这时就需要重分配内存，而重分配后，该节点后一个结点的previous_entry_length也要从1字节变成5字节，会导致连锁更新。
网友评论