[关闭]
@hainingwyx 2020-10-21T23:29:20.000000Z 字数 778 阅读 116

redis数据结构

redis


基本数据结构包括:String(字符串)、List(列表)、Hash(哈希)、Set(集合)和 Sorted Set(有序集合)

基本数据结构 底层实现
string 动态字符串
List 双向链表、压缩列表
Hash 哈希表,压缩列表
Sorted Set 跳表,压缩列表
Set 哈希表、数组

redis中的键值对采用哈希表,哈希表就是一个数组,数组的每个元素称为一个哈希桶,每个哈希桶中保存了键值对数据的指针。
哈希冲突采用链式哈希。同一个哈希桶中的多个元素用一个链表来保存,它们之间依次用指针连接。
冲突增多时,Redis 会对哈希表做渐进式 rehash操作。rehash 也就是增加现有的哈希桶数量,让逐渐增多的 entry 元素能在更多的桶之间分散保存,减少单个桶中的元素数量,从而减少单个桶中的冲突。渐进式 rehash时指拷贝数据时,Redis 仍然正常处理客户端请求,每处理一个请求时,从哈希表 1 中的第一个索引位置开始,顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中;等处理下一个请求时,再顺带拷贝哈希表 1 中的下一个索引位置的 entries

压缩列表

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

压缩列表是在内存中分配一块地址连续的空间,然后把集合中的元素一个接一个地放在这块空间内,非常紧凑。

跳表

跳表在链表的基础上,增加了多级索引,通过索引位置的几个跳转,实现数据的快速定位。

复杂度

各个数据结构的查找时间复杂度

数据结构 复杂度
哈希表 O(1)
跳表 O(logN)
双向链表 O(N)
压缩列表 O(N)
数组 O(N)
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注