這篇文章收錄在我的 Github 上 algorithms-tutorial，另外記錄了些算法題解笆呆，感興趣的可以看看呵曹，轉(zhuǎn)載請注明出處脏款。
我們面臨一個實際的問題：就是在大規(guī)模的數(shù)據(jù)存儲中，實現(xiàn)數(shù)據(jù)索引查詢的背景下退盯，這樣會導致二叉查找樹結(jié)構(gòu)由于樹的深度過大而導致磁盤 I/O 讀寫過于頻繁彼乌，進而導致查詢效率低下。
那么我們需要一種機制減少樹的深度：這也就是 B 樹的思想渊迁，采用多叉樹結(jié)構(gòu)
(一) 基本概念：
m階(m 必須是奇數(shù)) B-樹是一個 m 路樹 (即每個節(jié)點最多可以含有 m 個子節(jié)點)
一棵 B-樹是一棵平衡的 m 路搜索樹慰照，它或者是空樹，或者它一般具有以下性質(zhì)：
- 根結(jié)點的兒子數(shù)為[2, M]
- 除根結(jié)點以外的非葉子節(jié)點的兒子數(shù)為[M/2, M]
- 每個結(jié)點存放至少M/2-1（取上整）和至多M-1個關(guān)鍵字
- 每個節(jié)點的關(guān)鍵字比它的子節(jié)點個數(shù)少 1 (葉結(jié)點除外)
- 所有的葉子都在同一個層級
B-樹具有良好的平衡性(因為其所有的葉子都在同一個層級)
優(yōu)點：保證只有少數(shù)的磁盤訪問琉朽，解決數(shù)據(jù)結(jié)構(gòu)不在主存中的數(shù)據(jù)存儲問題毒租。
B 樹 可以為系統(tǒng)最優(yōu)化地對大塊數(shù)據(jù)進行讀和寫的操作，普遍運用在數(shù)據(jù)庫和文件系統(tǒng)箱叁。
(二) 基本操作：
1墅垮、查找元素：
B-樹的搜索，從根結(jié)點開始耕漱，對結(jié)點內(nèi)的關(guān)鍵字（有序）序列進行二分查找算色，如果命中則結(jié)束，否則進入查詢關(guān)鍵字所屬范圍的兒子結(jié)點螟够；重復灾梦，直到所對應的兒子指針為空，或已經(jīng)是葉子結(jié)點；
例如：1.在一棵 5 階B-樹中查找元素 29
首先29比根節(jié)點值大斥废，所以找根節(jié)點的右子數(shù)椒楣，然后再根據(jù)值得判斷，發(fā)現(xiàn) 29 介于 28 和 48 之間牡肉，然后在從中間子樹繼續(xù)查找下去捧灰。
2.同樣在該樹查找一個不存在元素 54
2、插入元素：
在插入一個元素到一棵 B-樹中的葉子節(jié)點時(可能該樹只有一個根結(jié)點)统锤，結(jié)果導致該葉子包含的元素個數(shù)加 1毛俏。
這時候就需要討論：
第一步：如果該節(jié)點的元素個數(shù)還沒達到 m，則插入完后無需處理
比如：在 B-樹中插入元素 3
第二步：如果該節(jié)點元素個數(shù)達到 m 時饲窿，這時候?qū)⒃夭迦氲胶线m的位置煌寇，將最中間的元素取出，成為該節(jié)點的父節(jié)點元素逾雄，然后將其余左右元素拆成兩個新節(jié)點
比如：在 B-樹中插入元素 44
第三步剛才的操作可能導致父節(jié)點的元素個數(shù)達到 m阀溶，這時候用情況 2 迭代處理，直到如果遇到根結(jié)點元素個數(shù)達到 m鸦泳，則最中間元素將成為新的根結(jié)點银锻。
比如：在 B-樹中插入元素 45
3、刪除元素：
我們需要分兩種情況進行討論：
一做鹰、如果該元素存在于葉子結(jié)點击纬，直接刪除它，無需進行其它處理钾麸。
二更振、如果該元素存在于非葉子節(jié)點，那么刪除它將會留下一個空位饭尝，這時候我們需要一些處理來填充該位置
因為節(jié)點的元素個數(shù)在 [M/2, M] 的范圍內(nèi)肯腕，所以比如這里我們以 5 階B-樹為例，判斷節(jié)點元素是否充足即滿足個數(shù)則至少擁有三（2 + 1）個元素的節(jié)點才算是有充足的元素芋肠。
1.如果被刪元素的左子樹擁有足夠的元素乎芳，這時候我們只需拿左子節(jié)點的最大值元素上來填充即可
例如：在 B-樹中刪除元素 23
2.當左子樹不夠元素而右子樹元素充足時遵蚜，這時候我們拿右子樹的最小值元素上來進行填充
例如：在 B-樹中刪除元素 35
3.當左右子樹所含元素均不足時帖池，但左子樹的左邊兄弟節(jié)點的元素個數(shù)充足，這時我們需要拿左邊的兄弟節(jié)點來進行調(diào)整吭净。
例如：在 B-樹中刪除元素 16
![Upload 12.gif failed. Please try again.]
4.當左右子樹所含元素均不足時睡汹，但左子樹的左邊兄弟節(jié)點的元素個數(shù)也不足時，這時候我們還是拿左子樹的最大值元素進行填充寂殉，之后再將該節(jié)點與其他節(jié)點合并形成新的節(jié)點囚巴。
例如：在 B-樹中刪除元素 40
最大容納量計算：
假設(shè)這是有棵 m 階 B-樹，則每層所能容納最多元素個數(shù)為：
根節(jié)點: m - 1
level1: m(m - 1)
level2: m^2(m - 1)
...
leveln: m^n(m - 1)
因此一棵樹高為 h 的 B-樹最多能容納的元素為 m^(h + 1) - 1 即(將上面式子相加)
例如：一課 5 階 B-樹的高度為 2，則該樹所能容納最多元素個數(shù)為 5^3 - 1 = 124
(三) 2-3 樹：
當 m = 3 時彤叉，此時的 B-樹又稱為 2-3 樹庶柿，因為之前實驗課要求 Java 實現(xiàn) 2-3 樹，實現(xiàn)細節(jié)就不細說秽浇，我放在 Github 上面浮庐，感興趣的可以去看一看。
參考資料：
