Redis 的底层数据结构

一、redis快速的原因:1、在内存中进行操作 2、高效的数据结构

底层数据结构一共有 6 种,分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。它们和数据类型的对应关系如下图所示:

Redis 的底层数据结构

 

 

  1.Redis使用一个哈希表保存所有键值对,2.哈希桶中的元素保存的不是值的本身,而是指向具体值的指针

 Redis 的底层数据结构

哈希冲突解决            

a:Redis的hash表是全局的,所以当写入大量的key时,将会带来哈希冲突,已经rehash可能带来的操作阻塞           

b:Redis解决hash冲突的方式,是链式哈希:同一个哈希桶中的多个元素用一个链表来保存         

c:当哈希冲突链过长时,Redis会对hash表进行rehash操作。rehash就是增加现有的hash桶数量,分散entry元素。  

Redis 的底层数据结构

 

但是,这里依然存在一个问题,哈希冲突链上的元素只能通过指针逐一查找再操作。如果哈希表里写入的数据越来越多,哈希冲突可能也会越来越多,这就会导致某些哈希冲突链过长,进而导致这个链上的元素查找耗时长,效率降低。

rehash机制            

a:为了使rehash操作更高效,Redis默认使用了两个全局哈希表:哈希表1和哈希表2,起始时hash2没有分配空间           

b:随着数据增多,Redis执行分三步执行rehash;                

1,给hash2分配更大的内存空间,如是hash1的两倍               

2,把hash1中的数据重新映射并拷贝到哈希表2中                

3,释放hash1的空间    

但是第二步涉及大量的数据拷贝(非常耗时,会阻塞redis)

为了解决这个问题Redis 采用了渐进式 rehash:集中迁移数据,改成每处理一个请求时,就从hash1中的第一个索引位置,顺带将这个索引位置上的所有entries拷贝到hash2中。

如下图所示:

Redis 的底层数据结构

压缩列表和跳表

压缩列表实际上类似于一个数组,数组中的每一个元素都对应保存一个数据。和数组不同的是,压缩列表在表头有三个字段 zlbytes、zltail 和 zllen,分别表示列表长度、列表尾的偏移量和列表中的 entry 个数;压缩列表在表尾还有一个 zlend,表示列表结束。

Redis 的底层数据结构

 

 在压缩列表中,如果我们要查找定位第一个元素和最后一个元素,可以通过表头三个字段的长度直接定位,复杂度是 O(1)。而查找其他元素时,就没有这么高效了,只能逐个查找,此时的复杂度就是 O(N) 了。

跳表:

有序链表只能逐一查找元素,导致操作起来非常缓慢,于是就出现了跳表。具体来说,跳表在链表的基础上,增加了多级索引,通过索引位置的几个跳转,实现数据的快速定位,如下图所示:

Redis 的底层数据结构

 

上一篇:极客时间-Redis核心技术与实战笔记(2)


下一篇:js图片库