關系模型中，表中的元組本身并沒有特定的順序。然而，許多數據庫查詢操作，例如 ORDER BY 子句、JOIN 操作、DISTINCT 去重以及 GROUP BY 聚合，都需要對數據進行排序。此外，將已排序的元組批量加載到 B+Tree 索引中也更加高效。本課程的核心目標之一，便是探討如何在數據量遠超可用內存的情況下， 有效地排序和聚合大量數據，同時最大限度地減少磁盤 I/O 操作 。

內存不足時的大數據排序：外部歸并排序 (External Merge Sort)

當整個數據集無法完全加載到內存中時，傳統的內存排序算法（如快速排序 QuickSort 或堆排序 HeapSort）會因頻繁的隨機磁盤 I/O 而變得極其低效。為此，數據庫系統采用 外部歸并排序（External Merge Sort） ，這是一種 分而治之 (Divide-and-Conquer) 的排序算法。

其基本思路分為兩個階段：

第一階段：排序 (Phase #1 – Sorting)

• 系統會 讀取盡可能多的數據塊（通常為 B 個頁面，B 為可用緩沖區頁數）到內存中 。
• 在內存中對這些數據進行 就地排序 ，形成一個個 “運行” (runs) 。
• 將這些已排序的運行 寫回磁盤 。
• 這個過程會一直重復，直到所有原始數據都被分塊排序并寫回磁盤。

第二階段：合并 (Phase #2 – Merging)

• 在后續的趟（pass）中，系統會 將之前生成的多個小規模已排序運行合并成更大的已排序運行 。
• 這個過程會 反復進行 ，直到所有運行被合并成一個完整的、已排序的數據集。

為了提高合并效率，通常采用 K 路歸并 (K-way Merge) 的方式，而非簡單的 2 路歸并。在 K 路歸并中，系統會同時合并 K 個已排序的運行。對于外部歸并排序，這意味著在合并階段，數據庫系統將 B-1 個緩沖區頁用于輸入，將 1 個緩沖區頁用于輸出?？偟?I/O 成本通常為 2N * (# passes)，其中 N 是頁數，# passes 的計算公式為 1 + ?logB-1 ?N / B? ?。

優化策略

• 雙重緩沖 (Double Buffering) ：為了最大限度地提高順序 I/O 的效率并減少等待時間，系統會 預取 (Prefetch) 后續需要處理的運行到后臺的第二個緩沖區中。這意味著當 CPU 正在處理當前的數據時，異步 I/O 操作（通常由操作系統或專門的 I/O 調度線程處理）會同時從磁盤中讀取下一批數據。這樣就實現了 CPU 計算和磁盤 I/O 的重疊執行 ，避免了兩者之間的乒乓效應，從而提高了整體性能。

利用 B+Tree 加速排序

• 如果表上已經存在 B+Tree 索引，并且需要排序的鍵與索引鍵相同，那么可以利用 B+Tree 來加速排序操作。
• 聚簇 B+Tree (Clustered B+Tree) ：如果 B+Tree 是聚簇索引（意味著數據元組的物理存儲順序與索引鍵的邏輯順序一致），那么只需遍歷 B+Tree 的葉子頁面（這些頁面本身就是按序排列的）即可直接獲取已排序的數據。這種方式的效率極高，因為它 不涉及額外的計算成本，且所有磁盤訪問都是順序的 。
• 非聚簇 B+Tree (Unclustered B+Tree) ：相比之下，如果 B+Tree 是非聚簇索引（即索引的排序順序與數據元組的物理存儲位置無關），那么利用它進行排序通常是一個 非常糟糕的選擇 。因為對于每個記錄，都需要追逐指針到其存儲的數據頁，這會導致大量的 隨機磁盤 I/O ，性能會非常差。

聚合操作 (Aggregations)

聚合操作是將多個元組的值合并成一個單一的標量值，例如 COUNT、SUM、AVG、MIN、MAX 等。數據庫系統通常有兩種主要的實現方式： 基于排序的聚合 和 基于哈希的聚合 。

基于排序的聚合 (Sorting Aggregation)

思路非常直接 ：首先根據 GROUP BY 的鍵對數據進行排序（如果數據量大，會使用外部歸并排序）。

一旦數據排序完成，只需 對已排序的數據進行一次順序掃描 (Sequential Scan) ，即可輕松地計算聚合結果或消除重復項（如 DISTINCT）。當掃描到同一鍵值的連續元組時，可以直接進行聚合計算。

優點 ：如果查詢結果本身就需要按聚合鍵排序，那么這種方法非常高效，因為排序一次滿足了兩個需求。

缺點 ：如果查詢結果不要求有序，那么排序過程本身的成本可能較高。

基于哈希的聚合 (Hashing Aggregate)

如果聚合查詢結果不要求有序，哈希方法通常會更快 ，因為它在計算上可能比排序更便宜。

當所有數據都 能放入內存時 ，系統會構建一個 臨時 (Ephemeral) 的哈希表。掃描輸入數據時，對于每個記錄，檢查哈希表中是否已存在對應條目：

• 對于 DISTINCT 操作，如果鍵已存在，則說明是重復項，直接丟棄。
• 對于 GROUP BY 操作，如果鍵已存在，則更新其對應的聚合值；否則，插入新條目。

如果數據量太大，哈希表在內存中放不下 ，則需要使用 外部哈希聚合 (External Hashing Aggregate) ，它同樣采用分而治之的策略來應對磁盤溢出。這個過程分為兩個階段：

第一階段：分區 (Phase #1 – Partition)

• 使用第一個哈希函數 h1 將元組 分割到磁盤上的不同分區（桶）中 。
• 關鍵是哈希函數的確定性 ：具有相同鍵值的元組將始終落入同一個分區。
• 系統利用緩沖區管理器將這些分區的數據 溢出到磁盤 。通常，B-1 個緩沖區頁用于不同的輸出分區，1 個緩沖區頁用于輸入數據。

第二階段：重哈希 (Phase #2 – ReHash)

• 對于磁盤上的每個分區，將其數據 讀入內存 。
• 在內存中，使用 第二個哈希函數 h2 (與 h1 不同) 再次構建一個哈希表。 通過分區，保證處理每個小塊時，同一個鍵值的所有元組都集中在該分區內 ，因此可以對該分區的所有數據進行聚合計算。
• 這個階段 假設每個分區都足夠小，可以完全加載到內存中 。
• 在重哈希階段，哈希表會存儲 (GroupKey → RunningValue) 形式的鍵值對。RunningValue 的內容取決于具體的聚合函數（例如，AVG 會維護 (COUNT, SUM)，MIN 維護 (MIN) 等）。當遇到一個元組時，如果 GroupKey 已存在，則更新 RunningValue；否則，插入新的鍵值對。

無論是排序還是哈希，這兩種技術都體現了數據庫系統設計中的一個核心理念： 將大的問題分解為小的、可管理的單元進行處理，并優先采用能夠最大化順序 I/O 的算法 。這對于處理磁盤數據至關重要，因為順序 I/O 遠比隨機 I/O 效率更高。