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(n2)。
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壓縮了解嗎？
是一種無損壓縮算法，用來減少數據占用的內存，核心思想是通過查找重復元素來實現壓縮，通過一個滑動窗口來查找重復的字節序列，將這些序列替換為更短的引用。
