Redis都有哪些底层数据结构？
有八种核心的底层数据结构。
SDS
Redis自己实现的动态字符串，SDS结构中直接存储了已使用的字符数组长度len和未使用的字符数组长度free，所以获取长度的时间复杂度是O(1)，还支持动态扩容，以及存储二进制数据。
字典
数组+链表实现的哈希表，为了避免rehash时一次性移动大量数据，底层使用了两个哈希表，后续的每次访问都会将将旧哈希表中的一部分数据移动到新的扩容后的哈希表，叫做渐进式rehash
ziplist
节省内存的紧凑型数据结构，所有的元素连续存储在一块内存里，但它有个致命的问题，叫做“连锁更新”，因为ziplist节点中记录的是上一个节点的总长度，所以上一个节点的总长度变化跨越了某个临界值（比如previous_entry_length 字段从1字节扩展为5字节）可能使其后面的所有元素内部都要重新编码，性能急剧下降。
quicklist
为了解决压缩列表的问题，Redis 后来设计了 quicklist。这个设计思路很聪明，它把 ziplist 拆分成小块，然后用双向链表把这些小块串起来。这样既保持了 ziplist 节省内存的优势，又避免了连锁更新的问题，因为每个小块的 ziplist 都不会太大。
listpack
为了解决ziplist的连锁更新问题，listpack中每个节点只记录自己的长度而不记录上一个节点的长度，前面节点的总长度变化不会触发后面节点的长度发生变化，不会引发连锁反应。
skiplist
跳表skiplist主要存在于有序集合ZSet中，通过多层指针实现快速查找，平均时间复杂度是O(logn)，支持范围查询
intset
整数集合，当Set中都是整数且数量较少时使用，内部是一个有序数组，查找时使用二分法。
LinkedList
早期版本使用，后来被quicklist取代，因为内存不连续，影响CPU缓存性能
简单介绍下链表？
Redis的LinkedList是一个双向无环结构，类似于java的LinkedList。
节点由 listNode 表示，每个节点都有指向其前置节点和后置节点的指针，头节点的前置和尾节点的后置均指向 null。
关于整数集合再详细说说
整数集合是 Redis 中一个非常精巧的数据结构，当一个 Set 只包含整数元素，并且数量不多时，默认不超过 512 个，Redis 就会用 intset 来存储这些数据。
有三种编码方式，16位、32位、64位，有类型升级机制，会根据存储的整数大小动态调整编码。比如原来存的都是小整数，用 16 位编码就够了，但突然插入了一个很大的数，超出了 16 位的范围，这时整个数组会升级到 32 位编码。
当然了，这种升级是有代价的，因为需要重新分配内存并复制数据，并且是不可逆的，但它的好处是可以节省内存空间，特别是在存储大量小整数时。
另外，所有元素在数组中按照从小到大的顺序排列，这样就可以使用二分查找来定位元素，时间复杂度为 O(log N)。
说一下ZSet的底层原理？
有两种底层实现机制：压缩列表和跳表。
压缩列表
当存储的元素数量少于128个，每个元素的大小小于64字节的时候，使用压缩列表。
使用压缩列表时，每个元素会使用两个列表中的节点表示，前一个存储元素值，后一个存储score
所有元素按分值从小到大有序排列，小的放在靠近表头的位置，大的放在靠近表尾的位置。
skiplist
当元素数量较多或元素本身较大时，会采用skiplist的编码方式，这个设计同时使用了两种数据结构：跳表和字典（哈希表）。
跳表按分数排序所有元素，通过多层链表实现，支持范围查询，平均时间复杂度为 O(log N)。而哈希表则用来存储成员和分值的映射关系，查找时间复杂度为 O(1)。
虽然同时使用两种结构，但它们会通过指针来共享相同元素的成员和分值，因此不会浪费额外的内存。
为什么Redis7.0要用listpack代替ziplist？
主要是为了解决压缩列表的一个核心问题——连锁更新。在压缩列表中，每个节点都需要记录前一个节点的长度信息。
当插入或删除一个节点时，如果这个操作导致某个节点的长度发生了变化，那么后续的节点可能都需要更新它们存储的"前一个节点长度"字段。如果前一个节点过长甚至可能会扩展字段的位数。
而 listpack 的设计理念完全不同。它让每个节点只记录自己的长度信息，不再依赖前一个节点的长度。这样就从根本上避免了连锁更新的问题。
连锁更新是怎么发生的？
比如说我们有一个压缩列表，其中有几个节点的长度都是 253 个字节。在 ziplist 的编码中，如果前一个节点的长度小于 254 字节，我们只需要 1 个字节来存储这个长度信息。
但如果在这些节点前面插入一个长度为 254 字节的节点，那么原来只需要 1 个字节存储长度的节点现在需要 5 个字节来存储长度信息。这就会导致后续所有节点的长度信息都需要更新，因为大家的长度都是253。
研究过Redis字典源码吗？
有，Redis字典分为三层，最外层是一个dict结构，包含两个哈希表ht[0]和ht[1]，然后是哈希表结构dictht，每个dictht里有一个dictEntry，是数组+链表的结构。
字典最大的特点是渐进式rehash，扩容时的数据重新分布不是一次性完成的，而是随着旧字典中数据的访问而分批复制移动。
当旧哈希表的元素数量达到阈值的时候，Redis会为ht[1]分配新的空间，通常是ht[0]的两倍，然后将ht[0]中的中的rehashidx设置为0，代表正在进行rehash的桶索引。
接下来每次操作旧字典的时候，都会将rehashidx指向的桶中的所有键值对从ht[0]复制移动到ht[1]中，然后rehashidx递增，直到整个ht[0]迁移完毕，此时会交换h[0]和h[1]的角色。
rehash期间查找的时候会先在h[0]中查找，如果没有找到再从h[1]中查找，新元素则直接插入h[1]
遇到哈希冲突怎么办？
通过链地址法解决，哈希表中的每个槽位是一个链表的头指针，当多个键的哈希值映射到同一个槽位时，这些键会以链表的形式利用头插法串联起来。
你了解跳表吗？
跳表是一种非常巧妙的数据结构，它在有序链表的基础上建立了多层索引，最底层包含所有数据，每往上一层，节点数量就减少一半。
它的核心思想是"用空间换时间"，通过多层索引来跳过大量节点不断缩小范围，从而提高查找效率。
怎么往跳表中插入节点呢？
从顶层开始，在每层向右移动直到下个节点的值大于要插入的值，用一个 update 数组记录每一层应该插入的位置的前驱节点，然后下降到下一层。
插入到最底层后，接下来随机生成新节点的层数。通常用一个循环，每次有 50% 的概率继续往上，直到随机失败或达到最大层数限制。利用之前记录的 update 数组，将新节点插入到正确位置，然后更新前后指针的连接关系。
zset为什么要使用跳表？
第一，跳表天然就是有序的数据结构，查找、插入和删除都能保持 O(log n) 的时间复杂度。
第二，跳表支持范围查询，找到起始位置后可以直接沿着底层链表顺序遍历，满足 ZRANGE 按排名获取元素，或者 ZRANGEBYSCORE 按分值范围获取元素。
跳表是如何定义的？
本质上是一个多层链表，最底层是一个包含所有元素的有序链表，之上的每一层作为索引链表，包含了下一层的部分节点，层数通过随机算法确定，理论上可以无限高。
跳表节点skiplistNode包含分值score、成员对象obj、一个后退指针backward，以及一个层级数组level。每个层级数组里有前进指针forward和跨度信息（到下一个节点的距离）span
跳表本身包含头尾节点，节点总数length和当前最大层级level
跨度信息span有什么用？
span 记录的是当前节点 forward 指针所跨越的底层节点的数量，从顶层的rank = 0开始，通过累加搜索过程中的span，快速找到ZSet中某个分值的排名，而无需遍历底层数组。
压缩列表了解吗？
压缩列表是 Redis 为了节省内存而设计的一种紧凑型数据结构，它会把所有数据连续存储在一块内存当中。
ziplist的头部信息包含总字节数zlbytes、最后一个节点的偏移量zltail、总节点数量zllen、实际数据区域entryX。
当 list、hash 和 set 的数据量较小且值都不大时，底层会使用压缩列表来实现。
通常情况在，每个节点包含三个部分：前一个节点的长度、编码类型和实际的数据。
前一个节点的长度是为了支持从后往前遍历；当前一个节点的长度小于 254 字节时，使用 1 字节存储；否则用 5 字节存储，第一个字节设置为 254，后四个字节存储实际长度。
但压缩列表有个致命问题，就是连锁更新。当插入或删除节点导致某个节点长度发生变化时，可能会影响后续所有节点存储的“前一个节点长度”字段，最坏情况下时间复杂度会退化到 O(n²)。
ziplist的节点数量会大于65535吗？
不会。
Zllen 字段的类型是 uint16_t，最大值为 65535，也就是 2 的 16次方，所以压缩列表的节点数量不会超过 65535。
当节点数量小于 65535 时，该字段会存储实际的数量；否则该字段就固定为 65535，实际存储的数量需要逐个遍历节点来计算。
ziplist的编码类型了解多少？
ziplist每个节点的编码类型都可以不同，主要分为字符串编码和整数编码两大类，目的是用最少的字节存储数据。
| 编码 | 长度 | 描述 |
|---|---|---|
| 11000000 | 1字节 | int16_t类型整数，2 字节 |
| 11010000 | 1字节 | int32_t类型整数，4 字节 |
| 11100000 | 1字节 | int64_t类型整数，8 字节 |
| 11110000 | 1字节 | 24位有符号整数 ，3 字节 |
| 1111xxxx | 1字节 | 数据范围在[0-12]，数据包含在编码中 |
| 编码 | 长度 | 描述 |
|---|---|---|
| 00pppppp | 1字节 | 0-63 字节的字符串 |
| 01pppppp qqqqqqqq | 2字节 | 64-16383字节的字符串 |
| 10______ qqqqqqqq rrrrrrrr ssssssss tttttttt | 5字节 | 16384-4294967295字节的字符串 |
quicklist了解吗？
结合了压缩列表和双向链表的优点，quicklist 通过将 List 拆分为多个小的 ziplist，再通过指针链接成一个双向链表，巧妙的解决了连锁更新问题。这样既保留了压缩列表的内存紧凑性，又减少了双向链表指针的数量，进一步降低了内存开销。
quicklist每个节点的元素数量或大小是可配置的，默认每个节点是8KB的大小。
如果想进一步节省内存，quicklist支持对中间节点进行LZF压缩。
LZF压缩了解吗？
是一种无损压缩算法，用来减少数据占用的内存，核心思想是通过查找重复元素来实现压缩，通过一个滑动窗口来查找重复的字节序列，将这些序列替换为更短的引用。
