關(guān)于我的 Leetcode 題目解答，代碼前往 Github：https://github.com/chenxiangcyr/leetcode-answers
B樹是一種查找樹，目的都是為了解決某種系統(tǒng)中，查找效率低的問題。
二叉查找樹的特點是每個非葉節(jié)點都只有兩個孩子節(jié)點。然而這種做法會導(dǎo)致當(dāng)數(shù)據(jù)量非常大時组哩，二叉查找樹的深度過深琅翻，搜索算法自根節(jié)點向下搜索時有决，需要訪問的節(jié)點也就變的相當(dāng)多但骨。
如果這些節(jié)點存儲在外存儲器磁盤中闷哆，每訪問一個節(jié)點，相當(dāng)于就是進行了一次I/O操作，隨著樹高度的增加勇蝙，頻繁的I/O操作一定會降低查詢的效率烫罩。
B樹的基本邏輯就是這個思路贝攒，它要改二叉為多叉，每個節(jié)點存儲更多的指針信息质欲，以降低I/O操作數(shù)九昧。
B 樹
一顆 m 階的B樹是一顆平衡的 m 路搜索樹诞仓，它或者為空樹墅拭，或者滿足下列條件：
- 每個結(jié)點最多有 m 個孩子
- 除根結(jié)點外，每個非葉子結(jié)點至少有
[ceil(m/2)]個孩子結(jié)點 - 若根節(jié)點不是葉子結(jié)點涣狗，則它至少有 2 個孩子
- 有 k 個孩子的非葉子結(jié)點有 k-1 個關(guān)鍵碼谍婉，關(guān)鍵碼按遞增次序排列
- 所有的葉子結(jié)點都在同一層。B樹的葉子結(jié)點可以看作一種外部結(jié)點镀钓，不包含任何信息
一個標(biāo)準(zhǔn)的 B樹 如下圖：
有關(guān)B樹的一些特性：
- 關(guān)鍵字集合分布在整顆樹中穗熬；
- 任何一個關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個結(jié)點中；
- 搜索有可能在非葉子結(jié)點結(jié)束丁溅；
- 其搜索性能等價于在關(guān)鍵字全集內(nèi)做一次二分查找唤蔗；
B樹的高度
所以當(dāng)B樹包含 N 個關(guān)鍵字時，B樹的最大高度為 K-1（因為計算B樹高度時窟赏，葉結(jié)點所在層不計算在內(nèi)）妓柜，即：K - 1 = log┌m/2┐((N+1)/2 )+1。
在搜索B樹時涯穷，很明顯棍掐，訪問節(jié)點（即讀取磁盤）的次數(shù)與樹的高度呈正比，而B樹與平衡的或者普通的二叉查找樹相比拷况，雖然高度都是對數(shù)數(shù)量級作煌，但是顯然B樹中 log 函數(shù)的底可以比 2 更大掘殴，因此，和二叉樹相比粟誓，極大地減少了磁盤讀取的次數(shù)奏寨。
B樹的搜索
搜索關(guān)鍵字的29的文件的過程：
- 從根節(jié)點開始，讀取根節(jié)點信息努酸，根節(jié)點有2個關(guān)鍵字：17和35服爷。因為17 < 29 < 35，所以找到指針P2指向的子樹获诈，也就是磁盤塊3（1次I/0操作）
- 讀取當(dāng)前節(jié)點信息仍源，當(dāng)前節(jié)點有2個關(guān)鍵字：26和30。26 < 29 < 30舔涎，找到指針P2指向的子樹笼踩，也就是磁盤塊8（2次I/0操作）
- 讀取當(dāng)前節(jié)點信息，當(dāng)前節(jié)點有2個關(guān)鍵字：28和29亡嫌。找到了：坑凇（3次I/0操作）
B樹的插入
首先找到要插入的關(guān)鍵字應(yīng)該插入的葉子節(jié)點 u。如果 u 是滿的挟冠，那么由于不能將一個關(guān)鍵字插入滿的節(jié)點于购，我們需要對 u 按其當(dāng)前排在中間關(guān)鍵字u.keyt 進行分裂，分裂成兩個節(jié)點 u1知染，u2肋僧；同時，作為分裂標(biāo)準(zhǔn)的關(guān)鍵字 u.keyt 會被上移到 u 的父節(jié)點中控淡，在 u.keyt 插入前嫌吠，如果 u 的父節(jié)點未滿，則直接插入即可掺炭；如果 u 的父節(jié)點已滿辫诅，則按照上面的方法對u的父節(jié)點分裂，這個過程如果一直不停止的話涧狮，最終會導(dǎo)致B樹的根節(jié)點分裂炕矮，B樹的高度增加一層。
B樹的刪除
刪除操作的基本思想和插入操作是一樣的勋篓，都是不能因為關(guān)鍵字的改變而改變B樹的結(jié)構(gòu)吧享。
插入操作主要防止的是某個節(jié)點中關(guān)鍵字的個數(shù)太多，所以采用了分裂譬嚣；刪除則是要防止某個節(jié)點中，因刪除了關(guān)鍵字而導(dǎo)致這個節(jié)點的關(guān)鍵字個數(shù)太少钞它，所以采用了合并操作拜银。
- 如果在當(dāng)前節(jié)點中殊鞭，找到了要刪的關(guān)鍵字，且當(dāng)前節(jié)點為內(nèi)部節(jié)點尼桶。那么操灿，如果有比較豐滿的前驅(qū)或后繼，借一個上來泵督，再把要刪的關(guān)鍵字降下去趾盐，在子樹中遞歸刪除；如果沒有比較豐滿的前驅(qū)或后繼小腊，則令前驅(qū)與后繼合并救鲤，把要刪的關(guān)鍵字降下去，遞歸刪除秩冈；
- 如果在當(dāng)前節(jié)點中本缠，還未找到要刪的關(guān)鍵字，且當(dāng)前節(jié)點為內(nèi)部節(jié)點入问。那么去找下一步應(yīng)該掃描的孩子丹锹，并判斷這個孩子是否豐滿，如果豐滿芬失，繼續(xù)掃描楣黍；如果不豐滿，則看其有無豐滿的兄弟棱烂，有的話租漂，從父親那里接一個，父親再找其最豐滿的兄弟借一個垢啼；如果沒有豐滿的兄弟窜锯，則合并，再令父親下降芭析，以保證B樹的結(jié)構(gòu)锚扎。
B+樹
B+樹是B樹的一種變形，它更適合實際應(yīng)用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫索引馁启。
m 階的B+樹的特征：
- 有 n 棵子樹的非葉子結(jié)點中含有 n 個關(guān)鍵字（B樹是n-1個）驾孔，這些關(guān)鍵字不保存數(shù)據(jù)，只用來索引惯疙，所有數(shù)據(jù)都保存在葉子節(jié)點（B樹是每個關(guān)鍵字都保存數(shù)據(jù)）翠勉。
- 所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針霉颠，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接对碌。
- 所有的非葉子結(jié)點可以看成是索引部分，結(jié)點中僅含其子樹中的最大（或最休镔恕）關(guān)鍵字朽们。
- 通常在B+樹上有兩個頭指針怀读，一個指向根結(jié)點，一個指向關(guān)鍵字最小的葉子結(jié)點骑脱。
- 同一個數(shù)字會在不同節(jié)點中重復(fù)出現(xiàn)菜枷，根節(jié)點的最大元素就是B+樹的最大元素。
一個標(biāo)準(zhǔn)的 B+樹 如下圖：
B樹 Vs B+樹
B+樹和B樹相比叁丧，主要的不同點在以下2項：
- 內(nèi)部節(jié)點中啤誊，關(guān)鍵字的個數(shù)與其子樹的個數(shù)相同，不像B樹種拥娄，子樹的個數(shù)總比關(guān)鍵字個數(shù)多1個
- 所有指向文件的關(guān)鍵字及其指針都在葉子節(jié)點中蚊锹，不像B樹，有的指向文件的關(guān)鍵字是在內(nèi)部節(jié)點中条舔。換句話說枫耳，B+樹中，內(nèi)部節(jié)點僅僅起到索引的作用孟抗，在搜索過程中迁杨，如果查詢和內(nèi)部節(jié)點的關(guān)鍵字一致，那么搜索過程不停止凄硼，而是繼續(xù)向下搜索這個分支铅协。
根據(jù)B+樹的結(jié)構(gòu)，我們可以發(fā)現(xiàn)B+樹相比于B樹摊沉，在文件系統(tǒng)狐史，數(shù)據(jù)庫系統(tǒng)當(dāng)中，更有優(yōu)勢说墨，原因如下：
B+樹的磁盤讀寫代價更低
B+樹的內(nèi)部結(jié)點并沒有指向關(guān)鍵字具體信息的指針骏全。因此其內(nèi)部結(jié)點相對B樹更小。如果把所有同一內(nèi)部結(jié)點的關(guān)鍵字存放在同一盤塊中尼斧，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多姜贡。一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對來說I/O讀寫次數(shù)也就降低了棺棵。B+樹的查詢效率更加穩(wěn)定
由于內(nèi)部結(jié)點并不是最終指向文件內(nèi)容的結(jié)點楼咳，而只是葉子結(jié)點中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點到葉子結(jié)點的路烛恤。所有關(guān)鍵字查詢的路徑長度相同母怜，導(dǎo)致每一個數(shù)據(jù)的查詢效率相當(dāng)。B+樹更有利于對數(shù)據(jù)庫的掃描
B樹在提高了磁盤IO性能的同時并沒有解決元素遍歷的效率低下的問題缚柏，而B+樹只需要遍歷葉子節(jié)點就可以解決對全部關(guān)鍵字信息的掃描苹熏，所以對于數(shù)據(jù)庫中頻繁使用的 range query，B+樹有著更高的性能。
引用：
B樹與B+樹
平衡二叉樹柜裸、B樹缕陕、B+樹粱锐、B*樹 理解其中一種你就都明白了
B樹(B-樹)疙挺、B+樹、AVL樹怜浅、B*樹
b樹和b+樹的區(qū)別
