Redis的五种数据结构及其底层实现原理
redis的字符串类型是由一种叫做简单动态字符串(SDS)的数据类型来实现
SDC和C语言字符串的区别:
1:SDS保存了字符串的长度,而C语言不保存,只能遍历找到第一个\0的结束符才能确定字符串的长度
2:修改SDS,会检查空间是否足够,不足会先扩展空间,防止缓冲区溢出,C字符串不会检查
3:SDS的预分配空间机制,可以减少为字符串重新分配空间的次数
备注:重新分配空间方式,小于1M的数据 翻倍+1,例如:13K+13K+1,如果大于1M,每次多分配1M,例如:10M+1M+1,如果字符串变短,并不会立即缩短,而是采用惰性空间释放,有专门的API可以释放多余空间
hash结构里其实是一个字典,有许多的键值对
redis的哈希表是一个dictht结构体:
哈希表节点的结构体如下:
hash算法:
当要将一个新的键值对添加到字典里面时, 程序需要先根据键值对的键计算出哈希值和索引值, 然后再根据索引值, 将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
hash冲突解决方式:链表法,后入的放到最前面
rehash:
键值数据量变动时,时为了让哈希表的负载因子(load factor)维持在一个合理的范围之内, 当哈希表保存的键值对数量太多或者太少时, 程序需要对哈希表的大小进行相应的扩展或者收缩。
如果是扩充,新数组的空间大小为 大于2*used的2的n次方,比如:used=5,则去大于10的第一个2的n次方,为16
如果是缩小,新数组的空间大小为第一个不大于used的2的n次方,比如:used=5,则新大小为4
redis的list列表是使用双向链表来实现的
···
typedef struct listNode {
struct listNode * pre; //前置节点
struct listNode * next; //后置节点
void * value; //节点的值
}
typedef struct list {
listNode *head; //表头节点
listNode tail; //表尾节点
unsigned long len; //链表所包含的节点数量
void ( dup) (void ptr); //节点值赋值函数 这里有问题
void ( free) (void ptr); //节点值释放函数
int ( match) (void *ptr, void *key) //节点值对比函数
}
···
1:有序集合的底层实现之一是跳表, 除此之外跳表它在 Redis 中没有其他应用。
2:整数集合(intset)是集合键的底层实现之一: 当一个集合只包含整数值元素, 并且这个集合的元素数量不多时, Redis 就会使用整数集合作为集合键的底层实现。
3:数据少是,使用ziplist(压缩列表),占用连续内存,每项元素都是(数据+score)的方式连续存储,按照score从小到大排序。ziplist为了节省内存,每个元素占用的空间可以不同,对于大数据(long long),就多用一些字节存储,而对于小的数据(short),就少用一些字节来存储。因此查找的时候需要按顺序遍历。ziplist省内存但是查找效率低。
无序集合可以用整数集合(intset)或者字典实现
Redis的5.0版本中,放出一个新的数据结构Stream。其实也是一个队列,没一个不同的key对应的是不同的队列,没个队列的元素,也就是消息,都有一个msgid,并且需要保证msgid是严格递增的。在Stream当中,消息是默认持久化的,即便是Redis重启,也能够读取到信息。
Stream的多播,与其它队列系统相似,对不同的消费者,也有消费者Group这样的概念,不同的消费组,可以消费通一个消息,对于不同的消费组,都维护一个Idx下标,表示这一个消费群组费到了哪里,每次进行消费,都会更新一下这个下标,往后面一位进行偏移。
跳跃表是一种有序数据结构,它通过在每个节点中维持多个指向其它节点的指针,从而大道快速访问节点的目的,具有以下性质:
1:有很多层结构组成
2:每一层都是一个有序的链表,排列顺序为由高到低,都至少包含两个链表节点,分别是前面的head节点和后面的nil节点
3:最底层的链表包含了所有的元素
4:如果一个元素出现在某一层的链表中,那么在该层之下的链表也全部都会出现
5:链表中的每个节点都包含两个指针,一个指向同一层的下一个链表节点,另一个指向下一层的通一个链表节点
多个跳跃表节点构成一个跳跃表
1:搜索,从最高层的链表节点开始,如果比当前节点要大和比当前层的下一个节点要小,那么则往下找,也及时和当前层的下一层的节点下一个节点
2:插入,首先确定插入的层数,有一种方法是抛一个硬币,如果是正面就累加,直到遇到反面为止,最后记录正面的次数作为插入的层数,当确定插入的层数K后,则需要将新元素插入从底层到K层
3:删除,在各个层中找到包含指定值得节点,然后将节点从链表中删除即可,如果删除以后只剩下头尾两个节点,则删除这一层。
整数集合是Redis用于保存整数值集合的抽象数据类型,它可以保存int16_t、int32_t、int64_t的整数值,并且保证集合中不会出现重复元素。
整数集合的每个元素都是contents数组的一个数据项,他们按照从小到大的顺序排列,并且不包含任何重复项。
length属性记录了contents数组的大小。
需要注意的是虽然contents数组声明为int8_t类型,但是实际上contents数组并不保存任何int8_t类型的值,其真正类型由encoding来决定。
压缩列表(ziplist)是Redis为了节省内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型数据结构,一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或一个整数值。
压缩列表的原理:压缩列表并不是对数据利用某种算法进行压缩的,而是将数据按照一定规则编码在一块连续的内存区域,目的是节省内存。
压缩列表的每个节点构成如下: