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

一、 基本概念與文件邏輯結(jié)構(gòu)

1. 文件與記錄：文件是存儲在外存上的、由大量性質(zhì)相同的記錄組成的集合。記錄是文件中可操作的基本數(shù)據(jù)單位，由若干數(shù)據(jù)項(xiàng)（字段）構(gòu)成。每個記錄通常包含一個能唯一標(biāo)識該記錄的關(guān)鍵字（Key）。
2. 文件的邏輯結(jié)構(gòu)：指用戶或應(yīng)用程序所看到的文件組織形式。

• 流式文件：文件內(nèi)容被視為一個無結(jié)構(gòu)的字符流（如文本文件、源程序文件）。

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

二、 文件的物理結(jié)構(gòu)（存儲結(jié)構(gòu)）

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

1. 順序文件（順序結(jié)構(gòu)）：記錄按其進(jìn)入文件的先后順序連續(xù)存放。

• 特點(diǎn)：批量存取（尤其是順序存取）效率高，但插入、刪除記錄困難，通常需重組文件。

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

1. 索引文件：由主文件（數(shù)據(jù)區(qū)） 和索引表兩部分構(gòu)成。索引表本身是一個文件，其記錄由關(guān)鍵字和對應(yīng)主文件記錄地址組成，并按關(guān)鍵字有序。

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

• 多級索引：當(dāng)索引表很大時，可為其再建立索引，形成樹形結(jié)構(gòu)（如ISAM）。

1. 索引順序文件（ISAM, VSAM）：是順序文件和索引文件的結(jié)合，在實(shí)踐中應(yīng)用廣泛。

• ISAM（索引順序存取方法）：采用靜態(tài)索引結(jié)構(gòu)，由主索引、柱面索引、磁道索引和多級主文件（柱面、磁道）構(gòu)成。插入記錄時使用溢出區(qū)，刪除記錄做標(biāo)記。定期需重組文件以恢復(fù)性能。

• VSAM（虛擬存儲存取方法）：采用B+樹動態(tài)索引結(jié)構(gòu)。文件由索引集、順序集（葉子節(jié)點(diǎn)，包含全部關(guān)鍵字和指針）和數(shù)據(jù)集組成。插入、刪除靈活，無需重組文件，存取路徑與設(shè)備物理特性無關(guān)。

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

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

三、 文件的操作

1. 檢索（查找）：

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

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

• 按關(guān)鍵字存取：存取關(guān)鍵字等于給定值的記錄。

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

四、 存儲支持服務(wù)與多路歸并

處理海量數(shù)據(jù)（超出內(nèi)存容量）時，需要借助外部存儲和特定的算法。

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

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

• 敗者樹：一種高效實(shí)現(xiàn)多路歸并選擇最小/最大值的數(shù)據(jù)結(jié)構(gòu)。能在k個記錄中選擇最小者，其比較時間復(fù)雜度僅為O(log?k)，有效減少了關(guān)鍵字的比較次數(shù)。

1. 置換-選擇排序：用于生成初始?xì)w并段。在內(nèi)存工作區(qū)容量為w的情況下，可以生成平均長度大于2w的初始?xì)w并段，從而進(jìn)一步減少初始?xì)w并段數(shù)量，縮短后續(xù)歸并趟數(shù)。
2. 最佳歸并樹（哈夫曼樹的應(yīng)用）：當(dāng)初始?xì)w并段長度不等時，通過構(gòu)造以歸并段長度為權(quán)值的k叉哈夫曼樹，可以確定最優(yōu)的歸并順序，使總的I/O次數(shù)最少。

五、 知識要點(diǎn)與考查重點(diǎn)

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

第六章將數(shù)據(jù)結(jié)構(gòu)的視角從內(nèi)存擴(kuò)展到外存，闡述了在存儲層次中管理大規(guī)模數(shù)據(jù)集的經(jīng)典方法與支持服務(wù)，是構(gòu)建數(shù)據(jù)庫、文件系統(tǒng)等復(fù)雜軟件的重要基石。復(fù)習(xí)時需在理解概念的基礎(chǔ)上，重點(diǎn)掌握其設(shè)計(jì)思想與算法流程。