為什么需要B-樹

當(dāng)所有數(shù)據(jù)都存儲(chǔ)在內(nèi)存中時(shí)，用紅黑樹的查找性能已經(jīng)非常的好了。但是當(dāng)數(shù)據(jù)量非常的大的時(shí)候，把數(shù)據(jù)存放在內(nèi)存中顯然是不可取的，這個(gè)時(shí)候就會(huì)想到把數(shù)據(jù)存放在磁盤中，再進(jìn)行查詢操作。但是有頻繁的磁盤I/O操作（磁盤查找數(shù)據(jù)時(shí)是機(jī)械運(yùn)動(dòng)），會(huì)降低效率，普通二叉樹的高度決定了磁盤I/O的時(shí)間。如果把相關(guān)的信息放在相近的地方，這樣在磁盤中就會(huì)被存放為同一個(gè)數(shù)據(jù)塊，減少磁盤中磁頭的移動(dòng)查找，從而減少I/O的時(shí)間。B-樹就是這樣一種數(shù)據(jù)結(jié)構(gòu)。

B-樹的定義和性質(zhì)

B-tree其實(shí)就是B樹。

B-樹

一顆m階B樹定義：

1. 每個(gè)節(jié)點(diǎn)至多有m個(gè)子樹
2. 除了根節(jié)點(diǎn)以為，每個(gè)節(jié)點(diǎn)至少有m/2棵子樹
3. 根節(jié)點(diǎn)至少有兩顆子樹
4. 所有葉子節(jié)點(diǎn)在樹結(jié)構(gòu)的同一層，并都不包含任何信息（可以看做是外部節(jié)點(diǎn)或查找失敗的節(jié)點(diǎn)），因此m階B樹總是樹高平衡的
5. 有k個(gè)孩子的非葉節(jié)點(diǎn)恰好有k-1個(gè)關(guān)鍵碼，關(guān)鍵碼按遞增順序排列

B-樹的查找、插入、刪除操作過程

• 查找過程分兩步，從B樹的根節(jié)點(diǎn)開始：

  1. 在當(dāng)前節(jié)點(diǎn)中對(duì)關(guān)鍵字進(jìn)行二分法查找。如果找到關(guān)鍵字，就返回相關(guān)記錄，如果當(dāng)前節(jié)點(diǎn)時(shí)葉子節(jié)點(diǎn)，就報(bào)告檢索失敗。
  2. 否則，沿著其中某一分支重復(fù)這一過程。

• 插入操作：
  找到最下層的內(nèi)部節(jié)點(diǎn)，如果節(jié)點(diǎn)的孩子個(gè)數(shù)小于m，那么就直接插入關(guān)鍵字；如果節(jié)點(diǎn)的孩子個(gè)數(shù)等于m，那么就把這個(gè)節(jié)點(diǎn)分裂成兩個(gè)節(jié)點(diǎn)，并且把中間的關(guān)鍵字提升到父節(jié)點(diǎn)。如果父節(jié)點(diǎn)也已經(jīng)滿了，就再分裂父節(jié)點(diǎn)，并且再次提升中間的關(guān)鍵字。插入過程保證所有節(jié)點(diǎn)至少半滿。

• 刪除操作：
  首先找到包含被指定關(guān)鍵字的節(jié)點(diǎn)，并從中刪除，如果節(jié)點(diǎn)為最下層的內(nèi)部節(jié)點(diǎn)，且其中的孩子個(gè)數(shù)大于m/2，則刪除完成；否則要進(jìn)行“合并操作”或從相鄰兄弟中借一個(gè)關(guān)鍵字，如果所刪除的關(guān)鍵字不是最下層的節(jié)點(diǎn)，則在此關(guān)鍵字右鄰子樹中最右邊的最下層中的最小關(guān)鍵字取出并替換刪除的節(jié)點(diǎn)的值，然后再刪除那個(gè)最小關(guān)鍵字節(jié)點(diǎn)。