CreateArtTechnology
/ Blog
Login
最新文章
Java
语言相关
库相关
虚拟机相关
CreateArtTechnology
项目搭建
使用的工具
自研的工具
开源工具
ELK
ElasticSearch
Jenkins
Markdown
GraphQL
Arthas
生产工具
Linux
Nginx
VersionControl
Subversion
Git
Redis
Archiva
Maven
Zookeeper
Spring
SpringBoot
MySql
HBase
Cassandra
容器化
Docker
Kubernetes
服务容器化从零开始
未分类笔记
算法相关
概念相关
豆知识
机器学习
机器学习从零开始
《Redis设计与实现》笔记<1-基础数据结构>
9
2019-04-02 18:18:52
生产工具
Redis
## 基础字符串结构SDS 我们知道,Redis数据结构中最基础的内容是字符串,而字符串的基础结构是字符数组。由于Redis中可以被修改的字符串通常使用一种名为简单动态字符串(simple dynamic string, SDS)的结构。 **SDS的结构** ```c struct sdshdr { // 已使用长度 int len; // 未使用长度 int free; // 数组 char buf[]; } ``` | sdshdr | | ------------ | | int len | | int free | | char buf[] | **一个SDS对象** | sdshdr | | ------------ | | 5 | | 0 | | 一个指向数组 ['R', 'e', 'd', 'i', 's', '\0'] 的指针 | **使用SDS的好处** - `常数复杂度获取字符串长度` - `避免缓冲区溢出` 可以根据len、free提前了解内存是否足够并按需扩容 - `减少内存重新分配的次数` 空间不足时可通过扩容增加字符串总容量,而空间充足时不需要重新分配;在删除时可以修改free进行惰性删除,节省内存重新分配的时间 - `二进制安全` 不以'\0'表示结束 - `兼容部分C字符串函数` 很多字符串函数以'\0'判断结尾,即使后边还有其他数据 ## 基础链表结构 Redis使用双端无环链表,加快向前向后遍历的速度。 ## 基础字典结构 Redis使用哈希表结构的字典,其结构中的哈希算法、API操作都是可替换的,目的是针对不同类型的值进行合适的操作。 Redis的字典结构会进行扩容、收缩(新字典的大小都是2的幂),并进行渐进式重哈希,同时优先读写新字典。 ## 基础跳表结构 Redis的有序集合使用了跳表,跳表查找效率接近平衡树,平均复杂度O(logN),最坏复杂度O(N)。 跳表很适合做range操作。 ## 基础整数集合 在元素均为整数且数量不多时,Redis使用基础整数集合来作为底层实现保存。 基础整数集合除了保存长度等基本属性外,使用数组保存元素(节省空间),并按元素类型使用int16、int32、int64三种类型的数组,必要时会进行升级,不会降级。 数组中的元素是经过排序由小到大存放的。 ## 基础压缩列表 在元素量少、元素为小整数或短字符串时,Redis使用压缩列表作为列表键(list)或哈希键(hash)的底层实现。 压缩列表除了表尾位置偏移量、表长度等基本属性外,使用一块连续空间保存多个节点。虽然节省了空间,但可能由于插入、删除操作引起连锁更新。 压缩列表的每个节点包含了`前一节点长`、`本节点编码(字符串或整数的各种类型)`、`内容`三个部分,同时结合表尾指针,使得Redis可以通过计算指针地址向前遍历。 ## 对象 Redis使用SDS、双端链表等基础结构构建了整个键值对数据库的对象系统。 Redis的键对象(以下简称key)均为“字符串对象”;而通常情况下,我们描述Redis的“数据类型”或Redis的“值”实际上是在描述Redis的值对象(以下简称value)。 **Redis对象定义** ```c typedef struct redisObject { // 类型 unsigned type; // 编码 unsigned encoding; // 指向底层数据结构的指针 void *ptr; // ... } robj; ``` **type定义** |类型|名称| |---|---| |REDIS_STRING|字符串对象| |REDIS_LIST|列表对象| |REDIS_HASH|哈希对象| |REDIS_SET|集合对象| |REDIS_ZSET|有序集合对象| 针对不同的对象类型的操作,需要使用不同的命令,如`set`与`mset`等。Redis在真正调用API前会判断命令与类型是否匹配。 针对不同编码的对象,虽然命令是相同的,但底层调用的API是不同的。
发布文章 101
文章被阅读 1602
最近修改
什么是“丝滑”的曲线
2021-12-08 15:19:20
高效空间数据索引R树及其批量加载方法STR简介
2021-09-29 20:33:37
关于分库分表的一些事儿
2021-06-25 11:51:25
获得诺奖的稳定匹配理论之TTC算法与GS算法
2021-03-14 23:04:48
算法小白的机器学习入门实践,从零到上线
2021-01-13 14:28:27
分站宗旨
一站式资料平台,减少重复检索,减少重复采坑。