1.4.4 B-Tree

B-Tree: B是Balance, 平衡的意思, 是一種平衡的多路搜尋樹, 主要是用於磁碟等外部儲存的一種資料結構, 例如用於文件索引.

磁碟存取資料:

1. 磁碟存取資料的基本過程

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

   2. 根據磁盤面號來確定指定盤面上的磁道

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

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

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

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

B-Tree的特性:

對於一顆m階(階指的是子節點的最大數目)的B-Tree, 有如下特性:

1. 根節點要就是葉子, 不然至少有兩個子節點

2. 每個節點最多含有m個節點(m ≥ 2)

3. 除了根節點和葉節點之外, 其他每個節點至少有[ceil(m/2)]個子節點

4. 所有的葉節點都出現在同一層上

5. 有s個子節點的非葉節點具有n = s - 1個關鍵字, 即s = n + 1

6. 每個非葉節點中包含有n個關鍵字訊息: (n, C0, K1, C1, K2, C2, ..., Kn, Cn), 其中:

   1. Ki (i = 1...n)為關鍵字, 且關鍵字按順序升序排序K(i-1) < Ki

   2. Ci為指向子樹根的節點, 且指標C(i-1)指向子樹中所有節點的關鍵字均小於Ki, 但都大於K(i-1)

   3. 關鍵字的個數n必須滿足: [ceil(m/2) - 1] ≤ n ≤ m-1

B-Tree的高度:

1. 就是B-Tree不包含葉節點的層數

2. 由於磁碟存取時的I/O次數, 與B樹的高度成正比, 高度越低, I/O次數也就越小, 因此理解如何計算B-Tree的高度是很有必要的

3. 假設若B-Tree總共包含N個關鍵字, 則此樹的葉節點可以有N+1個, 而所有的葉節點都在第K層, 可以得出:

   1. 因為根至少有兩個子節點, 因此第二層至少有兩個節點

   2. 除了根和葉之外, 其它節點至少有ceil(m/2)個子節點

   3. 因此在第3層至少有2*ceil(m/2)個節點

   4. 在第4層至少有2*(ceil(m/2)^2)個節點

   5. 在第k層至少有2*(ceil(m/2)^(k-2))個節點, 於是有: N+1 ≥ 2*(ceil(m/2)^(K-2)), 這就可以算出: K ≤ log(ceil(m/2))((N+1)/2)+2

   6. 由於計算B-Tree高度是不包含葉節點的層數, 所以B-Tree的高度 ≤ log(ceil(m/2))((N+1)/2) + 1