我们都知道Redis是一种内存数据库,其支持很多数据类型的操作,比如:String(字符串)、List(集合)、Hash(哈希表)、Set(集合)和 Sorted Set(有序集合),其实这些只是Redis保存键值对的数据类型,也就是数据的保存形式,而Redis底层的数据结构并不是这些,这边文章就带大家了解一下Redis底层的数据结构。
底层数据结构
Redis底层数据结构包括:
- 动态字符串
简单的动态字符串
- 双向链表
双向链表,其实就是通过链表的指针去顺序的寻找元素,时间复杂度是O(n),效率较低
- 压缩列表
压缩列表实际上类似于一个数组,数组中的每一个元素都对应保存一个数据。和数组不同的是,压缩列表在表头有三个字段 zlbytes、zltail 和 zllen,分别表示列表长度、列表尾的偏移量和列表中的 entry 个数;压缩列表在表尾还有一个 zlend,表示列表结束。在压缩列表中,如果要查找定位第一个元素和最后一个元素,可以通过表头三个字段的长度直接定位,复杂度是 O(1)。而查找其他元素时,就没有这么高效了,只能逐个查找,复杂度就是 O(N) 。
- 哈希表
哈希表,学习Java的同学都知道Java中的一个集合类型HashMap就是一个哈希表,它的实现就是数组+链表的形式实现,将KV对存储在数组中,如果出现哈希冲突的时候,使用链表的形式将冲突的KV对存储。
- 跳表
跳表在链表的基础上,增加了多级索引,通过索引位置的几个跳转,实现数据的快速定位,如下图,我们将链表增加多级索引进行查找,也就是将链表分为多个区间,通过区间范围去查找,会增加查找效率,如果我们不使用跳表形式去查找元素,时间复杂度为O(n),使用跳表的形式去查找时间复杂度为O(logn)
- 整数数组
整数数组,其实就类似与Java中的List,通过数组的下标去查询元素,时间复杂度是O(n),效率较低。
下图是Redis的数据类型对应的底层数据结构,下次面试的时候可以对照有序的说出各自类型对应的结构。
时间复杂度
上述Redis底层数据结构的时间复杂度用一张图表示下
Redis如何组织键值对?
Redis为什么快,它的时间复杂度为O(1),是根据key-value对去存储数据,通过key直接可以访问到想要的数据。这里我们可以很快联想到Java中的HashMap数据结构,不错,它正是使用哈希表来保存所有的键值对,这里我们可以称它为全局哈希表。
哈希表在存储大量数据后,难免会发生哈希冲突的情况,也就是同一个元素计算的哈希值一样,会落入同一个哈希桶里,我们都知道Redis是通过链式哈希方式进行解决冲突的,也就说将冲突的哈希值对应的数据直接链到当前哈希桶下面,当然这是Redis的处理方式,Java中的HashMap实现在1.8之后,如果链表长度大于8的话,会将链表转为红黑树,提高查询效率。
在Redis存储数据量过大后,Redis对哈希表做 rehash 操作。
为了使 rehash 操作更高效,Redis 默认使用了两个全局哈希表:哈希表 1 和哈希表 2。一开始,当你刚插入数据时,默认使用哈希表 1,此时的哈希表 2 并没有被分配空间。
Redis的rehash操作步骤
- 给哈希表 2 分配更大的空间,例如是当前哈希表 1 大小的两倍;
- 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中;
- 释放哈希表 1 的空间。
Redis 渐进式 rehash
主要针对上述第二步来做优化,Redis不会将所有数据一次性的映射拷贝到哈希表2中,如果这样做的话,会导致Redis线程阻塞,无法服务其他请求。
所以Redis使用渐进式 rehash,也就是说Redis在处理客户端请求的时候,每处理一个请求的时候就会将哈希表1中的第一个索引位置开始,将该索引下的所有数据映射拷贝到哈希表2中,等待处理下一个请求时,在处理哈希表1中的下一个索引位置的所有数据。这样就会节省开销,巧妙扩容。
Redis不同操作复杂度
- 单元素操作 是指每一种集合类型对单个数据实现的增删改查操作。 如:set、get、hget、hset、hdel、等 时间复杂度为O(1)
- 范围操作 是指集合类型中的遍历操作,可以返回集合中的所有数据 如:hgetall、lrange、zset等 时间复杂度O(n)
- 统计操作,是指集合类型对集合中所有元素个数的记录 如:llen 和 scard 时间复杂度为O(1)
- 例外情况,是指某些数据结构的特殊记录,例如压缩列表和双向链表都会记录表头和表尾的偏移量 相关命令:lpop、rpop、lpush、rpush。列表头尾进行操作,时间复杂度O(1)