ch3 存儲和文件結(jié)構(gòu)

數(shù)據(jù)庫系統(tǒng)設(shè)計與實現(xiàn)SchoolofSoftwareEngineering

HuazhongUniversityofScience&TechnolongyChapter1:存儲和文件結(jié)構(gòu)StorageandFileStructureChapter1:存儲和文件結(jié)構(gòu)存儲介質(zhì)概述磁盤（MagneticDisks）和快閃存儲器（Flashstorage）RAID第三級存儲（TertiaryStorage）文件組織文件中記錄的組織數(shù)據(jù)字典存儲物理存儲介質(zhì)分類數(shù)據(jù)訪問的速度單位數(shù)據(jù)的成本可靠性掉電或者系統(tǒng)故障物理損壞存儲可以分為:易失性存儲（volatilestorage）:斷電之后數(shù)據(jù)丟失，高速緩存（cache）主存（mainmemory）非易失性存儲（non-volatilestorage）:斷電后數(shù)據(jù)仍然保存閃存（flashmemory）磁盤（magnetic-disk）光學(xué)存儲器（opticalstorage:compactdisk、digitalvideodisketc.）磁帶（tapestorage）物理存儲介質(zhì)高速緩沖存儲器（Cache）最快也最昂貴的存儲介質(zhì);易失的;由計算機(jī)系統(tǒng)硬件來管理.一般在數(shù)據(jù)庫系統(tǒng)中不需要考慮cache的存儲管理，但在設(shè)計查詢處理的數(shù)據(jù)結(jié)構(gòu)和算法時，實現(xiàn)者會注意高速緩沖存儲器的影響主存儲器（Mainmemory）讀取速度快(10~100s納秒;1納秒=10–9

秒)通常太小或者比較昂貴而不能用來存放整個數(shù)據(jù)庫目前廣泛采用的主存儲器可以存放幾個GB的數(shù)據(jù)；成本每年在穩(wěn)定地下降易失性

物理存儲介質(zhì)(Cont.)閃存（Flashmemory）

NAND快閃NOR快閃NOR—快閃允許隨機(jī)訪問閃存中的單個字，且擁有和主存媲美的讀取速度；

NAND—快閃每次需要讀取整個數(shù)據(jù)頁（512B~4kB）,類似于磁盤中的扇區(qū)，但NAND快閃擁有更高的存儲容量和性價比。電源關(guān)閉或者故障的時候數(shù)據(jù)可以保存；也作為磁盤存儲器的替代品——固態(tài)驅(qū)動器（Solid-StateDrive）和磁盤相比，提供更快的隨機(jī)存取，一個數(shù)據(jù)頁在閃存中1~2微秒可以檢測到，而在磁盤上的隨機(jī)訪問則需要5~10毫秒。但閃存具有比磁盤低的傳輸速率20MB/s物理存儲介質(zhì)(Cont.)問題：固態(tài)驅(qū)動器是如何實現(xiàn)的但是寫入較慢(約幾微秒)，而且閃存的頁面不能直接覆蓋，一旦寫入，必須先擦除然后再重寫，并且對閃存頁可以擦除多少次存在限制（100k~1M次之間）；閃存的寫入策略？閃存轉(zhuǎn)換層：（flashtranslationlayer）通過邏輯頁碼和物理頁碼的映射（轉(zhuǎn)換表）和損耗均衡在一定程度上解決慢訪問速度和更新次數(shù)限制的影響物理存儲介質(zhì)(Cont.)磁盤（Magnetic-disk）數(shù)據(jù)存放在盤片表面，表面覆蓋著磁性物質(zhì)是數(shù)據(jù)長期存儲的主要介質(zhì)，通常整個數(shù)據(jù)庫都存放在磁盤上；為了能夠訪問數(shù)據(jù)，系統(tǒng)必須先將數(shù)據(jù)從磁盤上移動到主存；存儲容量到2TB左右（2012）和主存及閃存相比，有更大的存儲容量和更低的的價格磁盤容量差不多以每年50%的速度遞增掉電或者系統(tǒng)故障不會丟失數(shù)據(jù)也可能發(fā)生硬盤故障，但幾率要小很多物理存儲介質(zhì)(Cont.)光學(xué)存儲器（Opticalstorage）非易失的，數(shù)據(jù)通過光學(xué)的方法存儲在光盤上CD-ROM(640MB)，DVD(4.7to17GB)藍(lán)光DVD,Blu-raydisks:27GBto54GBWORM:Write-one,read-manyMultiplewriteversions(CD-RW,DVD-RW,DVD+RW,andDVD-RAM)讀寫速度都要慢于磁盤物理存儲介質(zhì)(Cont.)磁帶存儲器（Tapestorage）非易失的

—主要應(yīng)用于備份和歸檔數(shù)據(jù)；順序訪問

—訪問速度要遠(yuǎn)低于磁盤具有很高的存儲容量(40to300GB)可以從磁帶設(shè)備中移除，非常適合便宜的歸檔存儲，磁帶很便宜，但磁帶驅(qū)動器相對昂貴自動磁帶機(jī)（Tapejukeboxes）用于存儲非常巨大的數(shù)據(jù)集合。存儲設(shè)備層次結(jié)構(gòu)基本存儲聯(lián)機(jī)存儲三級存儲易失性存儲非易失性存儲Fastestmediabutvolatile磁盤（magneticharddisk）（扇區(qū)）（柱面）（讀寫頭）（磁盤臂）（主軸）（磁道）（磁盤臂組件）（盤片）磁盤讀寫頭（Read-writehead）每個盤片（platter）的每一面都有一個讀寫頭緊貼著盤片表面通過讀寫磁性介質(zhì)來編碼信息每張盤片的表面被劃分為圓形磁道（track）典型的，每面盤片劃分成為50K-100K磁道每條磁道被劃分成為若干扇區(qū)（sectors）

扇區(qū)是讀寫的最小單位.現(xiàn)在典型的磁盤的每個扇區(qū)大小一般是512bytes每條磁道典型的扇區(qū)數(shù)目：內(nèi)側(cè)磁道每道約500-1000個扇區(qū)，外側(cè)磁道1000-2000個扇區(qū)Toread/writeasector磁盤臂（diskarm）把讀寫頭移動到相應(yīng)磁道；盤片旋轉(zhuǎn)使得對應(yīng)扇區(qū)到讀寫頭的下方柱面（Cylinder）

所有盤片的第i條磁道合在一起成為第i個柱面磁盤(Cont.)早期的磁盤比較容易發(fā)生故障讀寫頭接觸到盤片的表面，掛掉的介質(zhì)散落于盤片和其它讀寫頭之間，引起整張磁盤的實效目前的磁盤使用一層金屬薄膜作為存儲記錄的介質(zhì)，不易損壞磁盤控制器（Diskcontroller）–計算機(jī)系統(tǒng)和實際的磁盤驅(qū)動器硬件之間的接口（interface）.接受高層次的讀寫扇區(qū)的命令移動磁盤臂到對應(yīng)的磁道用校驗和（checksum）來判斷讀取的數(shù)據(jù)是否正確如果數(shù)據(jù)出錯，很有可能讀出數(shù)據(jù)所計算的校驗和存儲的校驗和不一致執(zhí)行壞扇區(qū)的重映射（remapping）當(dāng)磁盤初始格式化或者寫一個扇區(qū)時，如果磁盤控制器檢測到壞扇區(qū)，會把這個扇區(qū)在邏輯上映射到另外一個位置，多張磁盤通過一個高速互聯(lián)通道連接到計算機(jī)系統(tǒng)磁盤接口標(biāo)準(zhǔn)ATA(ATadaptor)rangeofstandards串行ATA(SATA:SerialATA，最新標(biāo)準(zhǔn)是SATAII,SATAIII等)小型計算機(jī)互聯(lián)系統(tǒng)SCSI(SmallComputerSystemInterconnect)串行附著SCSI(SAS:SerialAttachedSCSI)光纖通道接口（FC:FibrreChannel）磁盤系統(tǒng)磁盤通常可以通過電纜直接與計算機(jī)系統(tǒng)的磁盤接口相連，也可以放置在遠(yuǎn)端并通過高速網(wǎng)絡(luò)與磁盤控制器相連存儲局域網(wǎng)（StorageAreaNetworks，SAN）,大量的磁盤通過網(wǎng)絡(luò)和許多計算機(jī)服務(wù)器相連RAID網(wǎng)路附加存儲（NetworkAttachedStorage，NAS）通過使用網(wǎng)絡(luò)文件系統(tǒng)協(xié)議提供文件系統(tǒng)接口提供文件系統(tǒng)接口。磁盤>>磁盤性能的度量訪問時間（Accesstime）–發(fā)出讀寫請求到數(shù)據(jù)開始傳輸之間的時間.組成:尋道時間（Seektime）–磁盤臂重定位的到正確的磁道所花費(fèi)的時間.平均尋道時間大約是最長尋道時間的1/2典型的磁盤的尋道時間在4-10毫秒之間。旋轉(zhuǎn)等待時間（Rotationallatencytime)–扇區(qū)旋轉(zhuǎn)到讀寫頭下所耗費(fèi)的時間.平均旋轉(zhuǎn)等待時間是磁盤旋轉(zhuǎn)一周時間的1/2.平均旋轉(zhuǎn)等待時間在2-5毫秒左右（15000-5400r.p.m.)數(shù)據(jù)傳輸率–從磁盤獲得數(shù)據(jù)或者或者向磁盤存儲數(shù)據(jù)的速率目前磁盤系統(tǒng)支持25~100MB每秒的數(shù)據(jù)最大傳輸率，內(nèi)側(cè)磁道的數(shù)據(jù)傳輸率明顯低于最大傳輸率一個接口的傳輸率由連接到這個接口的所有磁盤共享SATA:150MB/sec,SATA-II3Gb(300MB/sec)Ultra320SCSI:320MB/s,SAS(3to6Gb/sec)FiberChannel(FC2Gbor4Gb):256to512MB/s磁盤>>磁盤性能的度量平均故障時間（Meantimetofailure(MTTF)–指磁盤無故障連續(xù)運(yùn)行的時間.大部分磁盤的工作時間3~5年生產(chǎn)商聲稱的平均故障時間是500k~1200k小時的含義？給定1000張新磁盤，如果MTTF是1200k小時的含義是平均在1200個小時內(nèi)，將會有一張磁盤發(fā)生故障。并非磁盤預(yù)計可以連續(xù)工作1200k小時（136年）隨著時間的增加，磁盤故障率會顯著增高。磁盤>>磁盤訪問的優(yōu)化塊（Block）是一個邏輯單元，包含固定數(shù)目的連續(xù)扇區(qū)數(shù)據(jù)在主存和磁盤之間以塊為單位進(jìn)行傳輸，塊的大小在512字節(jié)到幾KB之間順序訪問&隨機(jī)訪問塊大小的影響較小的塊:

較多的傳輸次數(shù)較大的塊:可能讀取的塊中只有數(shù)據(jù)有用；典型塊的大小在4到16KB之間為了提高訪問塊的速度，產(chǎn)生了許多技術(shù)：緩沖：從磁盤讀取的塊暫時存儲在內(nèi)存緩沖區(qū)中，以滿足將來的要求緩沖區(qū)通過OS和數(shù)據(jù)庫系統(tǒng)共同運(yùn)作預(yù)讀：當(dāng)一個磁盤塊被訪問時，相同磁道的連續(xù)塊也被讀入到內(nèi)存緩沖區(qū)，即便沒有針對這些塊的即將來臨的請求適合順序訪問，對隨機(jī)訪問不是很有效調(diào)度：如果需要把一個柱面上的幾塊從磁盤，可以按照塊經(jīng)過讀寫頭的順序發(fā)出訪問請求，如果所需的塊在不同的柱面上，則按照使磁盤臂移動最短距離的順序發(fā)出訪問塊的請求是非常有利的磁盤>>磁盤訪問的優(yōu)化(Cont.)磁盤臂調(diào)度算法（Disk-arm-schedulingalgorithms）如果所訪問的數(shù)據(jù)塊在不同的柱面上，則按照使磁盤臂移動最短距離的順序發(fā)出訪問塊的請求是最為有利的。電梯算法（elevatoralgorithm）磁盤>>磁盤訪問的優(yōu)化(Cont.)R1R5R2R4R3R6InnertrackOutertrack磁盤>>磁盤訪問的優(yōu)化(Cont.)文件組織（Fileorganization）–為了減少塊訪問時間，可以按照與預(yù)期的數(shù)據(jù)訪問方式最接近的方式來組織磁盤上的塊。E.g.

如果預(yù)計一個文件將順序訪問，那么理想情況下，應(yīng)該使文件的所有塊存儲在連續(xù)的相鄰柱面上。經(jīng)過一段時間后，文件可能會被碎片化某些系統(tǒng)提供碎片整理工具，來提高文件的訪問速度。非易失性寫緩沖區(qū)（Nonvolatilewritebuffers）

更新操作密集的數(shù)據(jù)庫應(yīng)用的性能，高度依賴于磁盤寫操作的速度。

使用非易失性隨機(jī)訪問存儲器（NonVolatileRandom-AccessMemory）Non-volatileRAM:

常用的實現(xiàn)方法是使用備用電池內(nèi)容在發(fā)生電源故障時不會丟失，當(dāng)電源恢復(fù)時，數(shù)據(jù)將會被寫回磁盤當(dāng)數(shù)據(jù)庫系統(tǒng)（或者OS）請求往磁盤上寫一個塊時，磁盤控制器將這個塊先寫到NV-RAM,然后立即通知操作系統(tǒng)寫操作成功完成當(dāng)磁盤沒有其它請求或者NV-RAM寫滿時，磁盤控制器將這些數(shù)據(jù)寫回到磁盤相應(yīng)的目標(biāo)位置。從系統(tǒng)崩潰中進(jìn)行恢復(fù)時，NV-RAM中所有緩沖的未完成的操作將寫回到磁盤。磁盤>>磁盤訪問的優(yōu)化(Cont.)日志磁盤（Logdisk）

–一種專門應(yīng)用于寫順序日志的磁盤和NV-RAM的使用非常相似對日志磁盤的訪問都是順序的，從根本上消除了尋道時間。不需要特定的硬件，比如(NV-RAM)支持日志磁盤的文件系統(tǒng)稱為日志文件系統(tǒng)（JournalingFileSystem)磁盤>>磁盤訪問的優(yōu)化(Cont.)RAID獨(dú)立磁盤冗余陣列RAID（RedundantArraysofIndependentDisks）磁盤的組織技術(shù)使大量磁盤組織在一起提供統(tǒng)一的磁盤視圖高容量：多張磁盤Web,數(shù)據(jù)庫，多媒體應(yīng)用高讀寫速度很多獨(dú)立的讀寫操作可以并行的執(zhí)行（parallel）

提供了高可靠性在多張磁盤上存儲冗余信息，一個磁盤的故障不會導(dǎo)致數(shù)據(jù)的丟失

“I”的含義早期指的是``inexpensive’’，因為可以用多張小且廉價構(gòu)成的系統(tǒng)替代大而昂貴的磁盤；現(xiàn)在使用RAID是因為更高的可靠性和更高的執(zhí)行效率（更高的帶寬）“I”代表的意思是independent通過冗余提高可靠性可靠性問題：N張磁盤組成的集合中某張磁盤發(fā)生故障的概率比特定的一張磁盤發(fā)生故障的概率要高例如：一張磁盤的MTTF的平均時間是100,000小時(大約11years),那么由100張磁盤組成的陣列發(fā)生故障的平均時間為1000小時(大約41天)。如果只存儲數(shù)據(jù)的一個拷貝，那么任何一張磁盤故障都將導(dǎo)致大量數(shù)據(jù)的丟失，因此引入冗余RAID（cont.）通過冗余提高可靠性冗余（Redundancy）–存儲正常情況下不需要的額外信息，這些信息可以在磁盤發(fā)生故障時重建丟失的信息.鏡像（Mirroring）復(fù)制沒一張磁盤，一張邏輯磁盤由兩張物理磁盤組成。每次寫操作都在兩張磁盤上進(jìn)行讀操作可以從任意一張磁盤上進(jìn)行如果一張磁盤發(fā)生故障，數(shù)據(jù)可以從另外一張磁盤上讀出。只有在第一張磁盤被修復(fù)之前，第二張磁盤也發(fā)生故障，數(shù)據(jù)才會丟失采用鏡像技術(shù)的磁盤平均故障時間依賴于單張磁盤的平均故障時間和平均修復(fù)時間例如，如果兩張磁盤發(fā)生故障是相互獨(dú)立的（并非完全合理），如果MTTF=100,000小時,平均修復(fù)時間是10小時，則鏡像磁盤系統(tǒng)的平均數(shù)據(jù)丟失時間為100,000×100,000/2*10校驗碼冗余糾錯碼（ECC）內(nèi)存中每個字節(jié)都有一個奇偶校驗位與之相連，它記錄著這個字節(jié)中為1的比特位的總數(shù)是偶數(shù)（=0）還是奇數(shù)（=1），如果字節(jié)中有一位被破壞了，則字節(jié)的ECC和存儲的ECC就不相匹配，111100000101011101011111000鏡像提供了高可靠性，但是十分昂貴；拆分提供了數(shù)據(jù)的高傳輸率，但不能提供可靠性。通過結(jié)合“奇偶校驗位”和磁盤拆分思想，從而以較低的代價提供數(shù)據(jù)冗余，人們提出了不同的替代方案，這些方案在不同的成本和性能之間權(quán)衡，分成若干RAID級別

RAID級別通過并行提高性能通過磁盤鏡像，處理讀請求的速度將翻倍，因為讀請求可以發(fā)送到任意一張磁盤磁盤系統(tǒng)中并行的兩個目的1. 負(fù)載平衡（Loadbalance）多個小的訪問操作，提高訪問的吞吐量2. 并行執(zhí)行大的訪問，減少大訪問操作的響應(yīng)時間.通過在多張磁盤上進(jìn)行數(shù)據(jù)拆分來提高傳輸率比特級拆分（Bit-levelstriping）–將每個字節(jié)按比特分開，存儲到多個磁盤上在一個8張磁盤組成的陣列上，每個字節(jié)的第i位寫到第i張磁盤上.如果把這8張磁盤看做一張磁盤，則這張磁盤的每個扇區(qū)的大小是通常磁盤的8倍.缺點(diǎn)：每張磁盤都參與每次訪問，所以單位時間處理的訪問的次數(shù)和一張磁盤時一樣的，需要較多的尋道時間，比特級的拆分目前已經(jīng)基本不用塊級拆分（Block-levelStriping）–將塊拆分到多張磁盤當(dāng)讀一個大文件時，塊級拆分可以從n張磁盤上并行地讀取n個塊RAID級別結(jié)合奇偶校驗位（paritybits）和磁盤拆分(diskstriping)思想，以較低的代價提供數(shù)據(jù)冗余不同的RAID級別有不同的具有不同的成本，效率及可信度RAIDLevel1:使用塊級拆分的磁盤鏡像（Mirroreddisks）能提供最好的讀寫性能流行在數(shù)據(jù)庫系統(tǒng)中的日志文件的存儲RAIDLevel0:塊級拆分無冗余適用于數(shù)據(jù)不太重要的高性能應(yīng)用RAID級別(Cont.)RAID2:內(nèi)存風(fēng)格的糾錯碼（Memory-StyleError-Correcting-Codes).RAID3:

位交叉的奇偶校驗組織結(jié)構(gòu)RAIDLevel4:

塊交叉的奇偶校驗組織結(jié)構(gòu)RAID5:

塊交叉的分布奇偶校驗位的組織結(jié)構(gòu)RAID6:P+Q冗余方案RAID級別(Cont.)選擇RAID級別應(yīng)該考慮的因素所需額外磁盤存儲所帶來的花費(fèi)；在I/O操作數(shù)量方面的性能需求；磁盤故障時的性能數(shù)據(jù)重建過程中的性能RAID0—用于數(shù)據(jù)安全性不是很重要的高性能應(yīng)用RAID1

—數(shù)據(jù)重建最為簡單，因為數(shù)據(jù)可以從另外一張磁盤拷貝得到，一般應(yīng)用于高性能數(shù)據(jù)庫。RAID2andRAID4基本不用，因為它們分別被RAID3和RAID5所包含。RAID3和RAID5塊級拆分對于大量數(shù)據(jù)的傳輸有與RAID3級同樣好的傳輸速率，同時對于少量數(shù)據(jù)的傳輸使用了更少的磁盤比特級拆分的RAID3不如塊級拆分的RAID5，RAID6—極少被使用是因為RAID1和RAID5已經(jīng)提供了足夠的安全保障來滿足大部分應(yīng)用，RAID6用于數(shù)據(jù)安全十分重要的應(yīng)用RAID級別的選擇RAID1提供了最好的寫操作性能廣泛應(yīng)用于數(shù)據(jù)庫日志文件的存儲這類應(yīng)用RAID1有較高的存儲代價磁盤容量增長迅速(每年增長50%)，因此對現(xiàn)存的具有中等存儲要求的數(shù)據(jù)庫而言，磁盤鏡像所需要的額外磁盤存儲開銷相對變小，而存取速度增長相對緩慢(10年3倍)I/O操作的需求飛速增長，如Web應(yīng)用服務(wù)器RAID5有較低的存儲負(fù)載，但是寫操作需要更高的時間開銷，對于經(jīng)常進(jìn)行讀操作而很少進(jìn)行寫操作的應(yīng)用，RAID5是首選。

對于其它應(yīng)用，較多采用RAID1.RAID級別的選擇----RAID1ORRAID5軟件RAID:不改變硬件層，在只修改軟件的基礎(chǔ)上實現(xiàn)。硬件RAID:具有專有硬件支持的RAID系統(tǒng)RAID----硬件問題Compactdisk-readonlymemory(CD-ROM)640-700MB的存儲容量尋道時間100毫秒(CD和DVD的激光頭組件更重，需要更長的尋道時間)較高的延遲(3000RPM)和較低的數(shù)據(jù)傳輸率(CD:3-6MB/s)

DigitalVideoDisk(DVD)

DVD-54.7GBDVD-98.5GBDVD-10和DVD-18是雙面存儲格式9.4GBand17GB藍(lán)光DVD:27GB(54GB雙面)和CD-ROM一樣的緣故，較長的尋道時間和較低的傳輸速率（8-20MB/s）第三級存儲----光盤特點(diǎn)保存時間長、可靠、存儲容量大速度慢（每秒幾到幾十MB）、只能進(jìn)行順序儲存、可靠讀寫的次數(shù)是有限的種類數(shù)字音頻磁帶（幾個GB）數(shù)字線性磁帶(10-40GB)Ultrium格式（100GB）Ampex螺旋掃描磁帶(330GB)自動磁帶機(jī)（Tapejukebox）存儲范圍可以達(dá)到PB級，主要應(yīng)用于備份，比如通過遙感衛(wèi)星搜集到的數(shù)據(jù)或者電視廣播的大型視頻庫第三級存儲----磁帶文件組織和存儲數(shù)據(jù)庫被影射到多個不同的文件，每個文件在邏輯上是記錄的序列.每個文件分為定長的存儲單元，塊（block，4-8k）,塊是存儲分配和數(shù)據(jù)傳輸?shù)幕締卧?，?chuàng)建數(shù)據(jù)庫實例時，允許指定塊的大小，更大的塊在一些數(shù)據(jù)庫的應(yīng)用中很有用.一個塊中包含很多條記錄，假定沒有比塊更大的記錄，并且每個記錄包含在單個的塊中.情形一:假定記錄都是定長的；任意一個文件中只存儲一個固定長度的記錄不同的文件用于存放不同的關(guān)系文件組織考慮學(xué)生數(shù)據(jù)庫中的instructor記錄組成的文件定長記錄

typeinstructor=recordIDvarchar(5);namevarchar(20);dept_namevarchar(20);salarynumaric(8,2);end假設(shè)每個字符占一個字節(jié)，則每個instructor記錄占用了53個字節(jié)，比較簡單的方法是用前53個字節(jié)存儲第一條記錄，接下來的53個字節(jié)存儲第二條記錄，以此類推.存在的問題：塊的大小并非恰好是53的倍數(shù)；在這個結(jié)構(gòu)中刪除一條記錄會帶來很多問題，變得比較困難問題一的解決方案在一個塊中只分配它能完整容納下的最大記錄數(shù)，每個塊中余下的部分就不用了，從而避免了讀寫一次記錄要進(jìn)行兩次塊的訪問定長記錄定長記錄刪除record3方案一：定長記錄刪除record3方案二：移動記錄以占據(jù)被刪除的記錄所釋放的空間的做法并不十分理想，因為這樣需要做額外的塊訪問操作由于插入操作通常比刪除操作更為頻繁，因此讓被刪記錄占據(jù)的空間空著，直到隨后插入的記錄占據(jù)這個空間的做法是可以接受的。但問題是僅僅在被刪記錄上做一個標(biāo)記，在插入時找到這個可用空間是十分困難的因此我們需要一個替代方案定長記錄-----刪除在文件的開始處，分配一定數(shù)量的字節(jié)作為頭文件，頭文件中存儲被刪除的第一條記錄的地址在第一個記錄中存儲第二個被刪記錄的地址，第二個記錄中存放第三個被刪記錄的地址，以此類推；可以直觀地把這些存儲的地址看作指針，被刪的記錄就形成了一個鏈表，這個鏈表稱為空閑鏈表（Freelist）如果沒有可用空間，就把記錄添加到文件的末尾存在的問題是------萬一頭文件損壞定長記錄--刪除----空閑列表變長記錄以以下幾種方式出現(xiàn)在數(shù)據(jù)庫系統(tǒng)中：多重記錄類型在同一個文件中存儲；允許一個或者多個字段是變長的記錄類型；實現(xiàn)變長記錄必須解決的兩個問題在塊中如何存儲變長記錄，使得塊中的記錄可以被抽取；如何描述一條記錄，使得單個屬性可以被輕松抽取。一條有變長屬性的記錄通常表示成為兩部分，初始部分是定長屬性，第二部分是變長屬性對于定長屬性，分配存儲它們的值所需的字節(jié)數(shù)；對于變長屬性，在記錄的初始部分表示成為一對值：偏移量和長度偏移量表示記錄該屬性的數(shù)據(jù)開始的位置長度表示變長屬性的字節(jié)長度文件組織----變長記錄該圖顯示一個變長記錄，前三個屬性ID,Name,Dept_name是變長字符串，第四個屬性是一個長度固定的數(shù)值假定偏移量和長度值各占2個字節(jié)，Salary占8個字節(jié)文件組織----變長記錄條目個數(shù)

空閑空間大小位置

在塊中存儲變長記錄的問題：分槽的頁結(jié)構(gòu)表示法

每個塊的存儲結(jié)構(gòu)如下：記錄入口數(shù)：表示塊中記錄條目的個數(shù)存儲塊中空閑空間的末尾地址一個數(shù)組：包含每個記錄的位置和大小

文件組織----變長記錄文件中記錄的組織堆文件組織(Heapfileorganization）一條記錄可以放在文件的任何位置，只要那個地方有空，記