目錄

• 序言
• B樹的特點(diǎn)
• M階B樹的性質(zhì)（m >= 2）
• B樹 VS 二叉搜索樹

一 序言

B樹是一種平衡的多路搜索樹，多用于文件系統(tǒng)，數(shù)據(jù)庫(kù)的實(shí)現(xiàn)。也稱(B-tree或B-樹)

二 B樹的特點(diǎn)

1. 一個(gè)節(jié)點(diǎn)可以存儲(chǔ)超過(guò)2個(gè)元素，可以擁有超過(guò)2個(gè)子節(jié)點(diǎn)
2. 擁有二叉搜索樹的一些性質(zhì)
3. 平衡，每個(gè)節(jié)點(diǎn)的所有子樹高度一致
4. 比較矮

image.png

三 M階B樹的性質(zhì)（m >= 2）

1. 假設(shè)一個(gè)節(jié)點(diǎn)存儲(chǔ)的元素個(gè)數(shù)為 x

• 根節(jié)點(diǎn):1 ≤ x ≤ m ? 1
• 非根節(jié)點(diǎn):┌ m/2 ┐ ? 1 ≤ x ≤ m ? 1(向上取整)
• 如果有子節(jié)點(diǎn)，子節(jié)點(diǎn)個(gè)數(shù) y = x + 1
  • 根節(jié)點(diǎn):2 ≤ y ≤ m
• 非根節(jié)點(diǎn):┌ m/2 ┐ ≤ y ≤ m

比如 m = 3，2 ≤ y ≤ 3，因此可以稱為(2, 3)樹、2-3樹 
比如 m = 4，2 ≤ y ≤ 4，因此可以稱為(2, 4)樹、2-3-4樹 
比如 m = 5，3 ≤ y ≤ 5，因此可以稱為(3, 5)樹
比如 m = 6，3 ≤ y ≤ 6，因此可以稱為(3, 6)樹
比如 m = 7，4 ≤ y ≤ 7，因此可以稱為(4, 7)樹

思考:如果 m = 2，那B樹是什么樣子? ?
你猜數(shù)據(jù)庫(kù)實(shí)現(xiàn)中一般用幾階B樹? 200 ~ 300

四 B樹 VS 二叉搜索樹

B樹 和 二叉搜索樹，在邏輯上是等價(jià)的

• 多代節(jié)點(diǎn)合并，可以獲得一個(gè)超級(jí)節(jié)點(diǎn)

  • 2代合并的超級(jí)節(jié)點(diǎn)，最多擁有 4 個(gè)子節(jié)點(diǎn)(至少是 4階B樹)
  • 3代合并的超級(jí)節(jié)點(diǎn)，最多擁有 8 個(gè)子節(jié)點(diǎn)(至少是 8階B樹)
  • n代合并的超級(jí)節(jié)點(diǎn)，最多擁有 2n個(gè)子節(jié)點(diǎn)( 至少是 2n階B樹)

• m階B樹，最多需要 log2m 代合并

image.png

image.png

4.1 搜索

跟二叉搜索樹的搜索類似

image.png

1. 先在節(jié)點(diǎn)內(nèi)部從小到大開始搜索元素
2. 如果命中，搜索結(jié)束
3. 如果未命中，再去對(duì)應(yīng)的子節(jié)點(diǎn)中搜索元素，重復(fù)步驟1

4.2 添加

新添加的元素必定是添加到葉子節(jié)點(diǎn)

image.png

4.2.1 插入55

image.png

4.2.2 插入95

image.png

4.2.3 再插入98？（假設(shè)是一棵4階B樹）

最右下角的葉子節(jié)點(diǎn)的元素個(gè)數(shù)將超過(guò)限制
這種現(xiàn)象可以稱之為 上溢（overflow）

4.2.4 添加 - 上溢的解決（假設(shè)5階）

1. 上溢節(jié)點(diǎn)的元素個(gè)數(shù)必然等于m

2. 假設(shè)上溢節(jié)點(diǎn)最中間元素的位置為k

• 將k位置的元素向上與父節(jié)點(diǎn)合并
• 將 [0, k-1] 和 [k + 1, m - 1] 位置的元素分裂成 2 個(gè)子節(jié)點(diǎn)
  • 這 2 個(gè)子節(jié)點(diǎn)的元素個(gè)數(shù)，必然都不會(huì)低于最低限制(┌ m/2 ┐ ? 1)

3. 一次分裂完畢后，有可能導(dǎo)致父節(jié)點(diǎn)上溢，依然按照上述方法解決 * 最極端的情況，有可能一直分裂到根節(jié)點(diǎn)

image.png

4.2.5 添加

image.png

1. 插入98

image.png

2. 插入52

image.png

3. 插入54

image.png

4.3 刪除

4.3.1 刪除 - 葉子節(jié)點(diǎn)

假如需要?jiǎng)h除的元素在葉子節(jié)點(diǎn)中，那么直接刪除即可

image.png

?刪除 30

image.png

4.3.2 刪除 – 非葉子節(jié)點(diǎn)

• 假如需要?jiǎng)h除的元素在非葉子節(jié)點(diǎn)中

1. 先找到前驅(qū)或后繼元素，覆蓋所需刪除元素的值
2. 再把前驅(qū)或后繼元素刪除

刪除 60

image.png

• 非葉子節(jié)點(diǎn)的前驅(qū)或后繼元素，必定在葉子節(jié)點(diǎn)中
  • 所以這里的刪除前驅(qū)或后繼元素 ，就是最開始提到的情況:刪除的元素在葉子節(jié)點(diǎn)中
  • 真正的刪除元素都是發(fā)生在葉子節(jié)點(diǎn)中

4.3.3 刪除 - 下溢

image.png

刪除22（假設(shè)這是一棵5階B樹）
葉子節(jié)點(diǎn)被刪掉一個(gè)元素后，元素個(gè)數(shù)可能會(huì)低于最低限制（>= ┌ m/2 ┐- 1）

這種現(xiàn)象稱為：下溢（underflow）

4.3.4 刪除 - 下溢的解決

下溢節(jié)點(diǎn)的元素?cái)?shù)量必然等于 ┌ m/2 ┐ ? 2

如果下溢節(jié)點(diǎn)臨近的兄弟節(jié)點(diǎn)，有至少 ┌ m/2 ┐ 個(gè)元素，可以向其借一個(gè)元素

• 將父節(jié)點(diǎn)的元素 b 插入到下溢節(jié)點(diǎn)的 0 位置(最小位置)
• 用兄弟節(jié)點(diǎn)的元素 a(最大的元素)替代父節(jié)點(diǎn)的元素 b
• 這種操作其實(shí)就是:旋轉(zhuǎn)

image.png

4.3.5 刪除 - 下溢的解決

如果下溢節(jié)點(diǎn)臨近的兄弟節(jié)點(diǎn)，只有 ┌ m/2 ┐ ? 1 個(gè)元素

• 將父節(jié)點(diǎn)的元素 b 挪下來(lái)跟左右子節(jié)點(diǎn)進(jìn)行合并
• 合并后的節(jié)點(diǎn)元素個(gè)數(shù)等于┌ m/2 ┐ + ┌ m/2 ┐ ? 2，不超過(guò) m ? 1
• 這個(gè)操作可能會(huì)導(dǎo)致父節(jié)點(diǎn)下溢，依然按照上述方法解決，下溢現(xiàn)象可能會(huì)一直往上傳播

image.png

4.3.6 4階B樹

如果先學(xué)習(xí)4階B樹(2-3-4樹)，將能更好地學(xué)習(xí)理解紅黑樹

? 4階B樹的性質(zhì)

• 所有節(jié)點(diǎn)能存儲(chǔ)的元素個(gè)數(shù) x :1 ≤ x ≤ 3
• 所有非葉子節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù) y :2 ≤ y ≤ 4

?添加

• 從 1 添加到 22

?刪除

• 從 1 刪除到 22

image.png

本文參考 MJ老師的 戀上數(shù)據(jù)結(jié)構(gòu)與算法

《戀上數(shù)據(jù)結(jié)構(gòu)與算法一》筆記