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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、 文件的操作

1. 檢索（查找）：

• 順序存取：存取下一個(gè)邏輯記錄。

• 直接存取：存取第i個(gè)邏輯記錄。

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

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

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

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

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

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

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

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

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

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

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