[TOC]
參考
B樹、B+樹纵顾、LSM樹以及其典型應(yīng)用場景
B樹和B+樹的插入伍茄、刪除圖文詳解
BTree vs LSM
0. 前言
動(dòng)態(tài)查找樹主要有：二叉查找樹、平衡二叉樹施逾、紅黑樹敷矫、B樹、B+樹汉额。前面三種是典型的二叉查找樹曹仗，查找的時(shí)間復(fù)雜度是O(log2N)。涉及到磁盤的讀寫（比如每個(gè)節(jié)點(diǎn)都需要從磁盤獲热渌选）怎茫，讀寫的速度就與樹的深度有關(guān)系，那么降低樹的深度也就可以提升查找效率妓灌。這時(shí)就提出了平衡多路查找樹轨蛤，也就是B樹以及B+樹。
B樹和B+樹非常典型的場景就是用于關(guān)系型數(shù)據(jù)庫的索引(MySQL)
1. B類樹
1.2. B 樹
B樹是一種平衡多路搜索樹虫埂，B樹與紅黑樹最大的不同在于祥山，B樹的結(jié)點(diǎn)可以有多個(gè)子女，從幾個(gè)到幾千個(gè)掉伏。那為什么又說B樹與紅黑樹很相似呢?因?yàn)榕c紅黑樹一樣缝呕，一棵含n個(gè)結(jié)點(diǎn)的B樹的高度也為O（l ogn），但可能比一棵紅黑樹的高度小許多岖免，因?yàn)樗姆种б蜃颖容^大岳颇。所以，B樹可以在O（logn）時(shí)間內(nèi)颅湘，實(shí)現(xiàn)各種如插入（insert）话侧，刪除（delete）等動(dòng)態(tài)集合操作。
B樹的定義如下：
- 根節(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對應(yīng)的Value之間
- 其它節(jié)點(diǎn)至少有M/2個(gè)子節(jié)點(diǎn)
- 所有葉子結(jié)點(diǎn)位于同一層瞻鹏；
下圖是一個(gè)M=4的4階的B樹：
B樹的搜索：從根結(jié)點(diǎn)開始悲立，對結(jié)點(diǎn)內(nèi)的關(guān)鍵字（有序）序列進(jìn)行二分查找，如果命中則結(jié)束新博，否則進(jìn)入查詢關(guān)鍵字所屬范圍的兒子結(jié)點(diǎn)薪夕；重復(fù)，直到所對應(yīng)的兒子指針為空赫悄，或已經(jīng)是葉子結(jié)點(diǎn)原献；
B樹的特性：
- 關(guān)鍵字集合分布在整顆樹中；
- 任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)結(jié)點(diǎn)中埂淮；
- 搜索有可能在非葉子結(jié)點(diǎn)結(jié)束(樹中所有結(jié)點(diǎn)都存儲數(shù)據(jù)姑隅，與B+樹這一點(diǎn)不同)；
- 其搜索性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找倔撞；
1.2. B+樹
B+樹是對B樹的一種變形讲仰，與B樹的差異在于：
- 有n棵子樹的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字，每個(gè)關(guān)鍵字不保存數(shù)據(jù)痪蝇，只用來索引鄙陡，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)。
- 所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息躏啰，及指向含這些關(guān)鍵字記錄的指針趁矾，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。
- 所有的非終端結(jié)點(diǎn)可以看成是索引部分丙唧，結(jié)點(diǎn)中僅含其子樹（根結(jié)點(diǎn)）中的最大（或最杏骸）關(guān)鍵字。
- 為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針想际，便于區(qū)間查找和遍歷培漏。
- 所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)。
B+樹的搜索：與B-樹也基本相同胡本，區(qū)別是B+樹只有達(dá)到葉子結(jié)點(diǎn)才命中（B-樹可以在非葉子結(jié)點(diǎn)命中）牌柄，其性能也等價(jià)于在關(guān)鍵字全集做一次二分查找；
B+的特性：
- 非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引）侧甫，葉子結(jié)點(diǎn)相當(dāng)于是存儲（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層珊佣；
- B+樹的葉子結(jié)點(diǎn)都是相鏈的，因此對整棵樹的遍歷只需要一次線性遍歷葉子結(jié)點(diǎn)即可披粟。而且由于數(shù)據(jù)順序排列并且相連咒锻，所以便于區(qū)間查找和搜索。而B樹則需要進(jìn)行每一層的遞歸遍歷守屉。相鄰的元素可能在內(nèi)存中不相鄰惑艇，所以緩存命中性沒有B+樹好。
B+樹的分裂：
- 當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，分配一個(gè)新的結(jié)點(diǎn)滨巴，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)思灌，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針；
- B+樹的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)恭取，而不會影響兄弟結(jié)點(diǎn)泰偿，所以它不需要指向兄弟的指針。
1.3. B*樹
B*樹是B+樹的變體蜈垮，在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針耗跛；
B*樹的分裂：
- 當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，如果它的下一個(gè)兄弟結(jié)點(diǎn)未滿攒发，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點(diǎn)中课兄，再在原結(jié)點(diǎn)插入關(guān)鍵字，最后修改父結(jié)點(diǎn)中兄弟結(jié)點(diǎn)的關(guān)鍵字（因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍改變了）晨继；
- 如果兄弟也滿了，則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之間增加新結(jié)點(diǎn)搬俊，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn)紊扬，最后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針。
1.4. B 樹唉擂、 B+樹餐屎、B*樹總結(jié)和對比
B樹：多路搜索樹，每個(gè)結(jié)點(diǎn)存儲M/2到M個(gè)關(guān)鍵字玩祟，非葉子結(jié)點(diǎn)存儲指向關(guān)鍵字范圍的子結(jié)點(diǎn)腹缩；所有關(guān)鍵字在整顆樹中出現(xiàn)，且只出現(xiàn)一次空扎，非葉子結(jié)點(diǎn)可以命中藏鹊；
B+樹：在B-樹基礎(chǔ)上，為葉子結(jié)點(diǎn)增加鏈表指針转锈，所有關(guān)鍵字都在葉子結(jié)點(diǎn)中出現(xiàn)盘寡，非葉子結(jié)點(diǎn)作為葉子結(jié)點(diǎn)的索引；B+樹總是到葉子結(jié)點(diǎn)才命中撮慨；
B*樹：在B+樹基礎(chǔ)上竿痰，為非葉子結(jié)點(diǎn)也增加鏈表指針，將結(jié)點(diǎn)的最低利用率從1/2提高到2/3砌溺；
B+樹雖然優(yōu)點(diǎn)很多影涉，但是B樹也有優(yōu)點(diǎn)，其優(yōu)點(diǎn)在于规伐，由于B樹的每一個(gè)節(jié)點(diǎn)都包含key和value蟹倾，因此經(jīng)常訪問的元素可能離根節(jié)點(diǎn)更近，因此訪問也更迅速楷力。下面是B 樹和B+樹的區(qū)別圖：
為什么說B+tree比B樹更適合實(shí)際應(yīng)用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫索引喊式？
-
B+tree的磁盤讀寫代價(jià)更低
B+tree的內(nèi)部結(jié)點(diǎn)并沒有指向關(guān)鍵字具體信息的指針孵户。因此其內(nèi)部結(jié)點(diǎn)相對B樹更小。如果把所有同一內(nèi)部結(jié)點(diǎn)的關(guān)鍵字存放在同一盤塊中岔留，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多夏哭。一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對來說IO讀寫次數(shù)也就降低了献联。舉個(gè)例子竖配，假設(shè)磁盤中的一個(gè)盤塊容納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è)盤快。而B+ 樹內(nèi)部結(jié)點(diǎn)只需要1個(gè)盤快原押。當(dāng)需要把內(nèi)部結(jié)點(diǎn)讀入內(nèi)存中的時(shí)候胁镐，B 樹就比B+ 樹多一次盤塊查找時(shí)間(在磁盤中就是盤片旋轉(zhuǎn)的時(shí)間)。
B+tree的查詢效率更加穩(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)鍵字查詢的路徑長度相同笨农，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢效率相當(dāng)就缆。B樹在提高了磁盤IO性能的同時(shí)并沒有解決元素遍歷的效率低下的問題。正是為了解決這個(gè)問題谒亦，B+樹應(yīng)運(yùn)而生竭宰。B+樹只要遍歷葉子節(jié)點(diǎn)就可以實(shí)現(xiàn)整棵樹的遍歷。而且在數(shù)據(jù)庫中基于范圍的查詢是非常頻繁的份招，而B樹不支持這樣的操作（或者說效率太低）切揭。
2. LSM 樹
目前常見的主要的三種存儲引擎是：哈希、B+樹脾还、LSM樹：
- 哈希存儲引擎：是哈希表的持久化實(shí)現(xiàn)伴箩，支持增、刪鄙漏、改以及隨機(jī)讀取操作嗤谚，但不支持順序掃描，對應(yīng)的存儲系統(tǒng)為key-value存儲系統(tǒng)怔蚌。對于key-value的插入以及查詢巩步，哈希表的復(fù)雜度都是O(1)，明顯比樹的操作O(n)快,如果不需要有序的遍歷數(shù)據(jù)桦踊，哈希表性能最好椅野。
- B+樹存儲引擎是B+樹的持久化實(shí)現(xiàn)，不僅支持單條記錄的增、刪竟闪、讀离福、改操作，還支持順序掃描（B+樹的葉子節(jié)點(diǎn)之間的指針）炼蛤，對應(yīng)的存儲系統(tǒng)就是關(guān)系數(shù)據(jù)庫（Mysql等）妖爷。
- LSM樹（Log-Structured MergeTree）存儲引擎和B+樹存儲引擎一樣，同樣支持增理朋、刪絮识、讀、改嗽上、順序掃描操作次舌。而且通過批量存儲技術(shù)規(guī)避磁盤隨機(jī)寫入問題。當(dāng)然凡事有利有弊兽愤，LSM樹和B+樹相比彼念，LSM樹犧牲了部分讀性能，用來大幅提高寫性能浅萧。
上面三種引擎中国拇，LSM樹存儲引擎的代表數(shù)據(jù)庫就是HBase.
LSM樹核心思想的核心就是放棄部分讀能力，換取寫入的最大化能力惯殊。LSM Tree ，這個(gè)概念就是結(jié)構(gòu)化合并樹的意思也殖，它的核心思路其實(shí)非常簡單土思，就是假定內(nèi)存足夠大，因此不需要每次有數(shù)據(jù)更新就必須將數(shù)據(jù)寫入到磁盤中忆嗜，而可以先將最新的數(shù)據(jù)駐留在內(nèi)存中己儒，等到積累到足夠多之后，再使用歸并排序的方式將內(nèi)存內(nèi)的數(shù)據(jù)合并追加到磁盤隊(duì)尾(因?yàn)樗写判虻臉涠际怯行虻睦粒梢酝ㄟ^合并排序的方式快速合并到一起)闪湾。
日志結(jié)構(gòu)的合并樹（LSM-tree）是一種基于硬盤的數(shù)據(jù)結(jié)構(gòu)，與B+tree相比绩卤，能顯著地減少硬盤磁盤臂的開銷途样，并能在較長的時(shí)間提供對文件的高速插入（刪除）。然而LSM-tree在某些情況下濒憋，特別是在查詢需要快速響應(yīng)時(shí)性能不佳何暇。通常LSM-tree適用于索引插入比檢索更頻繁的應(yīng)用系統(tǒng)。
LSM樹和B+樹的差異主要在于讀性能和寫性能進(jìn)行權(quán)衡凛驮。在犧牲的同時(shí)尋找其余補(bǔ)救方案：
LSM具有批量特性裆站，存儲延遲。當(dāng)寫讀比例很大的時(shí)候（寫比讀多），LSM樹相比于B樹有更好的性能宏胯。因?yàn)殡S著insert操作羽嫡，為了維護(hù)B+樹結(jié)構(gòu)，節(jié)點(diǎn)分裂肩袍。讀磁盤的隨機(jī)讀寫概率會變大杭棵，性能會逐漸減弱。
B樹的寫入過程：對B樹的寫入過程是一次原位寫入的過程了牛，主要分為兩個(gè)部分颜屠，首先是查找到對應(yīng)的塊的位置，然后將新數(shù)據(jù)寫入到剛才查找到的數(shù)據(jù)塊中鹰祸，然后再查找到塊所對應(yīng)的磁盤物理位置甫窟，將數(shù)據(jù)寫入去。當(dāng)然蛙婴，在內(nèi)存比較充足的時(shí)候粗井，因?yàn)锽樹的一部分可以被緩存在內(nèi)存中，所以查找塊的過程有一定概率可以在內(nèi)存內(nèi)完成街图，不過為了表述清晰浇衬，我們就假定內(nèi)存很小，只夠存一個(gè)B樹塊大小的數(shù)據(jù)吧餐济≡爬蓿可以看到，在上面的模式中絮姆，需要兩次隨機(jī)尋道（一次查找醉冤，一次原位寫），才能夠完成一次數(shù)據(jù)的寫入篙悯，代價(jià)還是很高的蚁阳。
-
LSM優(yōu)化方式：
a. Bloom filter: 就是個(gè)帶隨機(jī)概率的bitmap,可以快速的告訴你，某一個(gè)小的有序結(jié)構(gòu)里有沒有指定的那個(gè)數(shù)據(jù)的鸽照。于是就可以不用二分查找螺捐，而只需簡單的計(jì)算幾次就能知道數(shù)據(jù)是否在某個(gè)小集合里啦。效率得到了提升矮燎，但付出的是空間代價(jià)定血。
b. compact:小樹合并為大樹:因?yàn)樾湫阅苡袉栴}，所以要有個(gè)進(jìn)程不斷地將小樹合并到大樹上诞外，這樣大部分的老數(shù)據(jù)查詢也可以直接使用log2N的方式找到糠悼，不需要再進(jìn)行(N/m)*log2n的查詢了
