数据结构
二进制安全:底层没有类型概念,只有byte数组,所以客户端需要将数据序列化成字节数组
string
- 字符串、数值、bit位图
应用场景:
- 做简单的KV缓存
sequenceDiagram
participant User as 用户
participant WebServer as Web服务器
participant Redis as 缓存层 (Redis)
participant MySQL as 持久层 (MySQL)
User->>WebServer: 请求数据
WebServer->>Redis: 查询缓存
alt hit
Redis-->>WebServer: return 缓存数据
else miss
Redis->>MySQL: 查询数据库
MySQL-->>Redis: 数据结果
Redis->>Redis: write cache
Redis-->>WebServer: 缓存数据
end
WebServer-->>User: return 数据响应
设计合理的键名,有利于防止键冲突和项目的可维护性,比较推荐的方式是使用业务名:对象名:id:[属性]
作为键名
- incr(计数):抢购,秒杀,详情页,点赞,评论
- session服务器
stateDiagram-v2
client --> WebServer1
RedisSession --> WebServer1
WebServer1 --> RedisSession
WebServer2 --> RedisSession
RedisSession --> WebServer2
WebServer3 --> RedisSession
RedisSession --> WebServer3
- 限速 通过对key设置过期时间的方式限制用户请求频率
- 使用位图来处理海量数据
- 哈希类型 hash
- 做对象属性读写
- 列表类型 list
- 可以做消息队列或者可以来存储列表信息,进行分页查询
- 集合类型 set
- 自动去重
- 推荐系统:数据交集
- 有序集合类型 sortedset
- 排序
GEO
地理信息定位功能
geoadd locations 116.38 39.55 beijing # 添加成员
geopos locations beijing # 获取
geodist locations beijing tianjin [m|km|mi|ft] # 计算两地距离
georadiusbymember locations beijing 150 km # 获取北京方圆150km内的成员
geohash locations beijing # 将二维经纬度转换为一维字符串
关于geohash:
- 字符串越长,表示的位置更精确
- 两个字符串越相似,它们之间的距离越近,Redis利用字符串前缀匹配 算法实现相关的命令
- Redis正是使用有序集合并结合geohash的特性实现了GEO的若干命令
内部数据结构
stateDiagram-v2
String --> 简单动态字符串
List --> 双向链表
List --> 压缩链表
Hash --> 压缩列表
Hash --> 哈希表
SortedSet --> 压缩链表
SortedSet --> 跳表
Set --> 哈希表
Set --> 整数数组
名称 | 查找时间复杂度 |
---|---|
哈希表 | 0(1) |
跳表 | O(logN) |
双向链表 | O(N) |
压缩列表 | O(N) |
整数数组 | O(N) |
字典
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
redis使用了两张哈希表来方便扩容时的rehash操作
在进行rehash时,为避免给服务器带来过大负担,并不是一次性将所有值rehash到另外一张表,而是通过渐进的方式,每次对字典执行添加、删除、查找或者更新操作时,将哈希表 entry 的转移操作分散在后续的每一次请求中以及定时任务中,而非一次性执行完
压缩列表
数组中的每一个元素都对应保存一个数据。和数组不同的是,压缩列表在表头有三个字段 zlbytes、zltail 和 zllen,分别表示列表长度、列表尾的偏移量和列表中的 entry 个数;压缩列表在表尾还有一个 zlend,表示列表结束
如果我们要查找定位第一个元素和最后一个元素,可以通过表头三个字段的长度直接定位
跳表
- O(N) 的空间复杂度,O(logN) 的插入、查询、删除的时间复杂度
查找时,从上层开始查找,找到对应的区间后再到下一层继续查找,类似于二分查找
这种查找数据结构跟红黑树相比:
- 插入非常快,因为不需要在插入后进行旋转
- 实现容易
- 支持无锁操作
完美跳表:所用的存储空间和查询过程,应该和二叉树是非常像的,我们会要求每一层都包含下一层一半的节点,且同一层指针跨越的节点数量是一样的
但随着元素不断增减,很难维护这样的完美跳表
引入随机性:通过 50% 的概率决策,决定是否需要继续将这个插入到更高的一层
操作复杂度
- 集合类型对单个数据实现的增删改查操作,复杂度由集合采用的数据结构决定,如 Hash 的增加查找都是O(1)
- 集合类型中的遍历操作,返回集合中的所有数据,这类操作的复杂度一般是 O(N)
- 集合类型对集合中所有元素个数的记录,复杂度为 O(1),因为这些结构中专门记录了元素的个数统计
- 还有一些特殊情况,压缩列表和双向链表都会记录表头和表尾的偏移量,所以POP PUSH 操作也为 O(1)