站長資訊網(wǎng)
推薦（免費）：redis
Redis完成數(shù)據(jù)操作的速度能達(dá)到微秒級別，Redis能有這么突出的表現(xiàn)，主要原因有兩個：
- Redis是內(nèi)存數(shù)據(jù)庫，所有操作都在內(nèi)存上完成，內(nèi)存的訪問速度本身就很快；
- Redis擁有高效的數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)。
為了實現(xiàn)key到value的快速訪問，Redis使用哈希表來存儲鍵值對，哈希桶中entry保存了指向?qū)嶋Hkey和value的指針，即使值是一個集合，也可以通過value指針查找到。
當(dāng)哈希表中數(shù)據(jù)越來越多后，會出現(xiàn)哈希沖突，也就是多個key的哈希值可能對應(yīng)到同一個哈希桶中。Redis使用鏈?zhǔn)焦斫鉀Q哈希沖突，就是將同一個哈希桶中的多個元素用一個鏈表來保存，元素之間依次用指針鏈接。
如果哈希沖突越來越多，會導(dǎo)致哈希沖突鏈過長，進(jìn)而導(dǎo)致查找元素耗時長、效率低。為了解決這個問題，Redis會對哈希表進(jìn)行rehash操作，將多個entry元素分散保存，減少單個哈希桶中的元素個數(shù)，從而減少單個桶中的沖突。
Redis默認(rèn)使用兩個全局哈希表來進(jìn)行高效rehash，一開始默認(rèn)使用哈希表1，哈希表2不分配空間，當(dāng)數(shù)據(jù)不斷增多時，redis通過如下步驟進(jìn)行rehash：
- 給哈希表2分配更大的空間
- 把哈希表1中的數(shù)據(jù)拷貝到哈希表2中
- 釋放哈希表1的空間，留作下一次rehash擴容備用
但是第2步如果一次性將大量數(shù)據(jù)進(jìn)行拷貝，可能會造成Redis線程阻塞，無法服務(wù)其他請求，所以Redis采用了漸進(jìn)式rehash，就是每處理一個請求，順帶將這個索引位置上的所有entry進(jìn)行拷貝。
對于String類型的value來說，找到哈希桶就可以直接進(jìn)行CRUD操作了，而對于集合來說，通過全局哈希表找到對應(yīng)的哈希桶后，在集合中再進(jìn)行CRUD。集合的操作效率與底層數(shù)據(jù)結(jié)構(gòu)和操作復(fù)雜度有關(guān)。
- 單元素操作是基礎(chǔ)，操作復(fù)雜度為O(1)；
- Hash：HGET、HSET、HDEL；
- Set類型的SADD、SREM、SRANDMEMBER等。
- 范圍操作非常耗時，操作復(fù)雜度為O(N)。
- Hash：HGETALL;
- Set：SMEMBERS;
- List：LRANGE
- ZSet：ZRANGE
- 統(tǒng)計操作通常高效，操作復(fù)雜度為O(1)。
- 例外情況只有幾個，操作復(fù)雜度為O(1)。
- List：LPOP、RPOP、LPUSH、RPUSH
