redis-数据结构

Author Avatar
丁起男 11月 18,2020
  • 在其它设备中阅读本文章

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)的时间复杂度内找到对应的节点。