熱門(mén)標(biāo)簽：百度地圖標(biāo)注要什么軟件 天津公司外呼系統(tǒng)軟件 中國(guó)地圖標(biāo)注公司 400電話(huà)申請(qǐng)廠(chǎng)家現(xiàn)貨 電話(huà)機(jī)器人的價(jià)格多少錢(qián)一個(gè)月 徐涇鎮(zhèn)騰訊地圖標(biāo)注 福建外呼電銷(xiāo)機(jī)器人加盟 昌德訊外呼系統(tǒng) 自己做地圖標(biāo)注需要些什么

摘要

面試時(shí)，交流有關(guān)mysql索引問(wèn)題時(shí)，發(fā)現(xiàn)有些人能夠濤濤不絕的說(shuō)出B+樹(shù)和B樹(shù)，平衡二叉樹(shù)的區(qū)別，卻說(shuō)不出B+樹(shù)和hash索引的區(qū)別。這種一看就知道是死記硬背，沒(méi)有理解索引的本質(zhì)。本文旨在剖析這背后的原理，歡迎留言探討

問(wèn)題

如果對(duì)以下問(wèn)題感到困惑或一知半解，請(qǐng)繼續(xù)看下去，相信本文一定會(huì)對(duì)你有幫助

• mysql 索引如何實(shí)現(xiàn)
• mysql 索引結(jié)構(gòu)B+樹(shù)與hash有何區(qū)別。分別適用于什么場(chǎng)景
• 數(shù)據(jù)庫(kù)的索引還能有其他實(shí)現(xiàn)嗎
• redis跳表是如何實(shí)現(xiàn)的
• 跳表和B+樹(shù)，LSM樹(shù)有和區(qū)別呢

解析

首先為什么要把mysql索引和redis跳表放在一起討論呢，因?yàn)樗麄兘鉀Q的都是同一種問(wèn)題，用于解決數(shù)據(jù)集合的查找問(wèn)題，即根據(jù)指定的key，快速查到它所在的位置（或者對(duì)應(yīng)的value）

當(dāng)你站在這個(gè)角度去思考問(wèn)題時(shí)，還會(huì)不知道B+樹(shù)索引和hash索引的區(qū)別嗎

數(shù)據(jù)集合的查找問(wèn)題

現(xiàn)在我們將問(wèn)題領(lǐng)域邊界劃分清楚了，就是為了解決數(shù)據(jù)集合的查找問(wèn)題。這一塊需要考慮哪些問(wèn)題呢

1. 需要支持哪些查找方式，單key/多key/范圍查找，
2. 插入/刪除效率
3. 查找效率（即時(shí)間復(fù)雜度）
4. 存儲(chǔ)大?。臻g復(fù)雜度）

我們看下幾種常用的查找結(jié)構(gòu)

hash

hash是key,value形式，通過(guò)一個(gè)散列函數(shù)，能夠根據(jù)key快速找到value

B+樹(shù)

B+樹(shù)是在平衡二叉樹(shù)基礎(chǔ)上演變過(guò)來(lái)，為什么我們?cè)谒惴ㄕn上沒(méi)學(xué)到B+樹(shù)和跳表這種結(jié)構(gòu)呢。因?yàn)樗麄兌际菑墓こ虒?shí)踐中得到，在理論的基礎(chǔ)上進(jìn)行了妥協(xié)。

B+樹(shù)首先是有序結(jié)構(gòu)，為了不至于樹(shù)的高度太高，影響查找效率，在葉子節(jié)點(diǎn)上存儲(chǔ)的不是單個(gè)數(shù)據(jù)，而是一頁(yè)數(shù)據(jù)，提高了查找效率，而為了更好的支持范圍查詢(xún)，B+樹(shù)在葉子節(jié)點(diǎn)冗余了非葉子節(jié)點(diǎn)數(shù)據(jù)，為了支持翻頁(yè)，葉子節(jié)點(diǎn)之間通過(guò)指針連接。

跳表

跳表是在鏈表的基礎(chǔ)上進(jìn)行擴(kuò)展的，為的是實(shí)現(xiàn)redis的sorted set數(shù)據(jù)結(jié)構(gòu)。 level0: 是存儲(chǔ)原始數(shù)據(jù)的，是一個(gè)有序鏈表，每個(gè)節(jié)點(diǎn)都在鏈上 level0+: 通過(guò)指針串聯(lián)起節(jié)點(diǎn)，是原始數(shù)據(jù)的一個(gè)子集，level等級(jí)越高，串聯(lián)的數(shù)據(jù)越少，這樣可以顯著提高查找效率，

總結(jié)

數(shù)據(jù)結(jié)構(gòu)	實(shí)現(xiàn)原理	key查詢(xún)方式	查找效率	存儲(chǔ)大小	插入、刪除效率
Hash	哈希表	支持單key	接近O(1)	小，除了數(shù)據(jù)沒(méi)有額外的存儲(chǔ)	O(1)
B+樹(shù)	平衡二叉樹(shù)擴(kuò)展而來(lái)	單key,范圍，分頁(yè)	O(Log(n)	除了數(shù)據(jù)，還多了左右指針，以及葉子節(jié)點(diǎn)指針	O(Log(n)，需要調(diào)整樹(shù)的結(jié)構(gòu)，算法比較復(fù)雜
跳表	有序鏈表擴(kuò)展而來(lái)	單key，分頁(yè)	O(Log(n)	除了數(shù)據(jù)，還多了指針，但是每個(gè)節(jié)點(diǎn)的指針小于2,所以比B+樹(shù)占用空間小	O(Log(n)，只用處理鏈表，算法比較簡(jiǎn)單

對(duì)LSM結(jié)構(gòu)感興趣的可以看下cassandra vs mongo (1)存儲(chǔ)引擎

cassandra vs mongo (1)存儲(chǔ)引擎

概括

存儲(chǔ)引擎：

B-Tree

緩存管理

緩存管理的核心在于置換算法，置換算法常見(jiàn)的有FIFO（First In First Out），LRU(Least Recently Used)。關(guān)系型數(shù)據(jù)庫(kù)在LRU的基礎(chǔ)上，進(jìn)行了改進(jìn)，主要使用LIRS(Low Inter-reference Recency Set)
將緩存分為兩級(jí)，第一次采用LRU，最近被使用到的數(shù)據(jù)會(huì)進(jìn)第一級(jí)，如果數(shù)據(jù)在較短時(shí)間內(nèi)被訪(fǎng)問(wèn)了兩次或以上，則成為熱點(diǎn)數(shù)據(jù)，進(jìn)入第二級(jí)。避免了進(jìn)行全表掃描的時(shí)候，可能會(huì)將緩存中的大量熱點(diǎn)數(shù)據(jù)替換掉。

LSM

Log-Structured Merge Tree:結(jié)構(gòu)化合并樹(shù)，核心思想就是不將數(shù)據(jù)立即從內(nèi)存中寫(xiě)入到磁盤(pán)，而是先保存在內(nèi)存中，積累了一定量后再刷到磁盤(pán)中

LSM VS B-Tree

LSM在B-Tree的基礎(chǔ)上為了獲取更好的寫(xiě)性能而犧牲了部分的讀性能，同時(shí)利用其它的實(shí)現(xiàn)來(lái)彌補(bǔ)讀性能，比如boom-filter.

1.寫(xiě)

B樹(shù)的寫(xiě)入，是首先找到對(duì)應(yīng)的塊位置，然后將新數(shù)據(jù)插入。隨著寫(xiě)入越來(lái)越多，為了維護(hù)B樹(shù)結(jié)構(gòu)，節(jié)點(diǎn)得分裂。這樣插入數(shù)據(jù)的隨機(jī)寫(xiě)概率就會(huì)增大，性能會(huì)減弱。

LSM 則是在內(nèi)存中形成小的排好序的樹(shù)，然后flush到磁盤(pán)的時(shí)候不斷的做merge.因?yàn)閷?xiě)入都是內(nèi)存寫(xiě)，不寫(xiě)磁盤(pán)，所以寫(xiě)會(huì)很高效。

2.讀

B樹(shù)從根節(jié)點(diǎn)開(kāi)始二分查詢(xún)直到葉子節(jié)點(diǎn)，每次讀取一個(gè)節(jié)點(diǎn)，如果對(duì)應(yīng)的頁(yè)面不在內(nèi)存中，則讀取磁盤(pán)，緩存數(shù)據(jù)。

LSM樹(shù)整個(gè)結(jié)構(gòu)不是有序的，所以不知道數(shù)據(jù)在什么地方，需要從每個(gè)小的有序結(jié)構(gòu)中做二分查詢(xún)，找到了就返回，找不到就繼續(xù)找下一個(gè)有序結(jié)構(gòu)。所以說(shuō)LSM犧牲了讀性能。但是LSM之所以能夠作為大規(guī)模數(shù)據(jù)存儲(chǔ)系統(tǒng)在于讀性能可以通過(guò)其他方式來(lái)提高，比如讀取性能更多的依賴(lài)于內(nèi)存/緩存命中率而不是磁盤(pán)讀取。

Cassandra

Cassandra是一個(gè)寫(xiě)性能優(yōu)于讀性能的NoSql數(shù)據(jù)庫(kù)，寫(xiě)性能好一個(gè)原因在于選擇了LSM存儲(chǔ)引擎。

Mongo

MMAPv1

Mongo 3.2以前默認(rèn)使用MMAPv1存儲(chǔ)引擎，是基于B-Tree類(lèi)型的。

邊界(padding)

MMAPv1 存儲(chǔ)引擎使用一個(gè)叫做”記錄分配”的過(guò)程來(lái)為document存儲(chǔ)分配磁盤(pán)空間。MongoDB與Cassandra不同的是，需要去更新原有的document。如果原有的document空間不足，則需要將這個(gè)document移動(dòng)到新的位置，更新對(duì)應(yīng)的index。這樣就會(huì)導(dǎo)致一些不必要的更新，和數(shù)據(jù)碎片。

為了避免出現(xiàn)上述情況，就有了邊界的概念，就是為document預(yù)分配空間。但是這樣就有可能造成資源的浪費(fèi)。mongo 按照64M,128M,256M…2G的2的冥次方遞增策略預(yù)分配，最大2G。在數(shù)據(jù)量小的情況下問(wèn)題并不明顯，但是當(dāng)達(dá)到2G時(shí)，磁盤(pán)占用量大的問(wèn)題就出來(lái)了。

同樣這一點(diǎn)和關(guān)系型數(shù)據(jù)庫(kù)也不一樣，關(guān)系型數(shù)據(jù)庫(kù)對(duì)于長(zhǎng)記錄數(shù)據(jù)會(huì)分開(kāi)存儲(chǔ)。

鎖

MMAPv1使用collection級(jí)別的鎖，即一個(gè)collecion增，刪，改一次只能有一個(gè)。在并發(fā)操作時(shí)，就會(huì)造成等待。

WiredTiger

3.2及其以后的默認(rèn)存儲(chǔ)引擎,同樣是基于B-Tree的。采用了lock-free,風(fēng)險(xiǎn)指針等并發(fā)技術(shù)，使得在多核機(jī)器上工作的更好。

鎖級(jí)別為document。并且引入了compression，減少了磁盤(pán)占用。

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)腳本之家的支持。