Redis的底层结构

384 阅读5分钟

redis我们都知道有5种数据类型,分别是string,list,hash,set,zset,那么你知道它们的底层数据结构实现吗? 字符串 列表 哈希 集合 有序集合

redis底层有6种数据结构,分别是简单动态字符串(SDS),链表,字典,跳跃表,整数集合,压缩列表。

每种数据类型都有着2种以上的数据结构实现,在不同状态下会进行数据结构的转换\

简单动态字符串(Simple dynamic string 简称 SDS)

SDS的数据结构

SDS只是在C字符数组的基础上封装了一下而已,其思想与java的集合类的扩容相似,当字符数组不能容纳修改后的字符的话就会进行自动扩容。此外,还添加字符长度len与空闲长度free两个字段,其数据结构如下:

public class SimpleDynamicString {
    
    int free;
    int len;
    char[] buf;
}
解决的问题

相对于直接使用C语言的字符数组来表示Redis中的字符串,Redis的SDS存在如下几个好处:

  • 无需再每次修改字符串时进行内存重分配操作(append 操作判断是否扩容,trim操作仅仅将回收的字节记录到free字段),因为buf数组中存在未使用的空间
  • buf数组中的内容是二进制安全的,因为C语言中数组结束的判断是通过'\0'判断的,而SDS是通过len来判断buf数组中的内容,这样SDS中可以存放包含'\0'的数据 获取字符串长度只需要返回len的值,无需遍历buf数组,时间复杂度由o(n)降低到o(1)

链表

链表结构是双向非循环链表,其实现与Java中LinkedList相同

使用场景:

当Redis中使用链表结构,且链表中的元素个数较多或者链表中保存字符串长度较长时,Redis中的链表会使用LinkedList来实现。

Hash表

Hash实现与Java中的HashMap实现相似,都是采用链地址法解决冲突(Redis中并没有引入红黑树优化),存在以下不同:

  • 扩容不同,Redis中的字典结构保存了两个Hash表,扩容时会将dict[0]中的元素重hash到dict[1]中,重hash完成后,将dict[0]执行dict[1], 通过字段trehashindex表示该字典是否正在重hash操作

  • 扩容条件不同,Redis扩容时会在哈希因子>1(如果发生save与bgsave操作,哈希因子>5)时才会进行扩容,Java中当哈希因子>0.75时就会扩容

  • Java中HashMap只会扩容,而没有收缩操作,Redis中当哈希因子<0.1时,会进行收缩操作

    使用场景

整数集合(IntSet)

整数集合存储的都是整数,并且保证集合的无重复和有序性。整数集合可以保存int_16、 int_32、 int_64类型的整数。

  • 升级操作

当往编码为int_16的整数集合中添加一个int_32的整数时,整数集合就会进行扩容操作,将int_16类型的整数全部升级为int_32表示,然后插入int_32的整数。这样可以保证在一个数组中保存的时同一类型的数据。数据都存放在一个int_8类型的数组中。(但是不会出现int_8类型的整数)

  • 使用场景

当Redis的集合元素中元素全部为数字并且元素个数较少 时,Redis集合的实现使用的就是整数集合

压缩列表(ZipList)

压缩列表使用的时连续的内存块,通过一个字节数组来表示,字节数组中严格标记了各个字节的作用: 列表字节数(4字节)+列表尾指针(4字节)+列表长度(2字节)+元素1+元素2+...+元素n+结束标记(1字节)

适用场景

压缩列表用于Redis的3种类型中:

  • 当Redis 列表元素个数非常少并且元素长度较短时,Redis列表底层实现使用ZipList
  • 当Redis字典中元素个数较少且元素长度较短时,Redis字典底层实现使用ZipList
  • 当Redis有序集合中元素个数较少时且元素长度较短时,Redis有序集合底层实现

使用ZipList(有序集合不能理解为Java中的集合,Java中的集合的元素为一个对象,Redis中的有序集合除了强调集合中的对象,还强调了对象对应的得分score,可以理解为Redis的有序集合为一个键值对,值为对象的得分。其次,ZipList不能自动保证有序,有序集合在使用ZipList时,强制ZipList进行了有序处理。正是因为有序集合中强调了得分与键值对的概念,所以有序集合并没有使用本身保证有序的整数集合来实现)

跳跃表(SkipList)

跳跃表与有序表不同的是,跳跃表中每一个元素都随机保存了到其后m个元素(这里称之为跨度)的指针,这样保证了元素可以快速往后查找,对于区间操作非常的方便。每一个元素还保存了到上一个节点的指针。元素节点数据结构如下:

  • 使用场景

Redis有序集合当元素数量较多或者元素内容较长时,使用SkipList实现,SkipList非常适合Range操作,但是对于查找对象得分的操作非常不方便,因为在Redis有序集合中还引入了Hash提供对象与得分的映射来辅助SKipList完成有序集合的相关操作 总结