第3章 磁碟排序#

資料量大到主記憶體裝不下時，經典的快速排序、堆積排序全都失效——因為它們假設任意位置的資料都能以 O(1) 存取，而磁碟上每一次「跳躍式存取」都要付出一次 I/O 的代價。本章介紹磁碟時代的主力排序法：外部合併排序（external merge sort）。它的核心思想是把資料切成記憶體裝得下的段落（run），逐段排序後寫回磁碟，再以多路合併（k-way merge）把段落逐步合併成最終結果。

我們將實作完整的兩階段外部排序、探討替換選擇如何產生更長的初始段落、並建立精確的 I/O 成本模型：排序 N 頁資料到底要幾次磁碟讀寫。這些模型在資料庫查詢最佳化中直接被用來估計成本，是第 8 章查詢處理的基石。