1. B樹(shù)基本性質(zhì)（又稱為多路平衡查找樹(shù)）（包括 B樹(shù)的高度計(jì)算方法）

• B樹(shù)中所有結(jié)點(diǎn)的孩子結(jié)點(diǎn)數(shù)最大值稱為B樹(shù)的階，通常用m表示，一顆m階B樹(shù)或?yàn)榭諛?shù)，或滿足以下條件
• 每個(gè)結(jié)點(diǎn)最多有m棵子樹(shù)
• 若結(jié)點(diǎn)不是終端結(jié)點(diǎn)，至少有兩棵子樹(shù)
• 出根結(jié)點(diǎn)外的非葉結(jié)點(diǎn)至少有 ?m/2? 棵子樹(shù)
• 非葉子結(jié)點(diǎn)結(jié)構(gòu)

結(jié)點(diǎn)結(jié)構(gòu)

n為該結(jié)點(diǎn)孩子數(shù)量，p是指針，k是關(guān)鍵字。
p0指向的結(jié)點(diǎn)的數(shù)均小于k1，p1指向的結(jié)點(diǎn)的數(shù)均大于k1，小于k2，如此類推

2. B樹(shù)查找

1. 找到結(jié)點(diǎn)，在結(jié)點(diǎn)內(nèi)找指向下一個(gè)結(jié)點(diǎn)的指針
2. 在最終的結(jié)點(diǎn)找關(guān)鍵字。
   由于B樹(shù)常存儲(chǔ)在磁盤(pán)上，則前一個(gè)查找操作是在磁盤(pán)上進(jìn)行的，而后一個(gè)查找操作是在內(nèi)存中進(jìn)行的，即在找到目標(biāo)結(jié)點(diǎn)后，先將結(jié)點(diǎn)中的信息讀入內(nèi)存，然后再采用順序查找法或折半查找法查找等于K的關(guān)鍵字。

根據(jù)B樹(shù)查找規(guī)律可知，每在磁盤(pán)中查找到一個(gè)結(jié)點(diǎn)，需把結(jié)點(diǎn)讀取到內(nèi)存里通過(guò)對(duì)比尋找關(guān)鍵字 / 找到指向下一個(gè)結(jié)點(diǎn)的指針。
計(jì)算機(jī)中，磁盤(pán)讀取尤為耗費(fèi)時(shí)間，所以，B樹(shù)查找的時(shí)間復(fù)雜度主要計(jì)算關(guān)鍵字在第幾層即可（每一層需要從磁盤(pán)讀取一個(gè)結(jié)點(diǎn)到內(nèi)存中）。

• 假設(shè)一顆包含 n 個(gè)關(guān)鍵字、高度為 h 、階數(shù)為 m 的B樹(shù)
  此時(shí)影響B(tài)樹(shù)高度的是每個(gè)結(jié)點(diǎn)所包含的子樹(shù)數(shù)，如果盡可能使結(jié)點(diǎn)子樹(shù)數(shù)都等于 ?m/2? ，則層數(shù)最多，最壞情況；如果盡可能使結(jié)點(diǎn)子樹(shù)數(shù)都等于 m ，則層數(shù)最少，最好情況。
  1. 最好情況：h >= log_m(n + 1)
  2. 最壞情況：h <= log_?m/2?((n + 1) / 2) + 1

3. B樹(shù)插入

插入本是直接加入相應(yīng)葉子結(jié)點(diǎn)的相應(yīng)位置就沒(méi)問(wèn)題了。
但是存在特殊情況，那就是插入后，結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)大于m。
因此，B樹(shù)的關(guān)鍵字插入分為兩個(gè)步驟：

1. 定位：通過(guò)查找，找到最底層的結(jié)點(diǎn)，便是該插入的位置了。
2. 插入：如果給結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)小于等于m - 1，直接插入，否則進(jìn)行分裂插入
3. 分裂插入：插入后，對(duì)結(jié)點(diǎn)進(jìn)行分裂，分裂后的新結(jié)點(diǎn)插入到其父結(jié)點(diǎn)中。如果造成父結(jié)點(diǎn)的關(guān)鍵字也超過(guò)上限，繼續(xù)分裂。

4. B樹(shù)刪除

分為三種情況：

1. 直接刪除關(guān)鍵字
2. 刪除關(guān)鍵字后，結(jié)點(diǎn)的關(guān)鍵字小于 ?m/2? 。與相鄰兄弟，合并，然后分裂。（從相鄰兄弟中取部分關(guān)鍵字，并在雙親結(jié)點(diǎn)中，兩兄弟指針之間的關(guān)鍵字調(diào)整）
3. 刪除關(guān)鍵字之后，結(jié)點(diǎn)的關(guān)鍵字小于 ?m/2?，而相鄰的兄弟關(guān)鍵字結(jié)點(diǎn)等于 ?m/2?不能借。兩個(gè)結(jié)點(diǎn)合并。（此時(shí)需從雙親結(jié)點(diǎn)中刪除關(guān)鍵字，雙親結(jié)點(diǎn)也要進(jìn)行刪除關(guān)鍵字操作。）

5. B+樹(shù)

與B樹(shù)不同之處：

1. 每個(gè)結(jié)點(diǎn)都少了大于k_n的子樹(shù)，即沒(méi)有了指針p_n，所以每個(gè)結(jié)點(diǎn)的子樹(shù)最多只有m - 1
2. 非葉子結(jié)點(diǎn)不存儲(chǔ)關(guān)鍵字，里面的key只是區(qū)分其子樹(shù)的分界數(shù)，所有關(guān)鍵字存儲(chǔ)于葉子結(jié)點(diǎn)
3. 所有葉子結(jié)點(diǎn)內(nèi)的數(shù)字按順序排列，且葉子節(jié)點(diǎn)之間按順序相互鏈接