Away Search Tree 講解

內部搜尋

• 內部搜尋：資料量小，資料可全部置於記憶體中。
• 二元搜尋數 (Binary Search Tree) & AVL Tree：標準內部搜尋方法，適合資料量較小的情況。

外部搜尋

• 外部搜尋：資料量大，無法一次置於記憶體，需要依靠輔助儲存體（如硬碟）進行分段搜尋。
• 硬碟的瓶頸：硬碟是機械式運作，讀寫速度慢，成為效能瓶頸。

M-way Search Tree

• 用於外部搜尋，解決大數據無法放入記憶體的問題。
• 樹的Degree：大於2，壓縮樹的高度，降低Disk IO次數。

Disk IO & 效率

• 硬碟IO多，搜尋效率低。
• 樹的高度影響Disk IO次數，需降低高度以提升效率。
• 比喻：硬碟如蝸牛，主記憶體和CPU如兔子。

M-way Search Tree 結構

• 節點的Degree：節點分支度大於2，靈活調節樹高度。
• 資料量限制：一個節點存放的資料量為m-1。

M-way Search Tree 的特徵

• 節點資料由小到大排序。
• 每個節點的指數仍為M-way Search Tree。
• 節點內資料與分支的比對關係。

節點結構

• 節點包含資料和指標。
• 每個節點資料量小於等於m-1。
• 指標指向子節點，子節點資料介於其指標所連接的兩個資料值之間。

例子與應用

• 此樹用於進行高效的外部搜尋。
• 增加節點的Degree來壓縮樹的高度，減少Disk IO次數。
• 避免將所有資料置於單一節點中，以免無法充分利用記憶體。

總結

• M-way Search Tree 的使用能提升外部搜尋效率。
• 優化策略在於降低樹高度與Disk IO次數。
• 實際應用需考慮節點Degree與資料分佈的平衡。