bat 连续读取两行_Redis底层数据结构解析(BAT大厂必问)
Redis是一個key-value存儲系統(tǒng)，現(xiàn)在在各種系統(tǒng)中的使用越來越多，大部分情況下是因為其高性能的特性，被當做緩存使用。Redis由于其豐富的數(shù)據(jù)結構也可以被應用到其他場景。Redis是一個K-V的非關系型數(shù)據(jù)庫（NoSQL），常見的NoSQL數(shù)據(jù)庫有：K-V數(shù)據(jù)庫如Redis、Memcached，列式數(shù)據(jù)庫如大數(shù)據(jù)組件HBase，文檔數(shù)據(jù)庫如mogoDB。Redis應用廣泛，尤其是被作為緩存使用。
Redis的具有很多優(yōu)勢：
（1）讀寫性能高--100000次/s以上的讀速度，80000次/s以上的寫速度；
（2）K-V，value支持的數(shù)據(jù)類型很多：字符串(String)，隊列（List）,哈希（Hash），集合（Sets），有序集合（Sorted Sets）5種不同的數(shù)據(jù)類型。
（3）原子性，Redis的所有操作都是單線程原子性的。
（4）特性豐富--支持訂閱-發(fā)布模式，通知、設置key過期等特性。
（5）在Redis3.0 版本引入了Redis集群，可用于分布式部署。
有需要Redis大廠面試題的小伙伴點擊這里
IT架構師luke：Redis面試題（BAT大廠真題）?zhuanlan.zhihu.comRedis數(shù)據(jù)類型及其底層實現(xiàn)方式
Redis是由C語言編寫的。Redis支持5種數(shù)據(jù)類型，以K-V形式進行存儲，K是String類型的，V支持5種不同的數(shù)據(jù)類型，分別是：string，list，hash，set，sorted set，每一種數(shù)據(jù)結構都有其特定的應用場景。從內部實現(xiàn)的角度來看是如何更好的實現(xiàn)這些數(shù)據(jù)類型。Redis底層數(shù)據(jù)結構有以下數(shù)據(jù)類型：簡單動態(tài)字符串（SDS），鏈表，字典，跳躍表，整數(shù)集合，壓縮列表，對象。接下來，就探討一下Redis是怎么通過這些數(shù)據(jù)結構來實現(xiàn)value的5種類型的。
簡單動態(tài)字符串（simple dynamic string SDS）
String的數(shù)據(jù)類型是由SDS實現(xiàn)的。Redis并沒有采用C語言的字符串表示，而是自己構建了一種名為SDS的抽象類型，并將SDS作為Redis的默認字符串表示。
redis>SET msg "hello world"
OK
上邊設置key=msg，value=hello world的鍵值對，它們的底層存儲是：鍵（key）是字符串類型，其底層實現(xiàn)是一個保存著“msg”的SDS。值（value）是字符串類型，其底層實現(xiàn)是一個保存著“hello world”的SDS。
注意：SDS除了用于實現(xiàn)字符串類型，還被用作AOF持久化時的緩沖區(qū)。
SDS的定義為：
/*
* 保存字符串對象的結構
*/
struct sdshdr {
// buf 中已占用空間的長度
int len;
// buf 中剩余可用空間的長度
int free;
// 數(shù)據(jù)空間
char buf[];
};
為什么要使用SDS：
我們一定會思考，redis為什么不使用C語言的字符串而是費事搞一個SDS呢，這是因為C語言用N+1的字符數(shù)組來表示長度為N的字符串，這樣做在獲取字符串長度，字符串擴展等操作方面效率較低，并且無法滿足redis對字符串在安全性、效率以及功能方面的要求。
獲取字符串長度（SDS O（1））
在C語言字符串中，為了獲取一個字符串的長度，必須遍歷整個字符串，時間復雜度為O(1)，而SDS中，有專門用于保存字符串長度的變量，所以可以在O（1）時間內獲得。
防止緩沖區(qū)溢出
C字符串，容易導致緩沖區(qū)溢出，假設在程序中存在內存緊鄰的字符串s1和s2，s1保存redis，s2保存MongoDB，如下圖：
如果我們現(xiàn)在將s1 的內容修改為redis cluster，但是又忘了重新為s1 分配足夠的空間，這時候就會出現(xiàn)以下問題：
因為s1和s2是緊鄰的，所以原本s2 中的內容已經(jīng)被S1的內容給占領了，s2 現(xiàn)在為 cluster，而不是“Mongodb”。而Redis中的SDS就杜絕了發(fā)生緩沖區(qū)溢出的可能性。
當我們需要對一個SDS 進行修改的時候，redis 會在執(zhí)行拼接操作之前，預先檢查給定SDS 空間是否足夠（free記錄了剩余可用的數(shù)據(jù)長度），如果不夠，會先拓展SDS 的空間，然后再執(zhí)行拼接操作。
減少擴展或收縮字符串帶來的內存重分配次數(shù)
當字符串進行擴展或收縮時，都會對內存空間進行重新分配。
1. 字符串拼接會產(chǎn)生字符串的內存空間的擴充，在拼接的過程中，原來的字符串的大小很可能小于拼接后的字符串的大小，那么這樣的話，就會導致一旦忘記申請分配空間，就會導致內存的溢出。
2. 字符串在進行收縮的時候，內存空間會相應的收縮，而如果在進行字符串的切割的時候，沒有對內存的空間進行一個重新分配，那么這部分多出來的空間就成為了內存泄露。
比如：字符串"redis"，當進行字符串拼接時，將redis+cluster=13，會將SDS的長度修改為13，同時將free也改為13，這意味著進行預分配了，將buffer大小變?yōu)榱?6。這是為了如果再次執(zhí)行字符串拼接操作，如果拼接的字符串長度<13,就不需要重新進行內存分配了。
通過這種預分配策略，SDS將連續(xù)增長N次字符串所需的內存重分配次數(shù)從必定N次降低為最多N次。通過惰性空間釋放，SDS 避免了縮短字符串時所需的內存重分配操作，并未將來可能有的增長操作提供了優(yōu)化。
二進制安全
C 字符串中的字符必須符合某種編碼，并且除了字符串的末尾之外，字符串里面不能包含空字符，否則最先被程序讀入的空字符將被誤認為是字符串結尾，這些限制使得C字符串只能保存文本數(shù)據(jù)，而不能保存想圖片，音頻，視頻，壓縮文件這樣的二進制數(shù)據(jù)。
但是在Redis中，不是靠空字符來判斷字符串的結束的，而是通過len這個屬性。那么，即便是中間出現(xiàn)了空字符對于SDS來說，讀取該字符仍然是可以的。
但是，SDS依然可以兼容部分C字符串函數(shù)。
鏈表
鏈表是list的實現(xiàn)方式之一。當list包含了數(shù)量較多的元素，或者列表中包含的元素都是比較長的字符串時，Redis會使用鏈表作為實現(xiàn)List的底層實現(xiàn)。此鏈表是雙向鏈表：
typedef struct listNode{
struct listNode *prev;
struct listNode * next;
void * value;
}
一般我們通過操作list來操作鏈表：
typedef struct list{
//表頭節(jié)點
listNode * head;
//表尾節(jié)點
listNode * tail;
//鏈表長度
unsigned long len;
//節(jié)點值復制函數(shù)
void *(*dup) (void *ptr);
//節(jié)點值釋放函數(shù)
void (*free) (void *ptr);
//節(jié)點值對比函數(shù)
int (*match)(void *ptr, void *key);
}
鏈表結構的特點是可以快速的在表頭和表尾插入和刪除元素，但查找復雜度高，是列表的底層實現(xiàn)之一，也因此列表沒有提供判斷某一元素是否在列表中的借口，因為在鏈表中查找復雜度高。
字典
字典，又稱為符號表（symbol table）、關聯(lián)數(shù)組（associative array）或映射（map），是一種用于保存鍵值對的抽象數(shù)據(jù)結構。
在字典中，一個鍵（key）可以和一個值（value）進行關聯(lián)，字典中的每個鍵都是獨一無二的。在C語言中，并沒有這種數(shù)據(jù)結構，但是Redis 中構建了自己的字典實現(xiàn)。
redis > SET msg "hello world"
OK
Redis本身的K-V存儲就是利用字典這種數(shù)據(jù)結構的，另外value類型的哈希表也是通過這個實現(xiàn)的。
哈希表dicy的定義為：
typedef struct dictht {
//哈希表數(shù)組
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩碼，用于計算索引值
unsigned long sizemask;
//該哈希表已有節(jié)點的數(shù)量
unsigned long used;
}
我們可以想到對比Java hashMap的實現(xiàn)方式，在dictht中，table數(shù)組的類型是：
typeof struct dictEntry{
//鍵
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
}
struct dictEntry *next;
}
我們存入里面的key 并不是直接的字符串，而是一個hash 值，通過hash 算法，將字符串轉換成對應的hash 值，然后在dictEntry 中找到對應的位置。
這時候我們會發(fā)現(xiàn)一個問題，如果出現(xiàn)hash 值相同的情況怎么辦？Redis 采用了鏈地址法來解決hash沖突。這與hashmap的實現(xiàn)類似。
注意：Redis又在dictht的基礎上，又抽象了一層字典dict，其定義為：
typedef struct dict {
// 類型特定函數(shù)
dictType *type;
// 私有數(shù)據(jù)
void *privedata;
// 哈希表
dictht ht[2];
// rehash 索引
in trehashidx;
}
type 屬性 和privdata 屬性是針對不同類型的鍵值對，為創(chuàng)建多態(tài)字典而設置的。
ht 屬性是一個包含兩個項（兩個哈希表）的數(shù)組，如圖：
解決hash沖突：采用鏈地址法來實現(xiàn)。
擴充Rehash： 隨著對哈希表的不斷操作，哈希表保存的鍵值對會逐漸的發(fā)生改變，為了讓哈希表的負載因子維持在一個合理的范圍之內，我們需要對哈希表的大小進行相應的擴展或者壓縮，這時候，我們可以通過 rehash（重新散列）操作來完成。其實現(xiàn)方式和hashmap略有不同，因為dict有兩個hash表dictht，所以它是通過這兩個dictht互相進行轉移的。
比如：
上圖這種情況，代表要進行擴容了，所以就要將ht[0]的數(shù)據(jù)轉移到ht[1]中。ht[1]創(chuàng)建為2*ht[0].size大小的，如下圖：
將ht[0]釋放，然后將ht[1]設置成ht[0]，最后為ht[1]分配一個空白哈希表：
其實上邊的擴容過程和Java 的HashMap具體的擴容實現(xiàn)方式還是挺像的。
漸進式rehash：在實際開發(fā)過程中，這個rehash 操作并不是一次性、集中式完成的，而是分多次、漸進式地完成的。采用漸進式rehash 的好處在于它采取分而治之的方式，避免了集中式rehash 帶來的龐大計算量。
漸進式rehash 的詳細步驟：
1、為ht[1] 分配空間，讓字典同時持有ht[0]和ht[1]兩個哈希表
2、在幾點鐘維持一個索引計數(shù)器變量rehashidx，并將它的值設置為0，表示rehash 開始
3、在rehash 進行期間，每次對字典執(zhí)行CRUD操作時，程序除了執(zhí)行指定的操作以外，還會將ht[0]中的數(shù)據(jù)rehash 到ht[1]表中，并且將rehashidx加一
4、當ht[0]中所有數(shù)據(jù)轉移到ht[1]中時，將rehashidx 設置成-1，表示rehash 結束
跳躍表
Redis 只在兩個地方用到了跳躍表，一個是實現(xiàn)有序集合鍵（sorted Sets），另外一個是在集群節(jié)點中用作內部數(shù)據(jù)結構。
其實跳表主要是來替代平衡二叉樹的，比起平衡樹來說，跳表的實現(xiàn)要簡單直觀的多。
跳躍表（skiplist）是一種有序數(shù)據(jù)結構，它通過在每個節(jié)點中維持多個指向其他節(jié)點的指針，從而達到快速查找訪問節(jié)點的目的。跳躍表是一種隨機化的數(shù)據(jù),跳躍表以有序的方式在層次化的鏈表中保存元素，效率和平衡樹媲美 ——查找、刪除、添加等操作都可以在O（logn）期望時間下完成。
Redis 的跳躍表 主要由兩部分組成：zskiplist（鏈表）和zskiplistNode （節(jié)點）：
typedef struct zskiplistNode{
//層
struct zskiplistLevel{
//前進指針
struct zskiplistNode *forward;
//跨度
unsigned int span;
} level[];
//后退指針
struct zskiplistNode *backward;
//分值
double score;
//成員對象
robj *obj;
}
1、層：level 數(shù)組可以包含多個元素，每個元素都包含一個指向其他節(jié)點的指針。level數(shù)組的每個元素都包含：前進指針：用于指向表尾方向的前進指針，跨度：用于記錄兩個節(jié)點之間的距離
2、后退指針：用于從表尾向表頭方向訪問節(jié)點
3、分值和成員：跳躍表中的所有節(jié)點都按分值從小到大排序（按照這個進行排序的，也就是平衡二叉樹（搜索樹的）的節(jié)點大小）。成員對象指向一個字符串，這個字符串對象保存著一個SDS值（實際存儲的值）
typedef struct zskiplist {
//表頭節(jié)點和表尾節(jié)點
structz skiplistNode *header,*tail;
//表中節(jié)點數(shù)量
unsigned long length;
//表中層數(shù)最大的節(jié)點的層數(shù)
int level;
}zskiplist;
從結構圖中我們可以清晰的看到，header，tail分別指向跳躍表的頭結點和尾節(jié)點。level 用于記錄最大的層數(shù)，length 用于記錄我們的節(jié)點數(shù)量。
跳躍表是有序集合的底層實現(xiàn)之一
主要有zskiplist 和zskiplistNode兩個結構組成
每個跳躍表節(jié)點的層高都是1至32之間的隨機數(shù)
在同一個跳躍表中，多個節(jié)點可以包含相同的分值，但每個節(jié)點的對象必須是唯一的
節(jié)點按照分值的大小從大到小排序，如果分值相同，則按成員對象大小排序
怎么使用跳表來實現(xiàn)O（logn）的增刪改查？？
其實跳表的實現(xiàn)原理，我們可以結合二分法來看。
比如上圖，我們要查找55，如果通過遍歷，則必須得從頭遍歷到最后一個才能找到，所以在數(shù)組實現(xiàn)中，我們可以使用二分法來實現(xiàn)，但是在鏈表中，我們沒辦法直接通過下標來訪問元素，所以一般我們可以用二叉搜索樹，平衡樹來存儲元素，我們知道跳表就是來替代平衡樹的，那么跳表是如何快速查詢呢？看下圖：
從上圖我們可以看到，我們通過第4層，只需一步便可找到55，另外最耗時的訪問46需要6次查詢。即L4訪問55，L3訪問21、55，L2訪問37、55，L1訪問46。我們直覺上認為，這樣的結構會讓查詢有序鏈表的某個元素更快。這種實現(xiàn)方式跟二分很相似，其時間復雜度就是O(logn)。其插入，刪除都是O（logn）。
我們可以看到，redis正是通過定義這種結構來實現(xiàn)上邊的過程，其層數(shù)最高為32層，也就是他可以存儲2^32次方的數(shù)據(jù)，其查找過程與上圖很類似。
整數(shù)集合（Intset）
《Redis 設計與實現(xiàn)》 中這樣定義整數(shù)集合：“整數(shù)集合是集合建(sets)的底層實現(xiàn)之一，當一個集合中只包含整數(shù)，且這個集合中的元素數(shù)量不多時，redis就會使用整數(shù)集合intset作為集合的底層實現(xiàn)。”
我們可以這樣理解整數(shù)集合，他其實就是一個特殊的集合，里面存儲的數(shù)據(jù)只能夠是整數(shù)，并且數(shù)據(jù)量不能過大。
typedef struct intset{
//編碼方式
uint32_t enconding;
// 集合包含的元素數(shù)量
uint32_t length;
//保存元素的數(shù)組
int8_t contents[];
}
整數(shù)集合是集合建的底層實現(xiàn)之一.
整數(shù)集合的底層實現(xiàn)為數(shù)組，這個數(shù)組以有序，無重復的范式保存集合元素，在有需要時，程序會根據(jù)新添加的元素類型改變這個數(shù)組的類型.
壓縮列表
壓縮列表是列表鍵（list）和哈希鍵（hash）的底層實現(xiàn)之一。當一個列表鍵只有少量列表項，并且每個列表項要么就是小整數(shù)，要么就是長度比較短的字符串，那么Redis 就會使用壓縮列表來做列表鍵的底層實現(xiàn)。
1、zlbytes:用于記錄整個壓縮列表占用的內存字節(jié)數(shù)
2、zltail：記錄要列表尾節(jié)點距離壓縮列表的起始地址有多少字節(jié)
3、zllen：記錄了壓縮列表包含的節(jié)點數(shù)量。
4、entryX：要說列表包含的各個節(jié)點
5、zlend：用于標記壓縮列表的末端
壓縮列表是一種為了節(jié)約內存而開發(fā)的順序型數(shù)據(jù)結構
壓縮列表被用作列表鍵和哈希鍵的底層實現(xiàn)之一
壓縮列表可以包含多個節(jié)點，每個節(jié)點可以保存一個字節(jié)數(shù)組或者整數(shù)值
添加新節(jié)點到壓縮列表，可能會引發(fā)連鎖更新操作。
如果你喜歡我寫的技術文章以及面試總結，歡迎關注收看我的視頻，并且點贊、收藏、關注我哦。
我是luke，感謝你的關注！
也可以加入到我的圈子一起學習成長哦【架構師之路】點擊鏈接申請加入圈子
架構師之路 - 知乎?www.zhihu.com總結
以上是生活随笔為你收集整理的bat 连续读取两行_Redis底层数据结构解析(BAT大厂必问)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python 日历查询系统_python
- 下一篇： python创建文件夹用什么函数_Pyt