redis底层数据结构详解
2023-06-13 09:16:13 时间
SDS ziplist skiplist hashtable
SDS(简单动态字符串)
一个SDS结构如下:
struct sdshdr{
int len; //记录保存字符串的长度,也就是buf的长度
int free; //记录数组中未使用字节的数量
char buf[];
}sdshdr
- 获取SDS字符长度的时间复杂度为O(1)
- 当修改SDS时,会先对len进行判断,如果不够长会先进行分配,空间预分配遵循以下规则,如果SDS的len小于1MB,将会预分配当前len长度的空间;如果SDS的len超过1MB,将会预分配1M的长度
- 惰性回收,当删除字符时,SDS不立即回收空间,而是留着等待下次使用
双向链表
一个双向链表的节点结构如下:
struct listNode{
listNode *pre;
listNode *next;
void *value;
}listNode
整个链表的结构如下:
struct list{
listNode *head; //头结点
listNode *tail; //尾节点
unsigned long len; //链表所含节点数量
void *(*dup)(void *ptr); //节点值赋值函数
void *(*free)(void *ptr); //节点值释放函数
void *(*match)(void *ptr, void *key); //节点值对比函数
}list
哈希和字典
字典底层由哈希结构组成,而哈希包含哈希节点,三者的数据定义如下:
//哈希表结构
struct dictht{
dictEntry **table; //哈希表数组
unsigned long size; //哈希表大小
unsigned long sizemask; //哈希表大小掩码,总是等于size-1
unsigned long used; //该哈希表当前已有节点
}dictht
//哈希节点结构
struct dictEntry{
void *key; //键
union{ //值
void *val;
uint64_tu64;
int64_ts64;
}v;
dictEntry *next; //下一个节点
}dictEntry
//字典结构
struct dict{
dictType *type; //类型特定函数
void *privdata; //私有数据
dictht ht[2]; //两个哈希表,一个用于hash, 一个用于rehash
int rehashidx; //是否正在rehash,如果为-1,说明当前不在进行
}dict
跳表
跳表的数据结构比较复杂,可以参考这里
跳表是可以实现二分查找的存储结构,查找效率是O(logn)
整数集合
整数集合结构如下:
struct intset{
uint32_t encoding; //决定数值类型
uint32_t length; //集合包含的元素数量
int8_t contents[]; //保存元素的数组
}intset
并且数组中的每个项按从小到大有序排列,不含任何重复项
压缩列表
压缩列表的结构如下:
struct ziplist{
unsigned int zlbytes; //压缩列表占用的字节内存数
unsigned int zltail; //压缩列表表尾节点的偏移量:用来倒序遍历压缩列表。
unsigned short zlen; //压缩列表包含的节点数量
zipEntry entry[]; //节点数组,包含元素的具体信息
byte zlend; //一个字节,标志节点结束
}ziplist
struct zipEntry{
previous_entry_length; //记录前一个节点的长度,一般是1字节或者5字节
encoding; //记录值的类型,一般有1字节,2字节,5字节
content; //保存的值,可以是整数或者字符串
}zipEntry
相关文章
- redis数据结构之intset的实例详解
- Redis管理更轻松,使用可视化工具体验提升(redis可视化管理工具)
- Redis连接步骤详解,轻松应对开发需求(redis怎么链接)
- Redis安装目录详解:了解Redis在哪里安装以及如何使用(redis的安装目录)
- Redis如何快速导入大型文件(redis导入文件)
- Redis的快速写入:从性能到实践(redis写入性能)
- 使用Redis存储数组数据的方法详解(redis怎么存数组)
- Redis服务端配置详解,助你更好地管理你的数据存储系统(redis从服务器配置)
- 精通Redis:加深对数据结构的理解(redis数据结构)
- Redis解决大型业务场景分析(redis 业务场景)
- 探索Redis数据结构之旅(遍历redis数据结构)
- Redis储存优势点赞技术开发之道(点赞怎么使用redis)
- 解读Redis源码启动的步骤与技巧(启动redis源码)
- Redis大幅提升高并发性能的实践解析(redis高并发详解)
- 解决Redis雪崩 一条微服务护城河(redis雪崩如何解决)
- 重建Redis集群更换节点步骤详解(redis 集群更换节点)
- Redis集群弹性扩容实现更高水平的可伸缩性(redis集群弹性扩容)
- Redis队列深入浅出以解锁动态管理能力(redis 队列详解)
- 火力全开Redis队列友盟推送(redis队列友盟推送)
- 研究Redis锁的内部原理(redis锁内部原理)
- 宕机Redis集群崩溃单数台宕机之恐惧(redis集群单数台)
- Redis灵活应用自定义注解解析(redis自定义注解详解)
- 揪出缓慢的Redis连接(redis连接缓慢)