redis内部数据结构
2024-08-29 16:05:18
redis内部数据结构,是指redis在自身的构建中,基于这些特定的内部数据结构进行的。
- 简单动态字符串:Simple Dynamic String
- 双端链表
- 字典:Dictonary
- 跳跃表:skipList
简单动态字符串
- 用途
- 实现字符串对象(StringObject);
- 在 Redis 程序内部用作 char* 类型的替代品;
- 数据结构
typedef char *sds; struct sdshdr { // buf 已占用长度
int len; // buf 剩余可用长度
int free; // 实际保存字符串数据的地方
char buf[];
};
- 总结
- Redis 的字符串表示为 sds ,而不是 C 字符串(以 \0 结尾的 char*)。
- 对比 C 字符串, sds 有以下特性:
- 可以高效地执行长度计算(strlen);
- 可以高效地执行追加操作(append);
- 二进制安全;
- sds 会为追加操作进行优化:加快追加操作的速度,并降低内存分配的次数,代价是多占用了一些内存,而且这些内存不会被主动释放。
- 用途
双端链表
双端链表作为一种通用的数据结构, 在 Redis 内部使用得非常多: 既是 Redis 列表结构的底层实现之一, 同时为大量 Redis 模块所用, 用于构建 Redis 的其他功能。
typedef struct listNode { // 前驱节点
struct listNode *prev; // 后继节点
struct listNode *next; // 值
void *value; } listNode; typedef struct list { // 表头指针
listNode *head; // 表尾指针
listNode *tail; // 节点数量
unsigned long len; // 复制函数
void *(*dup)(void *ptr);
// 释放函数
void (*free)(void *ptr);
// 比对函数
int (*match)(void *ptr, void *key);
} list- Redis 实现了自己的双端链表结构。
- 双端链表主要有两个作用:
- 作为 Redis 列表类型的底层实现之一;
- 作为通用数据结构,被其他功能模块所使用;
- 双端链表及其节点的性能特性如下:
- 节点带有前驱和后继指针,访问前驱节点和后继节点的复杂度为 O(1) ,并且对链表的迭代可以在从表头到表尾和从表尾到表头两个方向进行;
- 链表带有指向表头和表尾的指针,因此对表头和表尾进行处理的复杂度为 O(1) ;
- 链表带有记录节点数量的属性,所以可以在 O(1) 复杂度内返回链表的节点数量(长度);
- 总之
- 字典
跳跃表
最新文章
- BootLoader 详解(1)
- Java sun.misc.Unsafe类的学习笔记
- iOS 开发ALAsset获取图片缩略图
- linux 搭建SVN服务器,为多个项目分别建立版本库并单独配置权限
- linux 的终端字体色和背景色的修改方法(三)
- PHP创建XML文件讲解
- bzoj1821: [JSOI2010]Group 部落划分 Group
- PHP完整环境搭建
- cx_Oracle使用方法一
- hdu 5637 Transform 最短路
- malloc实现原理
- FileReader对象的readAsDataURL方法来读取图像文件
- 数据库之mysql篇(1)—— 数据库管理系统简介/mysql的安装、配置
- boost 随机数发生器
- hbase-基础架构
- Smali语法
- 机器学习入门-文本特征-使用LDA主题模型构造标签 1.LatentDirichletAllocation(LDA用于构建主题模型) 2.LDA.components(输出各个词向量的权重值)
- MySQL学习笔记04 插入中文时出现ERROR 1366 (HY000)
- Hex-Rays Decompiler
- react 共享数据流