数据结构角度解释各种数据类型差别

各种数据类型用了哪些数据结构

string 简单动态字符串 SDS(simple dynamis string)

zset 跳表 + listpack

hash 哈希表

set 整数集合 + 哈希表

list quicklist

新旧版本(Redis 3.0 和 Redis 7.0最新)涉及哪9种数据结构

SDS
双向链表
压缩列表ziplist
哈希表hash
跳表zskiplist
整数集合inset
quicklist
listpack

Redis所有的Key存储是什么数据结构，查找时间复杂度是啥

哈希表hash
O(1)

哈希表

散列函数 f(key)
数组存放记录 - 数组也称为散列表
给定表M，任意key通过f(key)直接获取表中的地址，则为哈希表

Redis的对象

struct{ type, encoding, pointer }

C语言字符串

获取长度时间复杂度O(N)
不能有'\0'所以无法保存二进制数据
字符串操作有缓冲区溢出风险

SDS

simple dynamis string 简单动态字符串

{len,alloc,flags,buf[]}

链表

Redis之中是双向链表
表头表尾节点获取时间复杂度都是O(1)
节点可以存储不同类型的值

链表因为内存不连续无法很好利用CPU缓存(数组因为内存是连续所以可以充分利用CPU缓存)

压缩列表

内存紧凑型

过多元素查询效率会降低
新增修改需要内存空间重新分配

跳表

zset对象底层用到了

zrangebyscore范围查找就是用到了跳表，而查找元素用到了哈希表

原理

跳表是链表基础上改进，号称 [多层] 的有序链表

查找复杂度是 O(logN)

struct{ []skiplistlevl{*pointer...} }

为什么用跳表而不用平衡树(AVL树\红黑树)

内存灵活
范围查找简单
经常更新消耗更小
实现难度更简单