數(shù)據(jù)結(jié)構(gòu)與算法分析第8章.ppt

《數(shù)據(jù)結(jié)構(gòu)與算法分析第8章.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)與算法分析APracticalIntroductiontoDataStructuresandAlgorithmAnalysis陳星第8章文件管理和外排序外排序：因數(shù)據(jù)量太大，不能將它們同時放在主存中。因此需要將全部數(shù)據(jù)放入磁盤，每次選擇部分?jǐn)?shù)據(jù)到主存進(jìn)行處理。8.1主存儲器和輔助存儲器主存儲器：隨機(jī)訪問存儲器（RAM）。輔助存儲器：硬盤、軟盤和磁帶等。主存儲器和輔助存儲器的比較主存儲器輔助存儲器價格昂貴（高兩個數(shù)量級）便宜存儲時間易失長期便攜性不具備具備讀寫速度快（10～100萬倍）慢容量小大盡可能減小對磁盤的訪問次數(shù)原則減小磁盤訪問次數(shù)的方法盡可

2、能少（最好一次）的訪問次數(shù)得到所需數(shù)據(jù)。每次磁盤訪問得到更多的數(shù)據(jù)，減少將來的訪問需要。一種實(shí)用的方法：壓縮存儲在磁盤中的信息。原理：用增加的CPU時間（壓縮和解壓數(shù)據(jù)）換取縮短的磁盤訪問時間。問題：不允許隨機(jī)訪問被壓縮文件的一部分。8.2磁盤磁盤：直接訪問存儲設(shè)備。磁帶：順序訪問存儲設(shè)備。盤片、磁道、柱面、扇區(qū)盤片以恒定速率轉(zhuǎn)動扇區(qū)每個磁道分為多個扇區(qū)。每個扇區(qū)有相同的數(shù)據(jù)量。一個扇區(qū)是一次讀出或?qū)懭氲淖钚?shù)據(jù)量。硬盤中讀寫數(shù)據(jù)的步驟：尋道：移動硬盤的I/O磁頭，定位到包含數(shù)據(jù)的磁道。（慢，占據(jù)讀寫數(shù)據(jù)的大部分時間）等待包含數(shù)據(jù)的扇區(qū)旋轉(zhuǎn)到磁頭下面。讀取或

3、寫入一個扇區(qū)的數(shù)據(jù)。安排扇區(qū)的交錯法：概念：引用的局部性：如果讀出文件的一個扇區(qū)，很可能就要讀出文件的下一個扇區(qū)。（假設(shè)）簇：多個扇區(qū)組成，為文件分配的最小單位，大小由操作系統(tǒng)所定。文件分配表：記錄哪些簇（扇區(qū)）屬于哪一個文件。范圍：一組物理上相連的簇。內(nèi)部碎片：由于數(shù)據(jù)沒有填滿一個扇區(qū)或一個簇而浪費(fèi)的存儲空間。8.2.2磁盤訪問代價訪問磁盤中信息的主要代價一般是尋道時間。尋道時間依賴于磁頭當(dāng)前所在的磁道與將要訪問的目標(biāo)磁道之間的距離，因此實(shí)際尋道時間差別很大。尋道時間可參考的兩個參數(shù)：磁道－磁道代價：磁頭從一個磁道移到相鄰磁道的最短時間。一次隨機(jī)訪問的平均

4、尋道時間。其它磁盤訪問代價：等待目標(biāo)扇區(qū)旋轉(zhuǎn)到磁頭下的時間。數(shù)據(jù)讀/寫時間。8.3緩沖區(qū)和緩沖池例8.1，讀取數(shù)據(jù)的時間代價：一個磁道（256個扇區(qū)）：一個扇區(qū)（512個字節(jié)）：9.5+11.1/2+(1/256)×11.1=15.1ms一個字節(jié)：9.5+11.1/2=15.05ms讀取的數(shù)據(jù)量對讀取時間影響不大。因此磁盤驅(qū)動器每次都是讀入或?qū)懭胝麄€扇區(qū)的數(shù)據(jù)。數(shù)據(jù)暫放在主存中，稱緩沖或緩存。緩沖：從磁盤中取出多余數(shù)據(jù)，以滿足將來的請求。緩沖技術(shù)可以減少數(shù)據(jù)從磁盤中讀取的次數(shù)。主存中通常建有多個輸入緩沖區(qū)和輸出緩沖區(qū)，緩沖區(qū)合起來稱為緩沖池。8.3緩沖區(qū)和緩

5、沖池當(dāng)緩沖池填滿后，替換緩沖區(qū)的方法：先進(jìn)先出法。最不頻繁使用法。最近最少使用法。虛擬存儲技術(shù)：將磁盤擴(kuò)展為主存的一部分。8.4程序員的文件視圖處理磁盤文件中記錄的方式：隨機(jī)訪問。順序訪問。8.5外部排序外部排序的特點(diǎn)：只能先將一些記錄從磁盤中讀出，進(jìn)行排序，再將記錄寫回磁盤。主要目標(biāo)：盡量減少磁盤訪問。在主存內(nèi)的內(nèi)部排序比讀寫磁盤的時間少。順序訪問磁盤中數(shù)據(jù)塊比隨機(jī)訪問更有效。但高效率的順序訪問要求：文件應(yīng)填充到連續(xù)的磁道中。順序訪問過程中，磁盤的I/O磁頭要始終在這個文件上，因此不同時處理兩個文件。只對關(guān)鍵碼排序，建立索引文件，而不是對整個記錄排序。8.

6、6外部排序的簡單方法內(nèi)部排序算法通常不適用于外部排序，如快速排序。一種較好的外部排序算法：改進(jìn)的歸并算法將被排序的子序列稱為順串（run）排序過程（P181）對有n條記錄的文件，外部歸并排序需要logn趟掃描，即每條記錄進(jìn)行l(wèi)ogn次磁盤讀寫。對外部歸并排序算法的改進(jìn)：對小的順串不做歸并排序。即對讀入主存的數(shù)據(jù)做內(nèi)部排序，并讀入盡可能多的數(shù)據(jù)，減小歸并排序的趟數(shù)。每一趟掃描歸并多個順串，即多路歸并技術(shù)。所有好的外部排序算法都是基于：把文件分成大的初始順串（讀入更多記錄到主存，執(zhí)行內(nèi)部排序）。把所有順串歸并在一起，形成一個已排序的文件。8.7置換選擇排序堆排序

7、算法的一個微小變體。如果分配給供內(nèi)部排序數(shù)組的可用主存大小是m條記錄，平均可創(chuàng)建2m條記錄的順串。置換選擇排序的過程：在可利用的內(nèi)存中構(gòu)建一個數(shù)組（堆）、一個輸入緩沖區(qū)和一個輸出緩沖區(qū)。從磁盤上讀取記錄填充數(shù)組。構(gòu)建一個最小值堆。設(shè)Last=m-1，m為數(shù)組大小，Last標(biāo)識堆中最后一個記錄。8.8多路歸并R個順串做二路歸并需要logR趟掃描。歸并時，每個順串只有一個塊的記錄在主存中，主存空間沒有得到充分利用。一次歸串多個順串，可以充分利用主存空間，并大大減少歸并的掃描趟數(shù)。