# 1.4.4 B-Tree

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

磁碟存取資料:

1. 磁碟存取資料的基本過程
   1. 根據磁柱號碼使磁頭移動到所需要的柱面上, 這一個過程被稱為定位或是查找
   2. 根據磁盤面號來確定指定盤面上的磁道
   3. 盤面確定以後, 盤面開始旋轉, 將指定磁區的磁軌段移動至磁頭下
2. 磁碟讀取資料是以block為基本單位的, 因此儘量將相關資訊存放在同一個磁區, 同一磁軌中, 以便在讀寫資料時儘量減少磁頭來回移動的次數, 避免過多的查找時間.
3. 當大量的資料儲存在磁碟中時, 如何高效地查詢磁碟中的資料, 就需要一種合理高效的資料結構了.

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

B-Tree的特性:

![](https://649506553-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o38bFiI5-RlHn7V%2F-M523rpyYLd_bz4SsJlN%2F-M523tOHEyB7KQPQHxX8%2FB-Tree.png?generation=1587042033650963\&alt=media)

對於一顆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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://clu.gitbook.io/data-structure-note/b-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.