卡飞资源网

专业编程技术资源共享平台

详解Redis五种数据结构的底层原理

1,redis有五种基本数据结构:string、hash、set、zset、list;底层redis是通过c语言来实现这w五种结构的,具体是如何实现的,我们具体看一下。

2,SDS "simple dynamic string",redis中所有场景中出现的字符串,基本都是由SDS来实现的。非数字的key、字符串值类型、非字符串数据类型的字符串值都是SDS实现的。

实现方式:

free:还剩多少空间 len:字符串长度 buf:真正存放的字符的数组


空间预分配:修改字符串带来的内存重分配,sds采用一次分配适当的内存(长度小于1MB,则多分配现有len长度的空间,大于等于1MB,则扩充除了满足修改之后的长度外,额外多1MB空间)

惰性空间释放:sds在数据减少时,并不立刻释放空间

2,int 存放数字包括字符串形式的数字

intset 整数集合是集合键的底层实现方式之一



3,双向链表

实现方式:head tail指针指向链表头尾,len链表的长度

4,ziplist 压缩表 是列表的键和hash的键的存储方式的底层实现,主要是为了节约内存,就是连续的内存块,减少内存碎片和指针占用。

zlbytes是占用内存总数,zllen记录节点个数,ztail表示结尾的指针偏移量

entry的结构

对压缩表的修改需要不断的对压缩列表进行空间重分配工作,直到结束

5,hash表

不同的key映射到bucket数组,数组用作hash碰撞的拉链也就是一个链表,rehash指的是重新计算键的哈希值和索引值,然后将键值对重排的过程。在hash因子达到阈值会rehash


6,跳跃表

header tail 指针指向跳跃表的头和尾,level层级最大的节点层数,len跳跃表的长度,是双向链表


7,redis没有直接使用以上结构来实现k-v数据库,而是基于对象引用上边的几种结构


指针指向具体的数据结构:

string:数字的时候是int,其他情况是SDS(row长字符embstr短字符 39是长短的界限)

list:双向链表quicklist和ziplist压缩链表(列表长度小于512,元素长度小于64)

hash:ziplist(个数小于512,元素长度小于64)和hashtable

set:intset数字集合和hashtable

zset:ziplist和跳跃表

控制面板
您好,欢迎到访网站!
  查看权限
网站分类
最新留言