[Data structure Cheat sheat] — M-way Search Tree to B/B+ tree/2,3,4 Tree

Leon .

8 min readJun 10, 2019

資料庫的底層元件簡單複習以及紀錄 : B - tree

M-way search tree
B - tree 的基本定義
與 B - treee 相關的理論（待補）
B - tree 的操作（delete代補）
B+ tree 的基本定義
B+ tree的操作

M-way Search Tree

談到B tree，必須要先從 m-way search tree 說起 :

External Search/Sort 資料量太大，無法一次置於memory中進行搜尋必須透過外部儲存裝置，e.g Disk 來保存在分批載入

因此，在Disk中，m-way search tree 常用來組織 Data Blocks

(降低Tree的高度 -> 可降低I/O次數 )

Theorem about m-way search tree’s height

高度H的m-way search tree 最多有(m^h)- 1/(m-1)個Node

高度H的m-way search tree 最多有(m^h)- 1個Key

B - tree

首先，B是Balance, 平衡的意思, 是一種平衡的m-way search tree，主要是用於磁碟等外部儲存的一種資料結構。

這裡稍微提一下"為何要使用B-tree"，其中包括磁碟存取資料的過程。

磁碟存取資料的基本過程

(i.) 根據磁柱號碼使磁頭移動到所需要的柱面上，這一個過程被稱為定位或是查找

(ii.) 根據磁盤面號來確定指定盤面上的磁道()

(iii.) 盤面確定以後, 盤面開始旋轉, 將指定磁區的磁軌段移動至磁頭下

2.磁碟讀取資料是以block為基本單位的, 因此儘量將相關資訊存放在同一個磁區, 同一磁軌中, 以便在讀寫資料時儘量減少磁頭來回移動的次數, 避免過多的查找時間.

3.當大量的資料儲存在磁碟中時, 如何高效地查詢磁碟中的資料, 就需要一種合理高效的資料結構了.

檔案系統或著是資料庫為了增加搜尋的效率, 就可以採用此資料結構. 在資料量變大時, 若用線性搜尋檔案中的紀錄, 效率其實是不好的, 所以這時候就可以建立索引(index), 但資料量又再度增加時, index檔案也會變得很龐大. 為此, 需要一個有效率的搜尋索引, 才能有效率的找到結果。

B - tree 的基本定義

B tree 又依照其 order (Degree)分為許多的種類，而若無特別指定其order 則以 order＝m 作為預設。

倘若 m = 3 :

則上述公式

會變成

整棵樹只有兩種Node :

(a). 2-Node

(b). 3-Node

如此就變成有名的 2-3 Tree

同理，若m=4 ，則有:

就變成 2-3-4 Tree

NOTE : 如果m=2，則退化成Binary Tree … (1≤Degree≤2)，而且為了滿足所有Failure Node都位於同一Level，他其實是”Full” Binary Tree.

Theorem about B tree’s height

高度H，最多Node數有(m^h)- 1/(m-1) (同m-way search tree)
高度H，最多Key數有(m^h)- 1(同m-way search tree)
高度H，最少Node數
高度H，最少Key數

B — tree ‘s Operation

Insert

1.尋找data應該被放在哪個葉子。
2.如果葉子還沒滿，放入後結束。
3.如果葉子滿了(>m-1)：(Split)
 a)先把它大力地硬插進去這個node。
 b)找到中間值(ceil(m/2))，拆成左邊的node和右邊的node，並把中間值上提拿給老爸。
 c)上提後的中間值，左pointer值向剛剛左邊的node，右邊同理。
 d)因為老爸多了一個data，檢查老爸有沒有滿(遞迴步驟2or3)。

Time complexity : O(log_mN) [O(logN)]

Build

不停地執行Insert Operation，記得每次都需要檢查是否達到m，然後split。

Time complexity : O(N*log_mN) [O(NlogN)]

Search

在B Tree中搜尋n
1.從root開始，檢查數字n是否在該node中。
2.如果在該node找不到，找出n介於哪兩個數a,b之間，改為拜訪a,b之間的pointer指向的node。
3.若拜訪到的node為NULL，表示找不到該數字。

Delete

先做Search Operation 找到 x，再依 x 所在位置分成兩種Case討論 :

x 在Lea fNode

a.)刪除 x
b.)檢查此Node是否有underflow(key數 < ceil(m)-1)
  ( I.)若無underflow，完成。
  (II.)若underflow:
        1.若可以使用"Rotation"處理，則Rotation後，完成。
        2.若不能則需做"Combine"處理，並且combine後還需針對檢查underflow。

2. x 在Internal Node

a.)先以x的左子樹中最大的Element取代(或是右子樹中最小的Element取代)
b.)此時相當於刪除了某一個Leaf Node，所以在使用上述的刪除x在Leaf Node的方式。

B+ tree

接下來，來談談B tree的進化版本: B+ tree 。

首先，先看看B+ tree 長什麼樣子

可以看到Node之間不只有 "重複的Element"，而且Leaf Node 還用pointer連在一起。

而且，所有父節點的最大(或最小)的Element都出現在子節點中

需要注意的是 :

Root 的最大元素(這裡是15)，也就是等同於整個B+ tree的最大元素。

以後無論insert多少元素，也要保持最大元素在Root

這裡給出B+ tree的統整定義

Create/Insert B+ tree

這邊給個原則(同B tree)，其他用圖例帶過

1.尋找data應該被放在哪個葉子。
2.如果葉子還沒滿，放入後結束。
3.如果葉子滿了：(Split)
    a)先把它大力地硬插進去這個node。
    b)找到中間值，拆成左邊的node和右邊的node，並把中間值上提拿給老爸。
    c)上提後的中間值，左pointer值向剛剛左邊的node，右邊同理。
    d)因為老爸多了一個data，檢查老爸有沒有滿(遞迴步驟2or3)。

其中 Split 的動作我們分成: