詳細分析Redis的資料結構與資料操作

建議（免費）：redis

#Redis完成資料操作的速度能達到微秒級別，Redis能有這麼突出的表現，主要原因有兩個：

• Redis是記憶體資料庫，所有操作都在記憶體上完成，記憶體的存取速度本身就很快；
• Redis擁有高效率的資料型別和資料結構。

為了實現key到value的快速訪問，Redis使用哈希表來儲存鍵值對，哈希桶中entry保存了指向實際key和value的指針，即使值是一個集合，也可以透過value指標查找到。

當雜湊表中資料越來越多後，會出現雜湊衝突，也就是多個key的雜湊值可能對應到同一個雜湊桶中。 Redis使用鍊式雜湊來解決雜湊衝突，就是將同一個雜湊桶中的多個元素用一個鍊錶來保存，元素之間依序用指標連結。

如果雜湊衝突越來越多，會導致雜湊衝突鏈過長，進而導致查找元素耗時長、效率低。為了解決這個問題，Redis會對雜湊表進行rehash操作，將多個entry元素分散保存，減少單一雜湊桶中的元素個數，從而減少單一桶中的衝突。

Redis預設使用兩個全域雜湊表來進行高效能rehash，一開始預設使用雜湊表1，雜湊表2不分配空間，當資料不斷增加時，redis透過下列步驟進行rehash：

1. 給哈希表2分配更大的空間
2. 把哈希表1中的資料拷貝到哈希表2中
3. 釋放哈希表1的空間，留作下一次rehash擴容備用

但是第2步如果一次性將大量資料進行拷貝，可能會造成Redis線程阻塞，無法服務其他請求，所以Redis採用了漸進式rehash，就是每處理一個請求，順帶將這個索引位置上的所有entry進行拷貝。

對於String類型的value來說，找到哈希桶就可以直接進行CRUD操作了，而對於集合來說，透過全域哈希表找到對應的哈希桶後，在集合中再進行CRUD。集合的操作效率與底層資料結構和操作複雜度有關。

1. 單一元素運算是基礎，運算複雜度為O(1)；
   • Hash：HGET、HSET、HDEL；
   • Set類型的SADD、SREM、SRANDMEMBER等。
2. 範圍操作非常耗時，操作複雜度為O(N)。
   • Hash：HGETALL;
   • Set：SMEMBERS;
   • #List：LRANGE
   • ZSet：ZRANGE

#####################統計操作通常高效，操作複雜度為O(1)。 ######例外情況只有幾個，操作複雜度為O(1)。 ######List：LPOP、RPOP、LPUSH、RPUSH#############

以上是詳細分析Redis的資料結構與資料操作的詳細內容。更多資訊請關注PHP中文網其他相關文章！