原文鏈接：https://blog.csdn.net/u010853261/article/details/78217823
前言
動(dòng)態(tài)查找樹(shù)主要有：二叉查找樹(shù)槽片、平衡二叉樹(shù)、紅黑樹(shù)肢础、B樹(shù)还栓、B+樹(shù)。前面三種是典型的二叉查找樹(shù)传轰，查找的時(shí)間復(fù)雜度是O(log2N)與樹(shù)的深度有關(guān)系剩盒，那么降低樹(shù)的深度也就可以提升查找效率。這時(shí)就提出了平衡多路查找樹(shù)慨蛙，也就是B樹(shù)以及B+樹(shù)辽聊。
B樹(shù)和B+樹(shù)非常典型的場(chǎng)景就是用于關(guān)系型數(shù)據(jù)庫(kù)的索引(MySQL)
B樹(shù)是一種平衡多路搜索樹(shù)纪挎，B樹(shù)與紅黑樹(shù)最大的不同在于，B樹(shù)的結(jié)點(diǎn)可以有多個(gè)子女跟匆，從幾個(gè)到幾千個(gè)异袄。那為什么又說(shuō)B樹(shù)與紅黑樹(shù)很相似呢?因?yàn)榕c紅黑樹(shù)一樣，一棵含n個(gè)結(jié)點(diǎn)的B樹(shù)的高度也為O（lgn）玛臂，但可能比一棵紅黑樹(shù)的高度小許多隙轻，應(yīng)為它的分支因子比較大。所以垢揩，B樹(shù)可以在O（logn）時(shí)間內(nèi)玖绿，實(shí)現(xiàn)各種如插入（insert），刪除（delete）等動(dòng)態(tài)集合操作叁巨。
B樹(shù)的定義如下：
根節(jié)點(diǎn)至少有兩個(gè)子節(jié)點(diǎn)
每個(gè)節(jié)點(diǎn)有M-1個(gè)key斑匪，并且以升序排列
位于M-1和M key的子節(jié)點(diǎn)的值位于M-1 和M key對(duì)應(yīng)的Value之間
其它節(jié)點(diǎn)至少有M/2個(gè)子節(jié)點(diǎn)
所有葉子結(jié)點(diǎn)位于同一層；
下圖是一個(gè)M=4的4階的B樹(shù)：?
B樹(shù)的搜索：從根結(jié)點(diǎn)開(kāi)始锋勺，對(duì)結(jié)點(diǎn)內(nèi)的關(guān)鍵字（有序）序列進(jìn)行二分查找蚀瘸，如果命中則結(jié)束，否則進(jìn)入查詢(xún)關(guān)鍵字所屬范圍的兒子結(jié)點(diǎn)庶橱；重復(fù)贮勃，直到所對(duì)應(yīng)的兒子指針為空，或已經(jīng)是葉子結(jié)點(diǎn)苏章；
B樹(shù)的特性：
關(guān)鍵字集合分布在整顆樹(shù)中寂嘉；
任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)結(jié)點(diǎn)中；
搜索有可能在非葉子結(jié)點(diǎn)結(jié)束(樹(shù)中所有結(jié)點(diǎn)都存儲(chǔ)數(shù)據(jù)枫绅，與B+樹(shù)這一點(diǎn)不同)泉孩；
其搜索性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找；
下面是一個(gè)B樹(shù)插入的演示動(dòng)畫(huà)并淋，依次插入：?
6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
B+樹(shù)是對(duì)B樹(shù)的一種變形寓搬，與B樹(shù)的差異在于：
有n棵子樹(shù)的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字，每個(gè)關(guān)鍵字不保存數(shù)據(jù)县耽，只用來(lái)索引句喷，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)。
所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息兔毙，及指向含這些關(guān)鍵字記錄的指針唾琼，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。
所有的非終端結(jié)點(diǎn)可以看成是索引部分瞒御，結(jié)點(diǎn)中僅含其子樹(shù)（根結(jié)點(diǎn)）中的最大（或最懈感稹）關(guān)鍵字。
為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針肴裙，便于區(qū)間查找和遍歷趾唱。
所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)；
如下圖一個(gè)M=3 的B+樹(shù)：
B+樹(shù)的搜索：與B-樹(shù)也基本相同蜻懦，區(qū)別是B+樹(shù)只有達(dá)到葉子結(jié)點(diǎn)才命中（B-樹(shù)可以在非葉子結(jié)點(diǎn)命中）甜癞，其性能也等價(jià)于在關(guān)鍵字全集做一次二分查找；
B+的特性：
非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引）宛乃，葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層悠咱；
B+樹(shù)的葉子結(jié)點(diǎn)都是相鏈的，因此對(duì)整棵樹(shù)的遍歷只需要一次線性遍歷葉子結(jié)點(diǎn)即可征炼。而且由于數(shù)據(jù)順序排列并且相連析既，所以便于區(qū)間查找和搜索。而B(niǎo)樹(shù)則需要進(jìn)行每一層的遞歸遍歷谆奥。相鄰的元素可能在內(nèi)存中不相鄰眼坏，所以緩存命中性沒(méi)有B+樹(shù)好。
B樹(shù)：多路搜索樹(shù)酸些，每個(gè)結(jié)點(diǎn)存儲(chǔ)M/2到M個(gè)關(guān)鍵字宰译，非葉子結(jié)點(diǎn)存儲(chǔ)指向關(guān)鍵字范圍的子結(jié)點(diǎn)；所有關(guān)鍵字在整顆樹(shù)中出現(xiàn)魄懂，且只出現(xiàn)一次沿侈，非葉子結(jié)點(diǎn)可以命中；
B+樹(shù)：在B-樹(shù)基礎(chǔ)上市栗，為葉子結(jié)點(diǎn)增加鏈表指針缀拭，所有關(guān)鍵字都在葉子結(jié)點(diǎn)中出現(xiàn)，非葉子結(jié)點(diǎn)作為葉子結(jié)點(diǎn)的索引填帽；B+樹(shù)總是到葉子結(jié)點(diǎn)才命中智厌；
B+樹(shù)雖然優(yōu)點(diǎn)很多，但是B樹(shù)也有優(yōu)點(diǎn)盲赊，其優(yōu)點(diǎn)在于铣鹏，由于B樹(shù)的每一個(gè)節(jié)點(diǎn)都包含key和value，因此經(jīng)常訪問(wèn)的元素可能離根節(jié)點(diǎn)更近哀蘑，因此訪問(wèn)也更迅速诚卸。下面是B 樹(shù)和B+樹(shù)的區(qū)別圖：
為什么說(shuō)B+tree比B樹(shù)更適合實(shí)際應(yīng)用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫(kù)索引？
（1) B+tree的磁盤(pán)讀寫(xiě)代價(jià)更低?
B+tree的內(nèi)部結(jié)點(diǎn)并沒(méi)有指向關(guān)鍵字具體信息的指針绘迁。因此其內(nèi)部結(jié)點(diǎn)相對(duì)B樹(shù)更小合溺。如果把所有同一內(nèi)部結(jié)點(diǎn)的關(guān)鍵字存放在同一盤(pán)塊中，那么盤(pán)塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多缀台。一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多棠赛。相對(duì)來(lái)說(shuō)IO讀寫(xiě)次數(shù)也就降低了。
舉個(gè)例子，假設(shè)磁盤(pán)中的一個(gè)盤(pán)塊容納16bytes睛约，而一個(gè)關(guān)鍵字2bytes鼎俘，一個(gè)關(guān)鍵字具體信息指針2bytes。一棵9階B-tree(一個(gè)結(jié)點(diǎn)最多8個(gè)關(guān)鍵字)的內(nèi)部結(jié)點(diǎn)需要2個(gè)盤(pán)快辩涝。而B(niǎo)+ 樹(shù)內(nèi)部結(jié)點(diǎn)只需要1個(gè)盤(pán)快贸伐。當(dāng)需要把內(nèi)部結(jié)點(diǎn)讀入內(nèi)存中的時(shí)候，B 樹(shù)就比B+ 樹(shù)多一次盤(pán)塊查找時(shí)間(在磁盤(pán)中就是盤(pán)片旋轉(zhuǎn)的時(shí)間)怔揩。
（2）B+tree的查詢(xún)效率更加穩(wěn)定?
由于非葉子結(jié)點(diǎn)并不是最終指向文件內(nèi)容的結(jié)點(diǎn)捉邢，而只是葉子結(jié)點(diǎn)中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路商膊。所有關(guān)鍵字查詢(xún)的路徑長(zhǎng)度相同伏伐，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢(xún)效率相當(dāng)。
（3）B樹(shù)在提高了磁盤(pán)IO性能的同時(shí)并沒(méi)有解決元素遍歷的效率低下的問(wèn)題晕拆。正是為了解決這個(gè)問(wèn)題藐翎，B+樹(shù)應(yīng)運(yùn)而生。B+樹(shù)只要遍歷葉子節(jié)點(diǎn)就可以實(shí)現(xiàn)整棵樹(shù)的遍歷潦匈。而且在數(shù)據(jù)庫(kù)中基于范圍的查詢(xún)是非常頻繁的阱高，而B(niǎo)樹(shù)不支持這樣的操作（或者說(shuō)效率太低）。
目前常見(jiàn)的主要的三種存儲(chǔ)引擎是：哈希茬缩、B+樹(shù)赤惊、LSM樹(shù)：
哈希存儲(chǔ)引擎：是哈希表的持久化實(shí)現(xiàn)，支持增凰锡、刪未舟、改以及隨機(jī)讀取操作，但不支持順序掃描掂为，對(duì)應(yīng)的存儲(chǔ)系統(tǒng)為key-value存儲(chǔ)系統(tǒng)裕膀。對(duì)于key-value的插入以及查詢(xún)，哈希表的復(fù)雜度都是O(1)勇哗，明顯比樹(shù)的操作O(n)快,如果不需要有序的遍歷數(shù)據(jù)昼扛，哈希表性能最好。
B+樹(shù)存儲(chǔ)引擎是B+樹(shù)的持久化實(shí)現(xiàn)欲诺，不僅支持單條記錄的增抄谐、刪、讀扰法、改操作蛹含，還支持順序掃描（B+樹(shù)的葉子節(jié)點(diǎn)之間的指針），對(duì)應(yīng)的存儲(chǔ)系統(tǒng)就是關(guān)系數(shù)據(jù)庫(kù)（Mysql等）塞颁。
LSM樹(shù)（Log-Structured MergeTree）存儲(chǔ)引擎和B+樹(shù)存儲(chǔ)引擎一樣浦箱，同樣支持增吸耿、刪、讀酷窥、改咽安、順序掃描操作。而且通過(guò)批量存儲(chǔ)技術(shù)規(guī)避磁盤(pán)隨機(jī)寫(xiě)入問(wèn)題竖幔。當(dāng)然凡事有利有弊板乙，LSM樹(shù)和B+樹(shù)相比是偷，LSM樹(shù)犧牲了部分讀性能拳氢，用來(lái)大幅提高寫(xiě)性能。
上面三種引擎中蛋铆，LSM樹(shù)存儲(chǔ)引擎的代表數(shù)據(jù)庫(kù)就是HBase.
LSM樹(shù)核心思想的核心就是放棄部分讀能力馋评，換取寫(xiě)入的最大化能力。LSM Tree 刺啦，這個(gè)概念就是結(jié)構(gòu)化合并樹(shù)的意思留特，它的核心思路其實(shí)非常簡(jiǎn)單，就是假定內(nèi)存足夠大玛瘸，因此不需要每次有數(shù)據(jù)更新就必須將數(shù)據(jù)寫(xiě)入到磁盤(pán)中蜕青，而可以先將最新的數(shù)據(jù)駐留在內(nèi)存中，等到積累到足夠多之后糊渊，再使用歸并排序的方式將內(nèi)存內(nèi)的數(shù)據(jù)合并追加到磁盤(pán)隊(duì)尾(因?yàn)樗写判虻臉?shù)都是有序的右核，可以通過(guò)合并排序的方式快速合并到一起)。
日志結(jié)構(gòu)的合并樹(shù)（LSM-tree）是一種基于硬盤(pán)的數(shù)據(jù)結(jié)構(gòu)渺绒，與B+tree相比贺喝，能顯著地減少硬盤(pán)磁盤(pán)臂的開(kāi)銷(xiāo)，并能在較長(zhǎng)的時(shí)間提供對(duì)文件的高速插入（刪除）宗兼。然而LSM-tree在某些情況下躏鱼，特別是在查詢(xún)需要快速響應(yīng)時(shí)性能不佳。通常LSM-tree適用于索引插入比檢索更頻繁的應(yīng)用系統(tǒng)殷绍。
LSM樹(shù)和B+樹(shù)的差異主要在于讀性能和寫(xiě)性能進(jìn)行權(quán)衡染苛。在犧牲的同時(shí)尋找其余補(bǔ)救方案：
（a）LSM具有批量特性，存儲(chǔ)延遲主到。當(dāng)寫(xiě)讀比例很大的時(shí)候（寫(xiě)比讀多）茶行，LSM樹(shù)相比于B樹(shù)有更好的性能。因?yàn)殡S著insert操作镰烧，為了維護(hù)B+樹(shù)結(jié)構(gòu)拢军，節(jié)點(diǎn)分裂。讀磁盤(pán)的隨機(jī)讀寫(xiě)概率會(huì)變大怔鳖，性能會(huì)逐漸減弱茉唉。
（b）B樹(shù)的寫(xiě)入過(guò)程：對(duì)B樹(shù)的寫(xiě)入過(guò)程是一次原位寫(xiě)入的過(guò)程，主要分為兩個(gè)部分，首先是查找到對(duì)應(yīng)的塊的位置度陆，然后將新數(shù)據(jù)寫(xiě)入到剛才查找到的數(shù)據(jù)塊中艾凯，然后再查找到塊所對(duì)應(yīng)的磁盤(pán)物理位置，將數(shù)據(jù)寫(xiě)入去懂傀。當(dāng)然趾诗，在內(nèi)存比較充足的時(shí)候，因?yàn)锽樹(shù)的一部分可以被緩存在內(nèi)存中蹬蚁，所以查找塊的過(guò)程有一定概率可以在內(nèi)存內(nèi)完成恃泪，不過(guò)為了表述清晰，我們就假定內(nèi)存很小犀斋，只夠存一個(gè)B樹(shù)塊大小的數(shù)據(jù)吧贝乎。可以看到叽粹，在上面的模式中览效，需要兩次隨機(jī)尋道（一次查找，一次原位寫(xiě)）虫几，才能夠完成一次數(shù)據(jù)的寫(xiě)入锤灿，代價(jià)還是很高的。
（c）LSM優(yōu)化方式：
Bloom filter: 就是個(gè)帶隨機(jī)概率的bitmap,可以快速的告訴你辆脸，某一個(gè)小的有序結(jié)構(gòu)里有沒(méi)有指定的那個(gè)數(shù)據(jù)的但校。于是就可以不用二分查找，而只需簡(jiǎn)單的計(jì)算幾次就能知道數(shù)據(jù)是否在某個(gè)小集合里啦每强。效率得到了提升始腾，但付出的是空間代價(jià)。
compact:小樹(shù)合并為大樹(shù):因?yàn)樾?shù)性能有問(wèn)題空执，所以要有個(gè)進(jìn)程不斷地將小樹(shù)合并到大樹(shù)上浪箭，這樣大部分的老數(shù)據(jù)查詢(xún)也可以直接使用log2N的方式找到，不需要再進(jìn)行(N/m)*log2n的查詢(xún)了
SML樹(shù)原理把一棵大樹(shù)拆分成N棵小樹(shù)辨绊，它首先寫(xiě)入內(nèi)存中奶栖，隨著小樹(shù)越來(lái)越大，內(nèi)存中的小樹(shù)會(huì)flush到磁盤(pán)中门坷，磁盤(pán)中的樹(shù)定期可以做merge操作宣鄙，合并成一棵大樹(shù)，以?xún)?yōu)化讀性能默蚌。
以上這些大概就是HBase存儲(chǔ)的設(shè)計(jì)主要思想冻晤，這里分別對(duì)應(yīng)說(shuō)明下：
因?yàn)樾?shù)先寫(xiě)到內(nèi)存中，為了防止內(nèi)存數(shù)據(jù)丟失绸吸，寫(xiě)內(nèi)存的同時(shí)需要暫時(shí)持久化到磁盤(pán)鼻弧，對(duì)應(yīng)了HBase的MemStore和HLog
MemStore上的樹(shù)達(dá)到一定大小之后设江，需要flush到HRegion磁盤(pán)中（一般是Hadoop DataNode），這樣MemStore就變成了DataNode上的磁盤(pán)文件StoreFile攘轩，定期HRegionServer對(duì)DataNode的數(shù)據(jù)做merge操作叉存，徹底刪除無(wú)效空間，多棵小樹(shù)在這個(gè)時(shí)機(jī)合并成大樹(shù)度帮，來(lái)增強(qiáng)讀性能歼捏。
