redis-数据结构

redis中有多种数据类型，每种数据类型的底层都由一种或多种数据结构来支持

• 字符串：动态字符串
• 列表：双端链表、压缩链表
• 哈希：压缩链表、字典
• 集合：字典
• 有序集合：字典、跳跃表

动态字符串

字符串长度处理

用一个len字段记录当前字符串的长度。想要获取长度只需要获取len字段即可。

内存重新分配

c语言中涉及到修改字符串的时候会重新分配内存。修改的越频繁，内存分配也就越频繁。而内存分配的会消耗性能的，那么性能下降在所难免。

而redis中会涉及到字符串频繁的修改操作，这种内存分配方式就不合适了。于是出现了两种优化策略：

1. 空间预分配：对sds修改或扩充时，处理分配所必须的空间外，还会额外分配未使用的空间
2. 惰性空间释放：sds缩短时，并不会回收多余的内存空间，而是使用free字段将多出来的空间记录下来。如果后续有变更操作，直接使用free中记录的空间，减少了内存的分配

二进制安全

二进制数据部署规则的字符串格式，可能会包含一些特殊的字符，比如“\0”等。

但c中字符串遇到“\0”就会结束，那后面的数据就读取不到了。但在sds中，是根据len来判断结束的。

c字符串和sds的区别：

c字符串	sds
获取字符串长度的复杂度为O(N)	获取字符串长度的复杂度为O(1)
api是不安全的，可能会造成缓冲区溢出	api是安全的，不会造成缓冲区溢出
修改字符串长度n次必然需要执行n次内存重分配	修改字符串长度n次最多需要执行n次内存重分配
只能保存文本数据	可以保存文本或者二进制数据
可以使用所有<string.h>库中的函数	可以使用一部分<string.h>库中的函数

双端链表

列表更多是被当作队列或栈来使用的。队列和栈的特性一个先进先出，一个先进后出。双端链表很好的支持了这些特性。

前后节点

链表里每个节点都带有两个指针，prev指向前节点，next指向后节点。

这样在时间复杂度为O(1)内就能获取到前后节点。

头尾节点

头节点里有head和tail两个参数，分别指向头节点和尾节点。这样是设计能够对双端节点的处理时间降至O(1)，对于队列和栈来说再合适不过。同时链表迭代时从两端都可以进行。

链表长度

头节点里同时还有一个参数len，和sds里类似，用来记录链表长度的。

压缩链表

如果在一个链表节点中存储一个小数据，比如一个字节，那么对应的就要保存头节点，前后指针等额外的数据。这样就浪费了空间，同时由于反复申请与释放也容易导致内存碎片化。

压缩列表它是经过特殊编码，专门为了提升内存使用效率设计的。所有的操作都是通过指针与解码出来的偏移量进行的。

压缩列表的内存是连续分配的，遍历的速度很快。

字典

redis作为k-v型数据库，所有的键值都是用字典来存储的。

字段又称哈希表，能够在O(1)时间复杂度内取出和插入关联的值

跳跃表

作为redis中持有的数据结构，其在链表的基础上增加了多级索引来提升查找效率。

每一层都有一条有序的链表，最底层的链表包含了所有的元素。这样跳跃表就可以支持在O(logN)的时间复杂度内找到对应的节点。