Redis“快”的重要表現(xiàn)：它接收到一個鍵值對操作后柬焕，能以微秒級別的速度找到數(shù)據(jù)沃饶，并快速完成操作。能夠這么優(yōu)秀的原因一方面石抡，這是因為它是內(nèi)存數(shù)據(jù)庫檐嚣，所有操作都在內(nèi)存上完成，內(nèi)存的訪問速度本身就很快啰扛。另一方面嚎京，這要歸功于它的數(shù)據(jù)結(jié)構(gòu)。
底層數(shù)據(jù)結(jié)構(gòu)一共有 6 種隐解，分別是簡單動態(tài)字符串鞍帝、雙向鏈表、壓縮列表煞茫、哈希表帕涌、跳表和整數(shù)數(shù)組。
String 類型的底層實現(xiàn)只有一種數(shù)據(jù)結(jié)構(gòu)续徽，也就是簡單動態(tài)字符串宵膨。而 List、Hash炸宵、Set 和 Sorted Set 這四種數(shù)據(jù)類型辟躏，都有兩種底層實現(xiàn)結(jié)構(gòu)。通常情況下土全，我們會把這四種類型稱為集合類型捎琐，它們的特點是一個鍵對應了一個集合的數(shù)據(jù)。
鍵和值用什么結(jié)構(gòu)組織裹匙？
為了實現(xiàn)從鍵到值的快速訪問瑞凑，Redis 使用了一個哈希表來保存所有鍵值對。
一個哈希表概页，其實就是一個數(shù)組籽御，數(shù)組的每個元素稱為一個哈希桶。所以惰匙，我們常說技掏，一個哈希表是由多個哈希桶組成的，每個哈希桶中保存了鍵值對數(shù)據(jù)项鬼。哈希桶中的元素保存的并不是值本身哑梳，而是指向具體值的指針。
這個哈希表保存了所有的鍵值對绘盟，所以鸠真，我也把它稱為全局哈希表悯仙。
注意： Redis 中寫入大量數(shù)據(jù)后，可能發(fā)現(xiàn)操作有時候會突然變慢了吠卷。哈希表的沖突問題和 rehash 可能帶來的操作阻塞锡垄。
為什么哈希表操作變慢了？
哈希沖突是不可避免的問題祭隔。這里的哈希沖突偎捎，也就是指，兩個 key 的哈希值和哈希桶計算對應關系時序攘，正好落在了同一個哈希桶中茴她。
Redis 解決哈希沖突的方式，就是鏈式哈希程奠。鏈式哈希也很容易理解丈牢，就是指同一個哈希桶中的多個元素用一個鏈表來保存，它們之間依次用指針連接瞄沙。如圖所示
但是己沛，這樣的話，哈希沖突鏈上的元素只能通過指針逐一查找再操作距境，隨著數(shù)量越來越多申尼，性能將會越來越差，為了解決這個問題垫桂，Redis 會對哈希表做 rehash 操作师幕。
為了使 rehash 操作更高效，Redis 默認使用了兩個全局哈希表：哈希表 1 和哈希表 2诬滩。一開始霹粥，當你剛插入數(shù)據(jù)時，默認使用哈希表 1疼鸟，此時的哈希表 2 并沒有被分配空間后控。隨著數(shù)據(jù)逐步增多，Redis 開始執(zhí)行 rehash空镜，這個過程分為三步：
給哈希表 2 分配更大的空間浩淘，例如是當前哈希表 1 大小的兩倍；
把哈希表 1 中的數(shù)據(jù)重新映射并拷貝到哈希表 2 中吴攒；
釋放哈希表 1 的空間张抄。
但是這個過程設計了大量的數(shù)據(jù)拷貝，如果一次性把哈希表 1 中的數(shù)據(jù)都遷移完舶斧，會造成 Redis 線程阻塞欣鳖。為了避免這個問題，Redis 采用了漸進式 rehash茴厉。主要是將上述第二步的步驟修改為：
- Redis 仍然正常處理客戶端請求泽台，每處理一個請求時，從哈希表 1 中的第一個索引位置開始矾缓，順帶著將這個索引位置上的所有 entries 拷貝到哈希表 2 中怀酷；等處理下一個請求時，再順帶拷貝哈希表 1 中的下一個索引位置的 entries嗜闻。
不同操作的復雜度
單元素操作是基礎蜕依；
范圍操作非常耗時；
統(tǒng)計操作通常高效琉雳；
例外情況只有幾個样眠。
第一，單元素操作翠肘，是指每一種集合類型對單個數(shù)據(jù)實現(xiàn)的增刪改查操作檐束。這些操作的復雜度由集合采用的數(shù)據(jù)結(jié)構(gòu)決定，例如束倍，HGET被丧、HSET 和 HDEL 是對哈希表做操作，所以它們的復雜度都是 O(1)绪妹；Set 類型用哈希表作為底層數(shù)據(jù)結(jié)構(gòu)時甥桂，它的 SADD、SREM邮旷、SRANDMEMBER 復雜度也是 O(1)黄选。
第二，范圍操作婶肩，是指集合類型中的遍歷操作糕簿，可以返回集合中的所有數(shù)據(jù)，比如 Hash 類型的 HGETALL 和 Set 類型的 SMEMBERS狡孔，或者返回一個范圍內(nèi)的部分數(shù)據(jù)懂诗，比如 List 類型的 LRANGE 和 ZSet 類型的 ZRANGE。這類操作的復雜度一般是 O(N)苗膝，比較耗時殃恒，我們應該盡量避免。
第三辱揭，統(tǒng)計操作离唐，是指集合類型對集合中所有元素個數(shù)的記錄，例如 LLEN 和 SCARD问窃。這類操作復雜度只有 O(1)亥鬓，這是因為當集合類型采用壓縮列表、雙向鏈表域庇、整數(shù)數(shù)組這些數(shù)據(jù)結(jié)構(gòu)時嵌戈，這些結(jié)構(gòu)中專門記錄了元素的個數(shù)統(tǒng)計覆积，因此可以高效地完成相關操作。
第四熟呛，例外情況宽档，是指某些數(shù)據(jù)結(jié)構(gòu)的特殊記錄，例如壓縮列表和雙向鏈表都會記錄表頭和表尾的偏移量庵朝。這樣一來吗冤，對于 List 類型的 LPOP、RPOP九府、LPUSH椎瘟、RPUSH 這四個操作來說，它們是在列表的頭尾增刪元素侄旬，這就可以通過偏移量直接定位肺蔚，所以它們的復雜度也只有 O(1)，可以實現(xiàn)快速操作勾怒。
