Redis常用数据结构

主要有

String List Set Zset Hash BitMap Hyperloglog Stream Geo

String:

Redis最常用的一种数据结构,Sting类型的数据存储结构有三种int、embstr、raw

1.int:用来存储long以下的整形

embstr raw 都是用来存字符串，其中小于44字节的字符串用embstr存 大于的用raw存

二者的底层都用的SDS(简单动态字符串) 底层就是一个char[]+length+free

相比c语言自己的字符串 有几个优势

1. 获取字符长度不用再遍历字符，直接返回length

2. 可以动态扩缩容，不会出现缓冲区溢出，扩容时会多分配一些(预分配策略)，缩容时只是用free记录空闲的长度

3. 二进制安全(c语言遇到\0时会认为字符串结束)

embstr会把redisObject相关的结构和sds存在一块连续的内存空间 节省内存

raw 是分开存储

List

在redis3.2之前，redis存list是通过ziplist+linkedlist 3.2之后用的是quicklist

3.2之前:

当元素个数较少(<512且每个元素的长度小于64字节)时  用ziplist(压缩列表)

用一整块连续内存存所有的数据，与普通数组不同的是，每个节点所占的空间并不相同，而是用多少占多数，这样更加紧凑，减少内存碎片，但是也会有一些问题

问题:1.随机访问性能差、由于每个节点的内存都不一样 所以难以随机访问

          2.可能触发连锁更新:节点中要存之前节点的长度，若是插入较大的元素，则可能引发级联更新(后面的元素更新pre_length 又导致后续的节点触发更新)

linkedlist:就是个双向链表

3.2之后:quicklist:每个节点都是一个ziplist 降低了级联更新产生的影响 也保证了空间上的紧凑性

redis7之后所有的ziplist都被替换成listpack(每个节点都只记录自己的长度)

Hash

在数据个数较少时 直接用的ziplist/listpack 压根没用hash 就是按keyvalue keyvalue 紧凑存储

获取数据时压根没用哈希 而是遍历的

说是在数据量较少时 用这种紧凑的结构 即使线性遍历 可能也比哈希快 

在数据量超过某个阈值后，会用ziplist/listpack +hashtable的结构

一个字典包括两个dict(渐进式hash用的)

扩容机制:有负载因子=已保存节点的数量/哈希表的大小 大于等于1时 若没有生成rdb或重写aof会扩容  大于5时 不管怎么样立马扩容 小于0.1时会进行缩容

渐进式rehash:哈希表在进行扩容时会一点一点扩容，而不是一次性扩容，当需要扩容时会先把rehash标记设为0，然后生成一个两倍原来大小的表，然后对原有表的增删改查会一步一步把数据迁移到新表，当迁移完毕后再移动指针

Set

底层有两种实现 HashTable 和IntSet(有序整数集合，且元素个数小于512，通过二分查找查找元素)

ZSet

底层是大名鼎鼎的跳表 我感觉本质上就是带了多层索引的双向链表

查询的时间复杂度是logn 添加或删除元素也是logn

新增元素时每层按0.5的概率决定该层是否增加该节点的索引

查询时自上向下 一直缩小要查询的节点所在的范围

为什么不用红黑树?

1.红黑树实现复杂、难以维护

2.红黑树要实现范围查询要回溯

为什么不用B+树?

1.B+树节点占用空间大

2.B+树插入节点可能要分裂 比较复杂

3.B+树主要是为了减少树高、减少io查询  redis不需要

BitMap

就是一个位图，是一串连续的二进制数 用偏移量来定位

redis的底层 bitmap是一个char[] 在c语言中 char是一个字节 即八个比特位

用位访问的方式set某位置元素为0或1

index + pos  index代表位置第几个char上  index表示在该index内 是第几位