一、Redis数据结构：
SDS
SDS（动态字符串）包含字符数组buf[]，字符数组现有长度len，字符数组分配空间的长度alloc，SDS类型flags。
总结：
1、C语言中使用char*实现字符串的不足，主要是因为使用“\0”表示字符串结束，操作时需遍历字符串，效率不高，并且无法完整表示包含“\0”的数据，因而这就无法满足Redis的需求。
2、Redis专门设计了SDS数据结构，在字符数组的基础上，增加了字符数组长度和分配空间大小等元数据。这样一来，需要基于字符串长度进行的追加、复制、比较等操作，就可以直接读取元数据，效率也就提升了。而且，SDS不通过字符串中的“\0”字符判断字符串结束，而是直接将其作为二进制数据处理，可以用来保存图片等二进制数据。
3、SDS中是通过设计不同SDS类型来表示不同大小的字符串，并使用attribute ((packed))这个编程小技巧，来实现紧凑型内存布局，达到节省内存的目的。
Hash
哈希冲突：Redis采用了链式哈希，在不扩容哈希表的前提下，将具有相同哈希值的数据链接起来，以便这些数据在表中仍然可以被查询到。
（但随着链表长度的增加，Hash表在一个位置上查询哈希项的耗时就会增加，所以引用了rehash）
Rehash指扩大Hash表空间，用一个hash表（ht[0]）复制到另一个hash表（ht[1]），然后将ht[1]设置为ht[0]
rehash开销：Redis实现了渐进式rehash设计，进而缓解了rehash操作带来的额外开销对系统的性能影响。
1、 rehash扩容扩多大？
默认是原来空间的2倍
2、为什么有rehash开销？（为什么要实现渐进式rehash？）
Hash表执行rehash时，需将键从原来的位置拷贝到新的位置。而在键拷贝时，由于Redis主线程无法执行其他请求，所以键拷贝会阻塞主线程，这样就会产生rehash开销。
3、渐进式rehash如何实现？
Redis并不会一次性把当前Hash表中的所有键，都拷贝到新位置，而是会分批拷贝，每次的键拷贝只拷贝Hash表中一个bucket中的哈希项
4、什么时候触发rehash？
hash表承载的元素个数超过了它本身的大小或者hash表承载的元素个数是它本身大小的5倍
Sorted Set
Sorted Set采用跳表和哈希表
跳表高效支持范围查询、哈希表高效支持单点查询。
跳表是一个多层的有序链表，每一层也是由多个结点通过指针连接起来的。
Ziplist、quicklist、Listpack
Ziplist不足：ziplist中元素个数多了，它的查找效率就会降低。而且如果在ziplist里新增或修改数据，ziplist占用的内存空间还需要重新分配；更糟糕的是，ziplist新增某个元素或修改某个元素时，可能会导致后续元素的prevlen占用空间都发生变化，从而引起连锁更新问题，导致每个元素的空间都要重新分配，这就会导致ziplist的访问性能下降。
Quicklist：quicklist结构在ziplist基础上，使用链表将ziplist串联起来，链表的每个元素就是一个ziplist。这种设计减少了数据插入时内存空间的重新分配，以及内存数据的拷贝。同时，quicklist限制了每个节点上ziplist的大小，一旦一个ziplist过大，就会采用新增quicklist节点的方法。
Listpack：该结构沿用了ziplist紧凑型的内存布局，把每个元素都紧挨着放置。listpack中每个列表项不再包含前一项的长度了，因此当某个列表项中的数据发生变化，导致列表项长度变化时，其他列表项的长度是不会受影响的，因而这就避免了ziplist面临的连锁更新问题。
Redis数据结构
链表
Redis链表为双向无环链表
Redis中的list是个双向无环链表，并使用了一个list来持有链表
双向：链表节点带有前驱、后继指针获取某个节点的前驱、后继节点的时间复杂度为0(1)。
无环: 链表为非循环链表表头节点的前驱指针和表尾节点的后继指针都指向NULL，对链表的访问以NULL为终点。
带表头指针和表尾指针：通过list结构中的head和tail指针，获取表头和表尾节点的时间复杂度都为O(1)。
带链表长度计数器:通过list结构的len属性获取节点数量的时间复杂度为O(1)。
多态：链表节点使用void*指针保存节点的值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用来保存各种不同类型的值。
字典
Redis字典使用散列表最为底层实现，一个散列表里面有多个散列表节点，每个散列表节点就保存了字典中的一个键值对。
Redis如何解决散列冲突
链式哈希和rehash
链式哈希：在不扩容哈希表的前提下，将具有相同哈希值的数据链接起来，以便这些数据在表中仍然可以被查询到。
Rehash：用一个hash表（ht[0]）复制到另一个hash表（ht[1]），然后将ht[1]设置为ht[0]
跳跃表
跳跃表基于链表，每层都是有序双向链表（有前进指针和后退指针）
跳跃表以空间换时间的方式提升了查找速度
Redis有序集合在节点元素较大或者元素数量较多时使用跳跃表实现
Redis的跳跃表实现由 zskiplist和 zskiplistnode两个结构组成,其中 zskiplist用于保存跳跃表信息(比如表头节点、表尾节点、长度),而zskiplistnode则用于表示跳跃表节点
Redis每个跳跃表节点的层高都是1至32之间的随机数
在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象的大小进行排序。
整数集合
整数集合是Redis自己设计的一种存储结构，集合键的底层实现之一。
整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素,在有需要时,程序会根据新添加元素的类型,改变这个数组的类型。
升级操作为整数集合带来了操作上的灵活性,并且尽可能地节约了内存。
整数集合只支持升级操作,不支持降级操作
升级指的是存储一个int64数据类型的元素，将数组中int32的元素全部都变成int64位数据类型
网友评论