王道考研數據結構第六章主要聚焦于數據處理與存儲支持服務，這部分內容是數據管理、文件組織以及外部存儲技術的基礎，對于理解大型系統中數據的有效組織和高效訪問至關重要。本章的核心在于理解如何在外部存儲（如磁盤）上組織和存取大量數據，其知識體系圍繞文件的邏輯結構、物理結構、操作以及相關支持技術展開。

一、 基本概念與文件邏輯結構

1. 文件與記錄：文件是存儲在外存上的、由大量性質相同的記錄組成的集合。記錄是文件中可操作的基本數據單位，由若干數據項（字段）構成。每個記錄通常包含一個能唯一標識該記錄的關鍵字（Key）。
2. 文件的邏輯結構：指用戶或應用程序所看到的文件組織形式。

• 流式文件：文件內容被視為一個無結構的字符流（如文本文件、源程序文件）。

• 記錄式文件：文件由若干邏輯記錄組成，記錄可順序或按關鍵字存取。這是本章討論的重點。

二、 文件的物理結構（存儲結構）

文件的物理結構定義了記錄在外存上的實際存儲與組織方式，直接影響存取效率。主要類型有：

1. 順序文件（順序結構）：記錄按其進入文件的先后順序連續存放。

• 特點：批量存?。ㄓ绕涫琼樞虼嫒。┬矢?，但插入、刪除記錄困難，通常需重組文件。

• 順序查找：可從頭開始依次查找，也可針對有序順序文件進行折半查找（需支持隨機存取）。

1. 索引文件：由主文件（數據區） 和索引表兩部分構成。索引表本身是一個文件，其記錄由關鍵字和對應主文件記錄地址組成，并按關鍵字有序。

• 特點：適合隨機存取和關鍵字查找。查找時先在有序索引表中快速定位（如折半查找），再根據地址訪問主文件記錄。

• 多級索引：當索引表很大時，可為其再建立索引，形成樹形結構（如ISAM）。

1. 索引順序文件（ISAM, VSAM）：是順序文件和索引文件的結合，在實踐中應用廣泛。

• ISAM（索引順序存取方法）：采用靜態索引結構，由主索引、柱面索引、磁道索引和多級主文件（柱面、磁道）構成。插入記錄時使用溢出區，刪除記錄做標記。定期需重組文件以恢復性能。

• VSAM（虛擬存儲存取方法）：采用B+樹動態索引結構。文件由索引集、順序集（葉子節點，包含全部關鍵字和指針）和數據集組成。插入、刪除靈活，無需重組文件，存取路徑與設備物理特性無關。

1. 散列文件（直接存取文件）：根據記錄的關鍵字，通過散列函數直接計算其在外存上的存儲地址（通常是桶Bucket的地址）。

• 特點：隨機存取速度極快，但散列沖突不可避免，處理沖突會降低效率（常用鏈地址法，將同義詞記錄鏈在同一桶內或溢出桶中）。不支持順序存取和范圍查詢。

三、 文件的操作

1. 檢索（查找）：

• 順序存取：存取下一個邏輯記錄。

• 直接存取：存取第i個邏輯記錄。

• 按關鍵字存取：存取關鍵字等于給定值的記錄。

1. 插入：將新記錄寫入文件。
2. 刪除：從文件中刪去指定記錄。
3. 修改：更改指定記錄的部分字段值。
4. 排序：按指定關鍵字對文件中的記錄進行排序，是許多操作（如高效檢索、歸并）的基礎。

四、 存儲支持服務與多路歸并

處理海量數據（超出內存容量）時，需要借助外部存儲和特定的算法。

1. 外排序：對大文件進行排序，數據主要存放在外存，排序過程中需要在內存與外存之間多次交換數據。
2. 歸并排序思想：是外排序的核心。先將大文件分割成若干能裝入內存的子文件（段），分別調入內存進行內排序，形成初始歸并段（順串） 寫回外存。然后對這些歸并段進行多路歸并，最終合并成一個有序文件。
3. 多路平衡歸并：

• 過程：一次性將k個歸并段中當前最小的記錄比較選出，送入輸出緩沖區，寫回磁盤。減少歸并趟數，從而減少I/O次數。k越大，趟數越少。

• 敗者樹：一種高效實現多路歸并選擇最小/最大值的數據結構。能在k個記錄中選擇最小者，其比較時間復雜度僅為O(log?k)，有效減少了關鍵字的比較次數。

1. 置換-選擇排序：用于生成初始歸并段。在內存工作區容量為w的情況下，可以生成平均長度大于2w的初始歸并段，從而進一步減少初始歸并段數量，縮短后續歸并趟數。
2. 最佳歸并樹（哈夫曼樹的應用）：當初始歸并段長度不等時，通過構造以歸并段長度為權值的k叉哈夫曼樹，可以確定最優的歸并順序，使總的I/O次數最少。

五、 知識要點與考查重點

• 理解與比較：深刻理解順序、索引、索引順序、散列四種文件物理結構的原理、優缺點及適用場景（如順序存取 vs 隨機存取，靜態 vs 動態）。
• 掌握操作效率：能分析在不同文件結構下進行檢索、插入、刪除等操作的大致時間開銷（與I/O次數相關）。
• 聚焦外排序：掌握多路平衡歸并的過程、敗者樹的作用與構建、置換-選擇排序生成初始歸并段的流程，以及最佳歸并樹的構造與應用。這是考研中的高頻計算和設計題考點。
• 聯系前后章節：本章的索引技術與前面的查找表（特別是B樹/B+樹）、散列技術緊密相關；外排序中的歸并與內排序算法一脈相承。

第六章將數據結構的視角從內存擴展到外存，闡述了在存儲層次中管理大規模數據集的經典方法與支持服務，是構建數據庫、文件系統等復雜軟件的重要基石。復習時需在理解概念的基礎上，重點掌握其設計思想與算法流程。