當(dāng)前位置：首頁 > news >正文

溧陽網(wǎng)站建設(shè)哪家好長沙百度快速排名

news 2025/7/14 22:54:47

溧陽網(wǎng)站建設(shè)哪家好,長沙百度快速排名,鮮花商城網(wǎng)站設(shè)計,服裝產(chǎn)品展示網(wǎng)站模板外部排序外存信息的存取計算基本存儲方式內(nèi)部存儲（主存）：斷電后數(shù)據(jù)會丟失，訪問速度快，成本高容量通常較小外部存儲（輔存）：斷電后數(shù)據(jù)不會丟失，訪問速度較慢&#x…

外部排序

外存信息的存取

計算基本存儲方式
- 內(nèi)部存儲（主存）：斷電后數(shù)據(jù)會丟失，訪問速度快，成本高容量通常較小
- 外部存儲（輔存）：斷電后數(shù)據(jù)不會丟失，訪問速度較慢，成本低容量通常較大
常見外存
- 磁帶：低成本存儲，適合長期歸檔，低能耗，但訪問速度慢。
- 磁盤（HDD）：提供較高性價比，適合大量數(shù)據(jù)存儲，隨機讀寫較慢，耐用性較好。
- 固態(tài)硬盤（SSD）：速度快，無機械部件，適合快速訪問需求，價格相對高但持續(xù)下降，壽命受寫入量限制。
磁帶存儲技術(shù)
- 磁帶結(jié)構(gòu)：磁帶是一種涂有磁性材料的窄帶
- 讀寫機制：磁帶通過驅(qū)動器控制轉(zhuǎn)動，以200英寸/秒的速度移動，并且是按需啟停的
- 間隙（IRG）：由于啟停需要一段時間才能達到穩(wěn)定狀態(tài)，所以字符組間需留空白區(qū)（IRG），影響磁帶利用率
- 成塊技術(shù)：為提高磁帶利用率，將多個字符組合并成塊寫入，減少IRG，增加數(shù)據(jù)緊湊性。物理塊大小通常限制在1K字節(jié)到8K字節(jié)之間，以平衡效率和可靠性（太大會出錯）
- I/O操作優(yōu)化：通過成塊，一次I/O可讀取整個物理塊到緩沖區(qū)，減少單個字符組的讀寫操作，提升效率。
  外部排序指的是大文件的排序，即待排序的記錄存儲在外存儲器上，在排序過程中需進行多次的內(nèi)、外存之間的交換。
- 在磁帶上讀寫一塊信息所需的時間 $T_{I/O}=t_a+n*t_w$ ，其中 $t_a$ 為延遲時間（讀/寫頭到達傳輸信息所在物理塊起始位置所需時間）， $t_w$ 為傳輸一個字符的時間
磁盤存儲技術(shù)
- 直接存取：與順序存取的磁帶不同，磁盤允許直接存取任何字符組
- 容量與速度：磁盤容量大，存取速度快，遠超磁帶。
- 盤片組成：磁盤可以是單片或多片盤組，每片有兩個面，但最頂和最底面不存信息。
- 驅(qū)動器功能：磁盤驅(qū)動器負(fù)責(zé)執(zhí)行讀/寫操作，盤片繞主軸高速旋轉(zhuǎn)。
- 磁頭類型：固定頭盤的每個磁道有獨立磁頭，而活動頭盤磁頭可移動
- 定位機制：磁盤上信息定位需用柱面號、盤面號、塊號的三維地址。
- 讀寫時間：磁盤讀寫時間包括尋查時間、等待時間和傳輸時間。
- 優(yōu)化策略：相關(guān)數(shù)據(jù)應(yīng)放在同一柱面或鄰近柱面，以減少磁頭移動次數(shù)，提高效率。
- 磁盤上讀取一塊信息所需的時間 $T_{I/O}=t_{f}+t_{l}+n*t_w$
  - $t_{f}$ 尋道時間：將磁頭移動到指定磁道所需要的時間
  - $t_{l}$ 延遲時間：磁頭定位到某一磁道的扇區(qū)所需要的時間
  - $t_w$ 傳輸時間：從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)歷的時間
  - 啟動時間：（一般忽略）：控制器的啟動時間。

外部排序的方法

外部排序的步驟
- 按可用內(nèi)存大小，將外存上含n個記錄的文件分成若干長度為l的子文件或端，這些子文件和段稱為歸并段或順串，將這些段一次讀入內(nèi)存，然后進行內(nèi)部排序，將獲得的有序的子文件重新寫入外存。
- 對這些有序子文件進行逐趟歸并，直至得到整個有序文件。
二路歸并算法步驟
- 每次將兩個頁塊讀取到磁盤中，進行內(nèi)排序后寫回到磁盤中
- 然后重復(fù)上述步驟，兩兩歸并，直到形成一個有序文件
提高外存讀寫效率的主要方法
- 多路歸并：通過多路歸并可以減少文件歸并的趟數(shù)，從而提高效率。
- 增加歸并段長度：增加歸并段的長度可以減少初始歸并的數(shù)目，降低處理時間。
- 最佳歸并方案：根據(jù)不同歸并段的長度，采取最佳歸并方案以優(yōu)化性能。
外排序的總時間由三部分組成：
- 產(chǎn)生初始歸并段的時間（內(nèi)排序）：
  $\times 得到一個歸并段的內(nèi)排序時間t_{is}$
- I/O操作的時間： $\times 一次讀寫的時間t_{io}$
- 內(nèi)部歸并的時間：
  $\times 對u個記錄進行一趟內(nèi)部歸并排序的時間t_{mg}$
影響外排序效率的主要原因：內(nèi)、外存之間數(shù)據(jù)交換的速度。

多路平衡歸并的實現(xiàn)

二路歸并
- 令 u 個記錄分布在兩個歸并段上，按 merge 過程進行歸并。
- 每得到歸并后的一個記錄，僅需一次比較即可，得到含 u 個記錄的歸并段需進行 u - 1 次比較。
k路歸并
- 令 u 個記錄分布在 k 個歸并段上，歸并后的第一個記錄是 k 個歸并段中關(guān)鍵字最小的記錄，需從每個歸并段的第一個記錄的相互比較中選出最小者，進行 k - 1 次比較。
- 每得到歸并后的有序段中的一個記錄，都要進行k - 1 次比較，得到含 u 個記錄的歸并段需進行（u - 1）（k - 1）次比較。
多路歸并的優(yōu)化
- 問題：k越大，內(nèi)部歸并的代價也會增大，當(dāng)其大于從外存讀取減少的代價，則內(nèi)部歸并就失去了其意義。
- 解決方法：使用敗者樹，在k-路歸并時，用于快速選出關(guān)鍵字最小的記錄，從而減少比較次數(shù)
對比：普通多路歸并需要k-1次比較，而敗者樹只需要 $O(klog_2k)$ 的構(gòu)建時間，但經(jīng)過 $O(log_2k)$ 次比較即可。假設(shè)k=5，則普通多路需要4次，敗者樹只需要2.321928次
三種最值結(jié)構(gòu)的不同
- 堆：每次調(diào)整需要父親和左右孩子進行比較，比較兩次
- 勝者樹：每次調(diào)整需要和兄弟節(jié)點進行比較
- 敗者樹：每次調(diào)整著需要和父親節(jié)點進行比較
敗者樹有幾個特點
- 是一顆用于高效合并 k 個有序序列的完全二叉樹
- 敗者樹的根結(jié)點記錄的是勝者，需要加一個結(jié)點來記錄整個比賽的最終敗者
- 建立一棵敗者樹的時間代價為 $O(klog_2k)$
- 從建立好的敗者樹獲取最值的時間代價為 $O(log_2k)$
- 敗者樹的建立和重構(gòu)僅僅涉及到父子節(jié)點之間的比較
生成過程
- 所有數(shù)字進行標(biāo)號作為葉子節(jié)點
- 每次比較將剩余的數(shù)值大的葉子節(jié)點的標(biāo)號寫入
- 最后根節(jié)點存儲
插入過程
- 再繼續(xù)新插入的節(jié)點從葉子節(jié)點開始，每次與父親節(jié)點進行比較，直到生成最終敗者
敗者樹的優(yōu)缺點
- 優(yōu)點：敗者樹優(yōu)化使得內(nèi)部歸并的比較次數(shù)與 k 無關(guān)，所以只要內(nèi)存空間允許，增大歸并路數(shù) k 將有效地減少歸并樹的高度，從而減少 I/O 次數(shù)，提高外部排序的速度。
- 當(dāng)歸并路數(shù) k 增大過大時，相應(yīng)地會增加輸入緩沖區(qū)的個數(shù)。所以會使得內(nèi)外存交換數(shù)據(jù)的次數(shù)增大

置換-選擇排序

概述
- 作用
  - 在處理大規(guī)模數(shù)據(jù)時，由于內(nèi)存容量有限，無法一次性將所有數(shù)據(jù)加載到內(nèi)存中進行排序
  - 置換 - 選擇排序可以有效地在有限內(nèi)存空間下，將大規(guī)模數(shù)據(jù)分批次處理，生成相對有序的歸并段，以便后續(xù)進行歸并操作，最終實現(xiàn)對大規(guī)模數(shù)據(jù)的排序。
步驟
- 設(shè)初始待排文件為 FI，初始歸并段輸出文件為 FO，內(nèi)存工作區(qū)為 WA，FO 和 WA 的初始狀態(tài)為空， WA 可容納 w 個記錄。
- ① 從 FI 輸入 w 個記錄到工作區(qū) WA 。
- ② 從 WA 中選出其中關(guān)鍵字取最小值的記錄，記為 MINIMAX 記錄。
- ③ 將 MINIMAX 記錄輸出到 FO 中去。
- ④ 若 FI 不空，則從 FI 輸入下一個記錄到 WA 中。
- ⑤ 從 WA 中所有關(guān)鍵字比 MINIMAX 記錄的關(guān)鍵字大的記錄中選出最小關(guān)鍵字記錄，作為新的 MINIMAX 記錄。
- ⑥ 重復(fù) ③-⑤，直至在 WA 中選不出新的 MINIMAX 記錄為止，由此得到一個初始歸并段，輸出一個歸并段的結(jié)束標(biāo)志到 FO 中去。
- ⑦ 重復(fù) ②-⑥，直至 WA 為空。由此得到全部初始歸并段。
- 【注：上述算法，在 WA 中選擇 MINIMAX 記錄的過程需利用敗者樹來實現(xiàn)?！?br />

最佳歸并樹

作用：將長度不等的歸并段進行多路平衡歸并，通過構(gòu)造最佳歸并樹進行優(yōu)化
特點
- 帶權(quán)路徑長度最小：最佳歸并樹是一棵哈夫曼樹，其帶權(quán)路徑長度最小，這意味著在進行歸并操作時，總的讀寫次數(shù)最少，從而提高了外部排序的效率。
- 減少 I/O 操作：通過最小化帶權(quán)路徑長度，最佳歸并樹可以減少歸并過程中的輸入 / 輸出（I/O）操作次數(shù)，這對于處理大規(guī)模數(shù)據(jù)非常重要，因為 I/O 操作通常是外部排序中最耗時的部分。
證明題
構(gòu)建步驟
- 確定歸并段數(shù)量和權(quán)值：首先確定初始歸并段的數(shù)量，并為每個歸并段賦予一個權(quán)值，通常權(quán)值可以是歸并段的長度或記錄數(shù)量。
- 構(gòu)建哈夫曼樹：將權(quán)值最小的兩個歸并段作為葉子節(jié)點，構(gòu)建一棵二叉樹，其根節(jié)點的權(quán)值為兩個葉子節(jié)點權(quán)值之和。重復(fù)這個過程，每次選擇權(quán)值最小的兩個節(jié)點構(gòu)建二叉樹，直到所有的歸并段都被包含在一棵樹中。
- 確定歸并順序：根據(jù)構(gòu)建好的哈夫曼樹，從根節(jié)點開始，按照左子樹優(yōu)先的順序進行遍歷，確定歸并的順序。每次歸并兩個子樹對應(yīng)的歸并段，直到所有的歸并段都被歸并為一個有序的文件。

文件

有關(guān)文件的基本概念

基本概念：
- 文件：性質(zhì)相同的記錄的集合。
- 記錄：文件中存取的基本單位
- 數(shù)據(jù)項/字段：文件可使用的最小單位
- 文件的操作
  - 檢索：順序、按關(guān)鍵字和隨機存取
  - 修改：插入、刪除和更新
  - 排序：可以實時處理或批量處理
文件的結(jié)構(gòu)
- 邏輯結(jié)構(gòu)：線性結(jié)構(gòu)。
- 物理結(jié)構(gòu)
  - 順序文件：按記錄進入文件的先后順序存放、其邏輯順序和物理順序一致的文件
  - 索引文件：在文件本身外，建立一張指明邏輯記錄和物理記錄之間映射關(guān)系的表
  - 索引順序存取方法(ISAM)文件
  - 虛擬存儲存取方法(VSAM)文件
  - 散列文件：利用散列存儲方式組織的文件，亦稱為直接存取文件。
  - 多關(guān)鍵字文件：對被查詢的次關(guān)鍵字也建立相應(yīng)的索引，則這種包含有多個次關(guān)鍵字索引的文件

順序文件

定義：文件物理結(jié)構(gòu)中的記錄順序和文件邏輯結(jié)構(gòu)中的記錄順序一致
組織形式:
- 連續(xù)文件(順序):次序相繼的記錄其存儲位置相鄰;
- 串聯(lián)文件（鏈?zhǔn)?#xff09;:物理記錄之間的順序由指針相鏈。
特點：
- 適合進行順序存取，但不便于進行直接存取，直接訪問某個特定記錄變得低效，尤其是當(dāng)文件很大時。
- 若記錄是有序的，則可以進行折半查找
- 插入新的記錄只能加在文件的末尾，因為文件中間的記錄不能被移動。
- 刪除記錄時，只作邏輯標(biāo)記，因為物理刪除記錄可能時間較長
- 更新副本：更新順序文件中的記錄通常需要創(chuàng)建一個新文件，將未更改的記錄和更新后的記錄寫入新文件，然后替換舊文件。
順序文件的批處理操作
- 定義：在順序文件中，插入、刪除和更新操作通常通過批處理方式進行，以提高效率
- 操作步驟：
  - 創(chuàng)建主文件（本體記錄）：主文件是已經(jīng)存在的有序文件，包含當(dāng)前的所有記錄。
  - 創(chuàng)建事務(wù)文件（增量邏輯）：事務(wù)文件包含所有需要插入和更新的記錄。這些記錄也需要被排序，以便于后續(xù)的合并操作。
  - 合并：將主文件和事務(wù)文件合并為一個新的有序文件。這個過程類似于歸并兩個有序表。
  - 刪除操作：在合并過程中，可以同時執(zhí)行刪除操作。通常，刪除操作是通過標(biāo)記已刪除的記錄來實現(xiàn)的，然后在合并時忽略這些記錄。
  - 生成新的主文件：合并完成后，新的有序文件成為新的主文件，替換舊的主文件。
假設(shè)主文件中有 $n$ 個記錄，事務(wù)文件中有 $m$ 個記錄：
- 對事務(wù)文件進行排序的時間復(fù)雜度為 $O (m l o g m)$ 。
- 內(nèi)部歸并的時間復(fù)雜度為 $O (m + n)$ 。
- 因此，總的內(nèi)部處理的時間復(fù)雜度為 $\log m + n)$
假設(shè)對外存進行一次讀/寫為 $s$ 個記錄，則整個批處理過程中讀/寫外存的次數(shù)為：
- 讀取主文件 $\frac{n}{s}$ 次。
- 讀取事務(wù)文件 $\frac{m}{s}$ 次。
- 寫入新主文件 $\frac{m+n}{s}$ 次。
- 整個批處理過程中讀/寫外存的總次數(shù)為 $\times \left( \frac{m}{s} + \frac{m+n}{s} \right)$ ，只需要對事務(wù)文件進行處理
文件的處理方式
- 實時處理：響應(yīng)時間要求嚴(yán)格
- 批量處理：響應(yīng)時間不是重要因素，提高整體效率是重要因素

索引文件

基本概念
- 組成：
  - 主文件：文件本身，包含所有記錄
  - 索引表：在文件外建立的表，指明邏輯記錄和物理記錄之間的對應(yīng)關(guān)系。
- 通常，索引文件中的主文件是無序文件，索引是（按關(guān)鍵字有序）的有序文件。
索引表組成：
- 索引表由多個索引項組成。
- 每個索引項包括主關(guān)鍵字和該關(guān)鍵字所在記錄的物理地址。
- 索引表必須按主關(guān)鍵字有序，而主文件本身可以有序或無序。
索引順序文件：
- 主文件按主關(guān)鍵字有序。
- 只對一個記錄塊（含多個有序記錄）建立一個索引項，
- 索引順序文件中的索引表為稀疏索引
索引非順序文件/索引文件
- 主文件按主關(guān)鍵字無序。
- 為每個記錄建立一個索引項，稱為稠密索引。
- 適合于隨機存取，不適合順序存取。
- 索引非順序文件中的索引表為稠密索引
區(qū)別
- 索引順序文件適合于隨機存取和順序存取。
- 索引順序文件的索引是稀疏索引，占用空間較少，是最常用的文件組織方式。
- 最常用的索引順序文件類型包括ISAM文件和VSAM文件。
若記錄很大使得索引表也很大時，可對索引表再建立索引，稱為查找表，通?？蛇_四級索引。
索引文件的存儲
- 索引區(qū)：存放索引表，占用空間較小
- 數(shù)據(jù)區(qū)：存放主文件。
存儲過程：
- 文件建立時，開辟一個索引區(qū)，通常固定在磁盤的一個或多個磁道上。
- 寫入記錄時，在索引區(qū)相應(yīng)登入一個索引項，記錄關(guān)鍵字和存儲地址。
- 文件建立后，將索引讀入內(nèi)存緩沖區(qū)，按關(guān)鍵字排序。
- 最終將排序好的索引項寫回到磁盤上的索引區(qū)。
檢索過程
- 預(yù)查找/讀索引：將含有索引區(qū)的頁塊送入內(nèi)存，查找所需記錄的物理地址。
- 讀取記錄/讀文件：根據(jù)已查到的地址，從外存讀取所查的記錄
注意事項：

索引表不大時：索引表可一次讀入內(nèi)存，檢索只需兩次訪問外存。
查找方法：由于索引表有序，可用順序查找或二分查找等方法。

ISAM文件

定義：
- ISAM（Indexed Sequential Access Method）是索引順序存取方法的縮寫。
- 專為磁盤存取文件設(shè)計，采用靜態(tài)索引結(jié)構(gòu)。
文件結(jié)構(gòu)：
- 記錄按關(guān)鍵字大小順序存放在磁盤的連續(xù)或相鄰的存儲區(qū)中。
- 文件劃分為若干個記錄塊，只為每塊中關(guān)鍵字最大（或最小）的記錄設(shè)置一個索引項。
索引結(jié)構(gòu)：
- 磁盤上的數(shù)據(jù)文件可以建立盤組、柱面和磁道三級索引。
- 每個柱面建立一個磁道索引，索引項包括關(guān)鍵字和指針。
- 柱面索引的索引項包括關(guān)鍵字和指向磁道索引的位置。
檢索操作：
- 從主索引出發(fā)找到相應(yīng)的柱面索引。
- 從柱面索引找到記錄所在柱面的磁道索引。
- 從磁道索引找到記錄所在磁道的第一個記錄的位置，然后順序查找。
插入操作：
- 將插入記錄置于數(shù)據(jù)區(qū)的末尾，并在索引表中插入索引項。
- 需要移動記錄并將同一磁道上最后一個記錄移至溢出區(qū)，同時修改磁道索引項。
刪除操作：
- 找到待刪除的記錄，在其存儲位置上作刪除標(biāo)記。
- 不需要移動記錄或改變指針。
溢出區(qū)：
- 每個柱面上還開辟有一個溢出區(qū)。
- 磁道索引項中有溢出索引項，這是為插入記錄所設(shè)置的。
文件整理：
- 經(jīng)過多次的增刪后，文件的結(jié)構(gòu)可能變得很不合理。
- 需要周期地整理ISAM文件，把記錄讀入內(nèi)存，重新排列，復(fù)制成一個新的ISAM文件，填滿基本區(qū)而空出溢出區(qū)。
溢出區(qū)的設(shè)置方法：
- 集中存放：整個文件設(shè)一個大的單一的溢出區(qū)。
- 分散存放：每個柱面設(shè)一個溢出區(qū)。
- 集中與分散相結(jié)合：記錄先移至每個柱面各自的溢出區(qū)，待滿之后再使用公共溢出區(qū)。
基本區(qū)與溢出區(qū)的結(jié)構(gòu)：
- 基本區(qū)是順序存儲結(jié)構(gòu)。
- 溢出區(qū)是鏈表結(jié)構(gòu)。
- 同一磁道溢出的記錄由指針相鏈。

VSAM文件

定義：
- VSAM（Virtual Storage Access Method）是虛擬存儲存取方法的縮寫。
- 采用B+樹作為動態(tài)索引結(jié)構(gòu)的索引順序文件組織方式。
B+Tree 數(shù)據(jù)結(jié)構(gòu)（MySQL InnoDB 的默認(rèn)索引數(shù)據(jù)結(jié)構(gòu)）
- 定義：B+樹可以分兩部分進行理解
  - 由非葉子結(jié)點組成的多路平衡查找樹用于快速的隨機查找操作
  - 由葉子結(jié)點組成的按主鍵順序的雙鏈表用于高效的數(shù)據(jù)的增刪操作和基于范圍的順序查找
- 多路平衡查找樹
  - 多路表示是一棵多叉樹（m>2），每個非葉子結(jié)點由兩部分組成
    - 按主鍵順序的子節(jié)點索引鏈表：每個子節(jié)點索引指向一個子節(jié)點，且索引結(jié)點鍵值等于索引子節(jié)點的最小鍵值（類似目錄查找）。
    - 最大和最小鍵值：主要用于快速定位和過濾查詢請求的。
  - 平衡表示B+樹的每個子樹的高度是相等的，盡可能“矮胖”
  - 查找表示B+樹的快速查找能力較強。
    - 相比B樹，非葉子結(jié)點不存放數(shù)據(jù)：可以存放更多的索引，使得樹更加“矮胖”，極大減少比較耗時的I/O操作。
    - 搜索復(fù)雜度為 $O(log_dN)$ ：當(dāng)最大分支數(shù)d大于100時，千萬級數(shù)據(jù)量的查詢操作也只需做 3~4 次的磁盤 I/O 操作，即樹的高度只有3~4層。
- 雙鏈表
  - 葉子結(jié)點的組成：一個葉子結(jié)點通常存儲多個數(shù)據(jù)記錄的物理地址，頁目錄由槽組成，索引數(shù)據(jù)記錄分組。數(shù)據(jù)記錄分組由數(shù)據(jù)記錄組成，按主鍵順序存儲可由二分法進行查找。
  - 提高磁盤IO效率：頁是磁盤IO的基本單位（默認(rèn)為16KB），通常與葉子結(jié)點一一對應(yīng)，但可以根據(jù)業(yè)務(wù)場景進行調(diào)節(jié)
  - 順序查找和增刪快：B+Tree 的層內(nèi)結(jié)點均按指定鍵順序進行雙鏈表鏈接?？梢愿咝M足數(shù)據(jù)的增刪操作和基于范圍的順序查找
VSAM文件的邏輯存儲單位：
- 控制區(qū)間：用戶進行一次存取的邏輯單位，可看作邏輯磁道，大小與物理磁道無關(guān)。
- 控制區(qū)域：由若干控制區(qū)間和它們的索引項組成，可看作邏輯柱面。
VSAM文件的記錄分布：
- 文件初建時，控制區(qū)間內(nèi)的記錄數(shù)不足額定數(shù)，有的控制區(qū)間的記錄數(shù)可能為零。
順序集和索引集：
- 順序集：本身是一個單鏈表，包含文件的全部索引項。
- 順序集中的每個結(jié)點即為B+樹的葉子結(jié)點。
- 索引集：結(jié)點即為B+樹的非葉結(jié)點。

直接存取文件/散列文件

基本概念
- 定義：根據(jù)記錄的關(guān)鍵字“直接”得到記錄在外存上的映象地址。
- 哈希文件的結(jié)構(gòu)：
  - 允許多個記錄映象到同一個地址上。
  - 外存儲器中存放多個記錄的“數(shù)據(jù)塊”稱為“桶”。
  - 由哈希函數(shù)得到的映象地址為“桶地址”。
- 哈希函數(shù)：根據(jù)文件中關(guān)鍵字的特點設(shè)計“哈希函數(shù)”。
- 處理沖突：當(dāng)多個記錄可能映象到同一個桶地址，需要有方法處理這種沖突。
檢索
- 只能進行按關(guān)鍵字的查找，不能進行順序查找
- 先在基桶內(nèi)進行查找，若基桶內(nèi)不存在，則再到溢出桶中進行查找
插入：當(dāng)查找不成功時，將記錄插入在相應(yīng)的基桶或溢出桶內(nèi)。
刪除
- 定義：對被刪記錄作特殊標(biāo)記，而不是真正從存儲中刪除。
- 操作：標(biāo)記記錄為已刪除。
直接存取文件的優(yōu)缺點
- 優(yōu)點
  - 記錄隨機存放：不需要進行排序。
  - 插入、刪除方便：操作簡單快捷。
  - 存取速度快：直接通過哈希函數(shù)定位記錄。
  - 節(jié)省存儲空間：不需要索引區(qū)。
- 缺點
  - 不能進行順序存取：只能按關(guān)鍵字查找。
  - 重組文件：在經(jīng)過多次插入和刪除操作之后，可能需要進行“重組文件”的操作以優(yōu)化文件結(jié)構(gòu)。

多關(guān)鍵字文件

主索引
- 按主關(guān)鍵字順序構(gòu)成的串聯(lián)文件
次索引
- 對各個次關(guān)鍵字項建立的索引記錄文件
- 次索引包含指向記錄的指針
多關(guān)鍵字文件的組織形式
- 多重鏈表文件
  - 記錄按主關(guān)鍵字的順序構(gòu)成一個串聯(lián)文件，并建立主關(guān)鍵字的索引（稱為主索引）；
  - 對每一個次關(guān)鍵字項建立次關(guān)鍵字索引（稱為次索引），所有具有同一關(guān)鍵字的記錄構(gòu)成一個鏈表。（次索引）
  - 主索引為非稠密索引，次索引為稠密索引；
  - 每個主索引項包括次關(guān)鍵字、頭指針和鏈表長度。
  - 容易插入，但是刪除需要在每個次索引表中進行刪除
- 倒排文件
  - 將所有具有相同次關(guān)鍵字的記錄構(gòu)成一個次索引順序表。
  - 在次索引順序表中僅存放記錄的“主關(guān)鍵字”或記錄的“物理記錄號”。
  - 次索引項中的“指針”指向相應(yīng)的次索引順序表。
  - 插入和刪除倒排表也要維護，處理困難
次關(guān)鍵字索引表的結(jié)構(gòu)
- 次關(guān)鍵字索引表本身的結(jié)構(gòu)可以是順序表，也可以是樹表或哈希表。
- 結(jié)構(gòu)的選擇視具體的次關(guān)鍵字的特性而定。