今天要進入新的大主題：外部搜尋

何謂外部搜尋（External search）

指的是：資料量太大，沒辦法一次將所有資料 load 進 memory 進行搜尋，必須使用「外部儲存體」如 disk。透過切割區塊（block）的方式，分批查找。

而最適合的結構就是：m-way search tree (m > 2)，許多 disk 和 database 都使用 m-way search tree 來組織資料區塊。

m-way search tree

定義如下：

1. 每個節點的 degree: 0 <= degree <= m
2. node 的 key 數為 degree - 1，且由小到大排序 ascending order
3. search/insert/delete 的時間為 O(H)，H 為樹高

圖示：4-way search tree (m = 4)

m-way search tree 最多節點數

第一層最多為 1 顆 root
第二層最多為 m 顆 nodes
第三層最多為 m^2 顆 nodes
到第 H 層最多為 m^(H - 1) 顆 nodes

加總起來就等於：(m^H - 1) / (m - 1)

m-way search tree 最多鍵值（key）數

總共最多有 (m^H - 1) / (m - 1) 顆 nodes，每顆 nodes 又有 m - 1 個 keys，因此最多鍵值數為 (m^H - 1) 個

m-way search tree 的大問題

跟 binary search tree 一樣，search/insert/delete 的時間為 O(H)，H 為樹高，此時如果樹為 skewed，則時間又退化。

在二元搜尋樹中，我們將其平衡，形成 Red-Black Tree 或 AVL tree，讓他的效率變成 O(logn)，因此，m-way search tree 也需要平衡。

今天我們講得比較少，明天就要來介紹平衡過後的 m-way search tree：B tree