數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn).ppt

1、數(shù)據(jù)庫(kù)系統(tǒng)基礎(chǔ),數(shù)據(jù)庫(kù)系統(tǒng)概述,數(shù)據(jù)庫(kù)的優(yōu)點(diǎn),1) 持久存儲(chǔ)。與文件系統(tǒng)類似， D B M S支持對(duì)非常大量的數(shù)據(jù)進(jìn)行存儲(chǔ)，這些數(shù)據(jù)獨(dú)立于使用數(shù)據(jù)的任何處理程序而存在。然而， D B M S在提供靈活性方面比文件系統(tǒng)做得更好，例如，它提供支持對(duì)非常大量的數(shù)據(jù)進(jìn)行高效存取的數(shù)據(jù)結(jié)構(gòu)。 2) 編程接口。D B M S使得用戶能夠通過強(qiáng)有力的查詢語(yǔ)言訪問和修改數(shù)據(jù)。D B M S在數(shù)據(jù)操縱的靈活性方面也比文件系統(tǒng)強(qiáng)。與文件讀寫相比， D B M S提供的對(duì)存儲(chǔ)的數(shù)據(jù)進(jìn)行操作的方式要復(fù)雜得多。 3) 事務(wù)管理。D B M S支持對(duì)數(shù)據(jù)的并發(fā)存取，即多個(gè)不同的進(jìn)程（稱作“事務(wù)”）同時(shí)對(duì)數(shù)據(jù)進(jìn)行存取。為避

2、免同時(shí)訪問所造成的不良后果， D B M S支持隔離，即看起來(lái)事務(wù)是一次一個(gè)地在執(zhí)行，以及原子性，即要求事務(wù)或者完全執(zhí)行；或者完全不執(zhí)行。D B M S還支持可恢復(fù)性，即能夠從多種類型的故障或錯(cuò)誤中恢復(fù)的能力。,術(shù)語(yǔ),數(shù)據(jù)：值得保留的任何信息，一般是電子形式的。 數(shù)據(jù)庫(kù)：為了訪問和修改而組織的、在長(zhǎng)時(shí)期內(nèi)保留的數(shù)據(jù)的集合。 查詢：從數(shù)據(jù)庫(kù)中抽取特定數(shù)據(jù)的操作。 關(guān)系：將數(shù)據(jù)組織到二維表中的組織方式，表中的行（元組）表示基本的實(shí)體或某種事實(shí)，表中的列（屬性）表示實(shí)體的特性。 模式：數(shù)據(jù)庫(kù)中數(shù)據(jù)結(jié)構(gòu)的描述，通常稱作“元數(shù)據(jù)”,自制數(shù)據(jù)庫(kù)系統(tǒng),Megatron 2000數(shù)據(jù)庫(kù)系統(tǒng)（虛構(gòu)） 特點(diǎn)：采用

3、關(guān)系方法，支持S Q L語(yǔ)言 數(shù)據(jù)存儲(chǔ)：采用文件系統(tǒng)來(lái)存儲(chǔ)它的關(guān)系 關(guān)系students(name, id,dept )存儲(chǔ)為一個(gè)單獨(dú)的文件,位于/ u s r / d b / s t u d e n t s.db 表結(jié)構(gòu)文件為s c h e m a 實(shí)現(xiàn)方式：數(shù)據(jù)的存儲(chǔ)，表結(jié)構(gòu)的存儲(chǔ),執(zhí)行查詢 查詢結(jié)果,執(zhí)行查詢的實(shí)現(xiàn)細(xì)節(jié) 考慮 數(shù)據(jù)庫(kù)管理系統(tǒng)將做下列事情： 1) 讀表結(jié)構(gòu)文件s c h e m a，以確定關(guān)系R中有哪些屬性，以及它們的類型。 2) 檢查對(duì)于關(guān)系R的語(yǔ)義合法性。 3) 顯示每一個(gè)屬性的名字作為列的頭。 4) 讀名字為R的文件，對(duì)于每一行： （a）檢查是否符合條件； （b）若符

4、合條件，則顯示該行為一個(gè)元組。,更復(fù)雜的查詢 這個(gè)查詢要求對(duì)關(guān)系S t u d e n t s和D e p t s進(jìn)行“連接”。即系統(tǒng)必須逐個(gè)考慮 從兩個(gè)關(guān)系中各取一個(gè)元組所組成的每一對(duì)元組，并檢驗(yàn)是否滿足下列條件： a）這兩個(gè)元組表示相同的系； b）學(xué)生的名字是S m i t h。 該算法可以非形式化地描述如下：,虛構(gòu)的數(shù)據(jù)庫(kù)系統(tǒng)存在的問題： 數(shù)據(jù)維護(hù)困難，缺乏對(duì)數(shù)據(jù)庫(kù)進(jìn)行修改時(shí)所需的靈活性。例如，如果我們?cè)谝粋€(gè)S t u d e n t s元組中將E E改為E C O N，整個(gè)文件都需要重寫，因?yàn)楹罄m(xù)的每一個(gè)字符都需要在文件中后移兩個(gè)位置。 查找代價(jià)太高。即使查詢要求給了我們一個(gè)值或一組值

5、，我們也總是需要讀入整個(gè)關(guān)系。在例子中，我們必須查看整個(gè)的S t u d e n t s關(guān)系，即使我們所要的只是學(xué)生S m i t h的元組。 查詢處理效率太低，實(shí)際上不必遍歷兩個(gè)關(guān)系的每一對(duì)元組。 沒有在主存儲(chǔ)器中緩存有用的數(shù)據(jù)，所有的數(shù)據(jù)都來(lái)自硬盤，I/O消耗時(shí)間多。 沒有并發(fā)控制。幾個(gè)用戶可以同時(shí)修改同一個(gè)文件，從而導(dǎo)致不可預(yù)期的結(jié)果。 沒有可靠性。發(fā)生故障時(shí)可能丟失數(shù)據(jù)，或者會(huì)有半途而廢的操作。 安全性差。假定作為基礎(chǔ)的操作系統(tǒng)以某種粗粒度的方式進(jìn)行存取控制。例如，對(duì)于不同的用戶，或者允許或者禁止他對(duì)于存放給定關(guān)系的文件進(jìn)行存取，但是不能夠做到對(duì)于一個(gè)用戶，允許他訪問一個(gè)關(guān)系中的某些屬

6、性，而不允許他訪問其他屬性,一個(gè)完整的D B M S的結(jié)構(gòu),單線框表示系統(tǒng)成分 雙線框表示內(nèi)存數(shù)據(jù)結(jié)構(gòu) 實(shí)線指明控制和數(shù)據(jù)流 虛線指明僅是數(shù)據(jù)流。 D B M S兩個(gè)不同的命令來(lái)源： 1) 普通用戶和應(yīng)用程序，他們要求對(duì)數(shù)據(jù)進(jìn)行訪問或修改。 2) 數(shù)據(jù)庫(kù)管理員：負(fù)責(zé)建立數(shù)據(jù)庫(kù)的結(jié)構(gòu)或模式的一個(gè)人或一組人。,查詢處理概述,D B A具有特殊的權(quán)限，可執(zhí)行模式修改命令（D D L命令，data-definition language，數(shù)據(jù)定義語(yǔ)言）由D D L處理程序進(jìn)行分析，然后傳給執(zhí)行引擎。由執(zhí)行引擎經(jīng)過索引/文件/記錄管理器，去改變?cè)獢?shù)據(jù)，即數(shù)據(jù)庫(kù)的模式信息。 用戶活動(dòng)可能沿著下面兩條路徑影

7、響數(shù)據(jù)庫(kù)： 1) 查詢響應(yīng)。 由查詢編譯器對(duì)查詢進(jìn)行分析和優(yōu)化。 得到的查詢計(jì)劃，或?yàn)榱嘶卮鸩樵兌扇〉膭?dòng)作序列被傳給執(zhí)行引擎。 執(zhí)行引擎向資源管理器發(fā)出一系列對(duì)于小的數(shù)據(jù)單元（通常是記錄或關(guān)系的元組）的請(qǐng)求。 資源管理器掌握著（存放關(guān)系的）數(shù)據(jù)文件，文件中的數(shù)據(jù)格式和記錄大小，以及支持對(duì)于數(shù)據(jù)文件中的元素進(jìn)行快速查找的索引文件。 查找數(shù)據(jù)的請(qǐng)求被翻譯成對(duì)頁(yè)面的請(qǐng)求，請(qǐng)求被傳送給緩沖區(qū)管理器。 緩沖區(qū)管理器的的任務(wù)是從持久地存儲(chǔ)數(shù)據(jù)的輔助存儲(chǔ)器（通常是磁盤）中將數(shù)據(jù)的適當(dāng)部分取到主存的緩沖區(qū)中。通常，緩沖區(qū)和磁盤間的傳輸單位是頁(yè)或“磁盤塊” 緩沖區(qū)管理器和存儲(chǔ)管理器進(jìn)行通信，以從磁盤獲取數(shù)據(jù)

8、。 存儲(chǔ)管理器通過操作系統(tǒng)命令或者直接發(fā)命令給磁盤控制器。 2) 事務(wù)處理。事務(wù)是組成一組的若干個(gè)查詢和其他動(dòng)作，是必須作為一個(gè)原子被孤立地執(zhí)行的單位。通常，每一個(gè)查詢或修改動(dòng)作自身就是一個(gè)事務(wù)。另外，事務(wù)的執(zhí)行必須是持久的，即任何已完成的事務(wù)的影響必須保留下來(lái)，即使事務(wù)剛一完成系統(tǒng)馬上就發(fā)生了某種故障。我們將事務(wù)處理器分成兩個(gè)主要部分： (a) 并發(fā)控制管理器，（或調(diào)度器），負(fù)責(zé)保證事務(wù)的原子性和孤立性。 (b) 日志和恢復(fù)管理器，負(fù)責(zé)事務(wù)的持久性。,主存緩沖區(qū)和緩沖區(qū)管理器,數(shù)據(jù)庫(kù)中的數(shù)據(jù)通常駐留在第二級(jí)存儲(chǔ)器（磁盤）中 數(shù)據(jù)必須在主存儲(chǔ)器（內(nèi)存）中，才能對(duì)數(shù)據(jù)進(jìn)行有用的操作。 緩沖區(qū)管理

9、器：負(fù)責(zé)將可利用的主存空間分割成緩沖區(qū)。 緩沖區(qū)與頁(yè)面同等大小，磁盤塊的內(nèi)容可以傳送到緩沖區(qū)中。 D B M S信息類型： 1) 數(shù)據(jù)：數(shù)據(jù)庫(kù)自身的內(nèi)容。 2) 元數(shù)據(jù)：描述數(shù)據(jù)庫(kù)的結(jié)構(gòu)和對(duì)數(shù)據(jù)庫(kù)的約束的數(shù)據(jù)庫(kù)模式。 3) 統(tǒng)計(jì)信息：D B M S收集和存儲(chǔ)的關(guān)于數(shù)據(jù)庫(kù)中各個(gè)關(guān)系或其他成分的大小、取值等的信息。 4) 索引：支持對(duì)數(shù)據(jù)進(jìn)行高效存取的數(shù)據(jù)結(jié)構(gòu)。,事務(wù)處理,事務(wù)：一個(gè)或多個(gè)數(shù)據(jù)庫(kù)操作組成一組 事務(wù)的A C I D特性 “A”表示“原子性”（A t o m i c i t y），即事務(wù)完全執(zhí)行或完全不執(zhí)行。 “I”表示“隔離”（I s o l a t i o n），即表面看起來(lái)每一個(gè)

10、事務(wù)都是在沒有其他事務(wù)同時(shí)執(zhí)行的情況下執(zhí)行的。 “D”表示“持久性”（D u r a b i l i t y），即一旦事務(wù)完成了，則事務(wù)對(duì)數(shù)據(jù)庫(kù)的影響就不會(huì)丟失。 “ C”表示“一致性”（C o n s i s t e n c y）。即，所有的數(shù)據(jù)庫(kù)都有一致性約束，或關(guān)于數(shù)據(jù)之間聯(lián)系的預(yù)期狀況（例如，某屬性是碼，學(xué)生不能同時(shí)修8門以上課程，等等）。,事務(wù)管理器：從應(yīng)用系統(tǒng)接受事務(wù)命令，安排事務(wù)運(yùn)行，反饋事務(wù)信息 事務(wù)處理器執(zhí)行下列任務(wù)： 1) 日志記錄：為了保證持久性，對(duì)于數(shù)據(jù)庫(kù)的每一個(gè)變化都在磁盤上登記日志。日志管理器能保證，不管在什么時(shí)候系統(tǒng)發(fā)生故障或“崩潰”，恢復(fù)管理器都能察看關(guān)于數(shù)據(jù)庫(kù)

11、變化的日志，并將數(shù)據(jù)庫(kù)恢復(fù)到某個(gè)一致的狀態(tài)。日志管理器將日志寫到緩沖區(qū)中，然后它與緩沖區(qū)管理器協(xié)調(diào)，保證在適當(dāng)?shù)臅r(shí)候?qū)⒕彌_區(qū)寫到磁盤中（磁盤中的數(shù)據(jù)不受系統(tǒng)崩潰的影響）。 2) 并發(fā)控制：事務(wù)的執(zhí)行從表面上看必須是孤立的。調(diào)度器（并發(fā)控制管理器）保證多個(gè)事務(wù)的每個(gè)動(dòng)作以一種適當(dāng)?shù)捻樞驁?zhí)行，從而使得最終的結(jié)果與這些事務(wù)一個(gè)執(zhí)行完了再執(zhí)行下一個(gè)的實(shí)際結(jié)果相同。調(diào)度器通過在數(shù)據(jù)庫(kù)的某些部分上維護(hù)若干個(gè)鎖來(lái)進(jìn)行它的工作。 3) 死鎖解決：當(dāng)事務(wù)之間通過調(diào)度器所授予的鎖進(jìn)行資源竟?fàn)帟r(shí)，可能會(huì)進(jìn)入死鎖情況：沒有任何一個(gè)事務(wù)能夠進(jìn)行下去，因?yàn)槊恳粋€(gè)事務(wù)都需要另一個(gè)事務(wù)所持有的某個(gè)資源。事務(wù)管理器取消（“中止

12、”）一個(gè)或多個(gè)事務(wù)，從而使其他的事務(wù)能進(jìn)行下去,查詢處理器 查詢處理器表示為兩個(gè)部分： 1) 查詢編譯器，它將查詢翻譯成一種內(nèi)部形式，稱作查詢計(jì)劃。查詢計(jì)劃是要在數(shù)據(jù)上執(zhí)行的一系列操作。通常，查詢計(jì)劃中的操作是“關(guān)系代數(shù)”的實(shí)現(xiàn)。查詢編譯器包括三個(gè)主要部分： (a) 查詢分析器，它由文本形式的查詢出發(fā)，建立一個(gè)樹結(jié)構(gòu)。（RPN） (b) 查詢預(yù)處理器，它對(duì)查詢進(jìn)行語(yǔ)義檢查（例如，檢查查詢中所提到的關(guān)系是否都確實(shí)存在），并進(jìn)行某些樹結(jié)構(gòu)轉(zhuǎn)換，將分析樹轉(zhuǎn)換為表示最初的查詢計(jì)劃的代數(shù)操作符樹。 (c) 查詢優(yōu)化器，它將最初的查詢計(jì)劃轉(zhuǎn)換為對(duì)于實(shí)際數(shù)據(jù)的最有效的操作序列。查詢編譯器利用元數(shù)據(jù)和關(guān)于數(shù)據(jù)

13、的統(tǒng)計(jì)數(shù)據(jù)來(lái)確定哪一個(gè)操作序列可能是最快的。 2) 執(zhí)行引擎，它負(fù)責(zé)執(zhí)行選中的查詢計(jì)劃中的每一步。 和緩沖區(qū)交互：為了對(duì)數(shù)據(jù)進(jìn)行操作，必須從數(shù)據(jù)庫(kù)取得數(shù)據(jù)并放到緩沖區(qū)中。 和調(diào)度器進(jìn)行交互：以避免訪問被加了鎖的數(shù)據(jù) 和日志管理器進(jìn)行交互：確保對(duì)于數(shù)據(jù)庫(kù)的所有修改都正確地記了日志。,數(shù)據(jù)庫(kù)模型,關(guān)系是元組的集合 元組是值的列表。 列標(biāo)題稱作屬性，表示元組中每一個(gè)分量的含義。 關(guān)系名和屬性名以及屬性類型稱作該關(guān)系的模式。（如右下圖） 數(shù)據(jù)庫(kù)模式是關(guān)系模式的集合 視圖：不實(shí)際存儲(chǔ)，但在需要時(shí)從實(shí)際存儲(chǔ)的關(guān)系構(gòu)造出來(lái)的關(guān)系的描述。,存儲(chǔ)器層次,高速緩沖存儲(chǔ)器（c a c h e，簡(jiǎn)稱高速緩存）。 高速

14、緩存是一種集成電路（“芯片”），或者是處理器芯片的一部分，它能存放數(shù)據(jù)或機(jī)器指令。 高速緩存中的數(shù)據(jù)（包括指令）是主存儲(chǔ)器中特定位置的數(shù)據(jù)的副本， 高速緩存通常分為兩級(jí)：?jiǎn)伟甯咚倬彺嫖挥谧鳛槲⑻幚砥鞅旧淼耐恍酒希?jí)高速緩存位于另一個(gè)芯片。 當(dāng)機(jī)器執(zhí)行指令時(shí)，它在高速緩存中尋找指令以及那些指令要使用的數(shù)據(jù)。 如果在高速緩存中找不到這些指令和數(shù)據(jù)，它就要到主存中去尋找，并將它們拷貝到高速緩存中去。由于高速緩存中只能保留有限數(shù)量的數(shù)據(jù)，通常必須將高速緩存中某些內(nèi)容移出去，以便接納新的數(shù)據(jù)。 如果被移出高速緩存的內(nèi)容自從它被復(fù)制到高速緩存以來(lái)一直沒有改變，就不需要再做任何事情。 如果要從高速緩存

15、移出的數(shù)據(jù)已經(jīng)被修改，那么新的值必須拷貝到它在主存中原先的位置。 當(dāng)高速緩存中的數(shù)據(jù)被修改時(shí)，只有單個(gè)處理器的簡(jiǎn)單計(jì)算機(jī)不需要立即更新主存中相應(yīng)位置的數(shù)據(jù)。 在多處理器系統(tǒng)中，允許多個(gè)處理器訪問相同的內(nèi)存，并且各處理器擁有它們各自的高速緩存。在這種情況下，需要直寫（write through）即立即修改主存中相應(yīng)的位置。 高速緩存與處理器之間數(shù)據(jù)的讀寫可以以處理器指令的速度執(zhí)行，通常為1 0納秒在高速緩存與主存之間移動(dòng)一條指令或一個(gè)數(shù)據(jù)項(xiàng)需1 0 0納秒,主存儲(chǔ)器 主存是隨機(jī)訪問的，在同一的時(shí)間內(nèi)可獲得任何一個(gè)字節(jié)。從主存訪問數(shù)據(jù)的通常是在1 01 0 0納秒。 虛擬存儲(chǔ)器 虛擬存儲(chǔ)器空間比通

16、常的內(nèi)存要大得多，虛擬存儲(chǔ)器的大部分內(nèi)容實(shí)際上是保存在硬盤上。 32位機(jī)器的虛擬存儲(chǔ)器為4 GB（232字節(jié)） 硬盤被邏輯地分成多個(gè)塊（b l o c k）。塊的大小是在4 K B 5 6 K B。 虛擬存儲(chǔ)器塊為單位在硬盤和主存之間移動(dòng)，在主存中這些塊常常被稱作頁(yè)( p a g e )。 機(jī)器硬件和操作系統(tǒng)允許虛存頁(yè)進(jìn)入主存的任何部分，并且使得塊中的每一個(gè)字節(jié)都被它的虛擬地址正確地指向,第二級(jí)存儲(chǔ)器(也稱輔助存儲(chǔ)器，或簡(jiǎn)稱輔存)，是存儲(chǔ)器的一種形式，它的速度要比內(nèi)存慢得多，而存儲(chǔ)容量則要比內(nèi)存大得多，并且基本上是隨機(jī)訪問。 在操作系統(tǒng)或數(shù)據(jù)庫(kù)系統(tǒng)的控制下，文件以塊的方式在磁盤與主存之間移動(dòng)。

17、將一個(gè)塊從磁盤移動(dòng)到主存是一次磁盤讀，將一個(gè)塊從主存移動(dòng)到磁盤是一次磁盤寫。我們稱之為一次磁盤I / O（磁盤輸入/輸出） 主存的某些部分被用于作為文件緩沖區(qū)，即以塊大小為單位保留這些文件的某部分 數(shù)據(jù)庫(kù)管理系統(tǒng)由自己管理磁盤塊，而不依賴于操作系統(tǒng)的文件管理器在主存和輔存之間移動(dòng)塊 應(yīng)當(dāng)盡可能地讓我們需要訪問的數(shù)據(jù)所在的磁盤塊已經(jīng)在主存緩沖區(qū)內(nèi),磁盤 使用第二級(jí)存儲(chǔ)器是數(shù)據(jù)庫(kù)管理系統(tǒng)的重要特性之一，而第二級(jí)存儲(chǔ)器幾乎都是基于磁盤的。 為了說(shuō)明D B M S實(shí)現(xiàn)中采用的許多思想的理由, 我們必須詳細(xì)地研究磁盤操作。,存儲(chǔ)二進(jìn)制位的存儲(chǔ)單元被組織成磁道（t r a c k），磁道是單個(gè)盤片上的同心

18、圓。 磁道被組織成扇區(qū)（s e c t o r）扇區(qū)是不可分割的讀寫單位，若一部分磁化層被損壞，那么整個(gè)扇區(qū)也不能再使用 扇區(qū)是被間隙( g a p )分割的圓的片斷，間隙在兩個(gè)方向上均不被磁化。間隙大約占整個(gè)磁道的1 0 %，用于幫助標(biāo)識(shí)扇區(qū)的起點(diǎn)。 “塊” 是在磁盤與主存之間所傳輸數(shù)據(jù)的邏輯單元，由一個(gè)或多個(gè)扇區(qū)所組成,磁盤控制器 一個(gè)或多個(gè)磁盤驅(qū)動(dòng)器被一個(gè)磁盤控制器所控制，磁盤控制器是一個(gè)小處理器，能夠完成以下功能： 1) 控制移動(dòng)磁頭組合的機(jī)械傳動(dòng)裝置，將磁頭定位到一個(gè)特定的半徑位置。在同一時(shí)刻位于磁頭下的各個(gè)磁道被認(rèn)為構(gòu)成一個(gè)柱面（c y l i n d e r）。 2) 選擇盤面，

19、并從磁頭下的磁道上選擇一個(gè)扇區(qū)。 3) 將從扇區(qū)讀取的二進(jìn)制位傳送到計(jì)算機(jī)的主存儲(chǔ)器，或者將從主存儲(chǔ)器寫入的二進(jìn)制位傳送到扇區(qū),磁盤訪問特性,從發(fā)出讀塊命令的時(shí)刻起，到塊的內(nèi)容出現(xiàn)在主存中，其間所花費(fèi)的時(shí)間稱為磁盤的等待時(shí)間( l a t e n c y )。這個(gè)時(shí)間可以劃分為下列幾部分： 1) 由處理器和磁盤控制器處理請(qǐng)求所花費(fèi)的時(shí)間，通常是零點(diǎn)幾毫秒，可忽略不計(jì) 2) 將磁頭組合定位到合適的柱面所花費(fèi)的時(shí)間。這個(gè)時(shí)間稱為尋道時(shí)間（seek time）。大約是1 04 0毫秒范圍內(nèi)。平均尋道時(shí)間經(jīng)常被用來(lái)作為表示磁盤速度特征的一種度量。 3) 磁盤轉(zhuǎn)動(dòng)到組成該塊的第一個(gè)扇區(qū)到達(dá)磁頭時(shí)所需要的

20、時(shí)間，稱為轉(zhuǎn)動(dòng)延時(shí)（rotational latency）。常用的硬盤大約每1 0毫秒完整地轉(zhuǎn)動(dòng)一周。平均轉(zhuǎn)動(dòng)等待在5毫秒左右。 4) 傳輸時(shí)間（transfer time）是塊的扇區(qū)以及各扇區(qū)之間的間隙旋轉(zhuǎn)通過磁頭所需要的時(shí)間。每秒鐘讀取大約1 0兆字節(jié)。一個(gè)4 0 6 9字節(jié)塊的傳輸時(shí)間小于半毫秒。,第二級(jí)存儲(chǔ)器的有效使用,計(jì)算的I/O模型的規(guī)則：如果一個(gè)塊需要在磁盤與主存之間移動(dòng)，那么執(zhí)行讀或?qū)懰ㄙM(fèi)的時(shí)間或許要比用于操縱主存中的數(shù)據(jù)所花費(fèi)的時(shí)間長(zhǎng)得多。這樣，塊訪問（讀和寫）次數(shù)就是算法所需要的時(shí)間的近似值，而且應(yīng)該被最小化。 為什么要?jiǎng)?chuàng)建索引： 假設(shè)數(shù)據(jù)庫(kù)有關(guān)系R，有一個(gè)對(duì)元組的查詢請(qǐng)

21、求，該元組有一個(gè)確定的碼值k。 在R上創(chuàng)建一個(gè)索引，用于標(biāo)識(shí)帶有碼值k的元組出現(xiàn)的磁盤塊。 索引可以一次性地裝入內(nèi)存，在內(nèi)存中完成元組的排序搜索等操作。 在主存中執(zhí)行搜索的附加時(shí)間將小于塊訪問時(shí)間的1 %。,第二級(jí)存儲(chǔ)器中的數(shù)據(jù)排序,由于大部分?jǐn)?shù)據(jù)位于磁盤中，基于內(nèi)存的排序方法不可用（比如快排） 基于磁盤的排序方法時(shí)間消耗決定于讀寫磁盤的次數(shù) 歸并排序（M e rg e - S o r t）：法將幾個(gè)小的已排好 序的表歸并為一個(gè)較大的排好序的表，來(lái)實(shí)現(xiàn)排序。為了歸并兩個(gè)已排序的表，反復(fù)比較每個(gè)表所剩余的最小的碼，把其中碼值較小的記錄移出，如此反復(fù)，直到一個(gè)表被取盡。,兩階段多路歸并排序（Tow

22、-phase, Multiway Merg e - S o r t） 階段1：構(gòu)建若干有序子表，這些子表覆蓋所有記錄。 1) 將需要排序的塊調(diào)入內(nèi)存 2) 對(duì)位于內(nèi)存中的記錄排序 3) 將排序后的記錄從主存儲(chǔ)器寫入第二級(jí)存儲(chǔ)器的新塊中，并形成一個(gè)有序子表。 在第一階段結(jié)束時(shí)，原始關(guān)系的所有記錄已經(jīng)被讀入主存一次 階段2：歸并所有的有序子表以形成一個(gè)單個(gè)排序表。 注意，一個(gè)子表包含若干塊,1 ) 在所有的表的剩余元素的第一個(gè)元素中間找出最小碼。 2) 將最小元素移動(dòng)到輸出塊的第一個(gè)可用位置。 3) 如果輸出塊已經(jīng)填滿，則將其寫入磁盤，并且重新初始化主存中的該緩沖區(qū)，以便存放下一個(gè)輸出塊。 4)

23、如果剛剛從中取出最小元素的塊現(xiàn)在已經(jīng)取盡了記錄，則從相同的有序子表中讀出下一個(gè)塊到相同的緩沖區(qū)，即剛剛?cè)”M記錄的那個(gè)塊用過的緩沖區(qū)。,提高磁盤訪問速度,按柱面組織數(shù)據(jù) 由于尋道時(shí)間占平均塊訪問時(shí)間的一半，在一些應(yīng)用中，將一些可能被一起訪問的數(shù)據(jù)存儲(chǔ)在單個(gè)柱面上。 如果沒有足夠的空間，那么可使用鄰近的柱面。 如果我們選擇在一個(gè)單個(gè)磁道上或者在一個(gè)柱面上連續(xù)地讀所有塊，則可只考慮第一次尋道時(shí)間和第一次旋轉(zhuǎn)等待時(shí)間，而忽略其他時(shí)間。 此時(shí)，從磁盤上讀寫數(shù)據(jù)的速度接近于理論上的傳輸速率。,使用多個(gè)磁盤 如果我們用多個(gè)磁盤（每個(gè)磁盤都具獨(dú)立磁頭組）來(lái)代替一個(gè)磁盤（其多個(gè)磁頭鎖定在一起），常常能夠提高系統(tǒng)

24、的速度。 可將一個(gè)有序子表分別存儲(chǔ)在不同磁盤上,磁盤鏡像 有兩個(gè)或更多的磁盤保留同樣的數(shù)據(jù)拷貝，這些磁盤被稱作相互鏡像( m i r r o r ) 作用： 1）增強(qiáng)可靠性 2）提高訪問數(shù)據(jù)的速度。 通常，如果做一個(gè)磁盤的n個(gè)拷貝，就能并行地讀任何n個(gè)塊。 如果同時(shí)要讀的塊比n少，那么通過正確地選擇從哪個(gè)磁盤讀，就經(jīng)常能獲得速度提升。例如，可以選擇其磁頭最靠近我們要求讀的那個(gè)柱面的可用磁盤。,磁盤調(diào)度和電梯算法 調(diào)度大量塊請(qǐng)求的一個(gè)簡(jiǎn)單而有效的方法被稱為電梯算法（elevator algorithm）。 我們把磁頭看作是在作橫跨磁盤的掃描，從柱面最內(nèi)圈到最外圈，然后再返回來(lái)，正如電梯作垂直掃描

25、，從大樓的底層到頂層，然后再返回來(lái)。 當(dāng)磁頭通過柱面時(shí)，如果有一個(gè)或多個(gè)對(duì)該柱面上的塊的請(qǐng)求，磁頭就停下來(lái)。 根據(jù)請(qǐng)求，所有這些塊被讀或?qū)?。然后磁頭沿著其正在行進(jìn)的同一方向繼續(xù)移動(dòng)，直至遇到下一個(gè)包含要訪問塊的柱面。當(dāng)磁頭到達(dá)其行進(jìn)方向上的某一個(gè)位置，在該位置的前方不再有訪問請(qǐng)求時(shí)，磁頭就朝相反方向移動(dòng)。,電梯算法的塊訪問完成時(shí)間 先到達(dá)先服務(wù)算法的塊訪問完成時(shí)間,預(yù)取和大規(guī)模緩沖 預(yù)取( p r e f e t c h i n g )，也稱雙緩沖(double buff e r i n g )。如果能夠預(yù)測(cè)從磁盤請(qǐng)求塊的順序，就能在需要這些塊之前將它們裝入主存，能較好地調(diào)度磁盤，通過采用諸如

26、電梯算法等，減少訪問塊所需要的平均時(shí)間。 預(yù)寫，按照預(yù)取的思想，可以延遲緩沖塊的寫 如果采用大的輸出緩沖區(qū)（磁道大小或柱面大小），基本上能消除尋道時(shí)間和旋轉(zhuǎn)等待，并以磁盤的最大傳輸速率寫盤。,各種策略及其優(yōu)缺點(diǎn) 磁盤訪問請(qǐng)求的兩 種極端情況： a)塊可以按能事先預(yù)測(cè)的次序讀和寫。并且只有一個(gè)使用磁盤的進(jìn)程，例如，兩階段多路歸并排序法。 b)短進(jìn)程的一個(gè)集合，它們并行地執(zhí)行，共享相同的磁盤，并且不能事先預(yù)測(cè)。諸如航班預(yù)訂或銀行帳目 優(yōu)點(diǎn)和缺點(diǎn)： 1. 基于柱面的組織 優(yōu)點(diǎn)：對(duì)于類型（ a）的應(yīng)用極佳。在類型（ a）中，訪問可事先預(yù)測(cè)，而且僅有一個(gè)進(jìn)程正在使用磁盤。 缺點(diǎn)：對(duì)類型（b）的應(yīng)用無(wú)法提

27、高性能，因?yàn)椋╞）的訪問是不可預(yù)測(cè)的。 2. 多磁盤 優(yōu)點(diǎn)：對(duì)于兩類應(yīng)用，都能增加處理讀/寫請(qǐng)求的速率。 問題：對(duì)同一磁盤的多個(gè)讀或?qū)懻?qǐng)求不能同時(shí)滿足，所以加速系數(shù)可能小于磁盤數(shù)增加的系數(shù)。 缺點(diǎn)：若干小磁盤的開銷超過具有相同總?cè)萘康膯蝹€(gè)磁盤的開銷。,3. 鏡像 優(yōu)點(diǎn)：對(duì)于兩種類型的應(yīng)用，均增加處理讀/寫請(qǐng)求的速率，不存在多磁盤中提到的訪問沖突的問題。改善所有應(yīng)用的容錯(cuò)性。 缺點(diǎn)：付出兩個(gè)或多個(gè)磁盤的代價(jià)，只能得到一個(gè)磁盤的存儲(chǔ)容量。 4. 電梯算法 優(yōu)點(diǎn)：當(dāng)對(duì)塊的訪問為不可預(yù)測(cè)時(shí)，減少讀/寫塊的平均時(shí)間。 問題：在有許多磁盤訪問請(qǐng)求等候的情況下，這種算法是最有效的，但因此這些請(qǐng)求處理的平均延

28、時(shí)就很長(zhǎng)。 5. 預(yù)取/雙緩沖 優(yōu)點(diǎn)：當(dāng)需要訪問的塊為已知但請(qǐng)求的時(shí)序依賴于數(shù)據(jù)時(shí)，可加速訪問，如同多路歸并排序的階段2那樣。 缺點(diǎn)：要求額外的主存緩沖區(qū)。當(dāng)訪問為隨機(jī)時(shí)不能提高訪問性能。,磁盤故障,磁盤故障的類型 1) 間斷性故障，讀或?qū)懸粋€(gè)扇區(qū)的某次嘗試沒有成功，但是經(jīng)過反復(fù)嘗試，又能成功地讀或?qū)??？捎闷媾夹ｒ?yàn)作為檢測(cè)間斷性故障的方法。 2)介質(zhì)損壞，在這種故障中，一個(gè)或多個(gè)二進(jìn)制位永久地?fù)p壞，不管嘗試多少次都無(wú)法正確地讀一個(gè)扇區(qū)。 3) 寫故障，當(dāng)企圖寫一個(gè)扇區(qū)時(shí)，既不能正確地寫，也不能檢索先前寫入的扇區(qū)。一種可能的原因是寫扇區(qū)的過程中發(fā)生了供電中斷。 4)磁盤崩潰，是磁盤故障的最嚴(yán)重形

29、式，整個(gè)磁盤突然變?yōu)橛谰貌豢勺x。用“ R A I D”技術(shù)解決磁盤崩潰問題。,校驗(yàn)和：每個(gè)扇區(qū)有若干個(gè)附加位，稱為校驗(yàn)和（c h e c k s u m），附加位的設(shè)置取決于存儲(chǔ)在那個(gè)扇區(qū)的數(shù)據(jù)位的值。在讀出時(shí)，如果發(fā)現(xiàn)校驗(yàn)和對(duì)數(shù)據(jù)位不適合，就返回狀態(tài)“壞”，否則就返回狀態(tài)“好”。 基于扇區(qū)內(nèi)所有位的奇偶性（p a r i t y）的校驗(yàn)和。如果在二進(jìn)制的集合中有奇數(shù)個(gè)1，設(shè)置奇偶位是1；如果在二進(jìn)制位的集合 中有偶數(shù)個(gè)1，設(shè)置奇偶位是0。 二進(jìn)制位的集合中1的個(gè)數(shù)與它們的奇偶位中1的個(gè)數(shù)總和總是偶數(shù)。 當(dāng)寫一個(gè)扇區(qū)時(shí)，磁盤控制器能計(jì)算出奇偶位，并將它附加到寫在扇區(qū)中的二進(jìn)制位的序列中，每個(gè)扇

30、區(qū)將有偶數(shù)奇偶性。 例如：扇區(qū)中二進(jìn)制位序列是0 11 0 1 0 0 0，奇偶位是1。這個(gè)序列后面加上它的奇偶位，便有0 11 0 1 0 0 0 1。 如果所給的數(shù)據(jù)位序列是111 0 111 0，有偶數(shù)個(gè)1，而奇偶位為0。序列后面加上它的奇偶位便是111 0 111 0 0。,在讀或?qū)憯?shù)據(jù)位及其奇偶位的過程中，磁盤控制器計(jì)算1的個(gè)數(shù)，如果一個(gè)扇區(qū)有奇數(shù)奇偶性就判定存在一個(gè)錯(cuò)誤。 當(dāng)然，扇區(qū)可能有一個(gè)以上的位出錯(cuò)，二進(jìn)制位1的個(gè)數(shù)仍為偶數(shù)控制器將檢測(cè)不到錯(cuò)誤。 需要保持若干個(gè)奇偶校驗(yàn)位，以增加檢測(cè)出大量錯(cuò)誤的機(jī)會(huì)。 例如，可保持8位奇偶校驗(yàn)位，其中一位用于檢測(cè)每個(gè)字節(jié)的第一位，另一位用于檢

31、測(cè)每個(gè)字節(jié)的第二位，等等，直到奇偶位的第八位和每個(gè)字節(jié)的最后一位。 任何一個(gè)奇偶位將檢測(cè)出錯(cuò)誤的可能性是5 0 %，8位都檢測(cè)不出錯(cuò)誤的機(jī)會(huì)是1 / 2 5 6。 一般地說(shuō)，如果我們用n個(gè)獨(dú)立位作為校驗(yàn)和，漏掉一個(gè)錯(cuò)誤的機(jī)會(huì)僅為1 / 2n。 例如，我們用4字節(jié)作為校驗(yàn)和，那么大約在4 0億次中僅有一次錯(cuò)誤不能被檢測(cè)出來(lái)。,穩(wěn)定存儲(chǔ) 穩(wěn)定存儲(chǔ)( s t a b l es t o r a g e )策略?？偟乃枷胧牵葏^(qū)是成對(duì)的，每一對(duì)代表一個(gè)扇區(qū)內(nèi)容X。我們把代表X的扇區(qū)對(duì)分別稱作“左”拷貝XL和“右”拷貝XR 。假定這兩個(gè)拷貝用足夠多的奇偶校驗(yàn)位來(lái)，以排除誤判可能性。這樣可以假定，如果讀函數(shù)

32、對(duì)XL或XR中的任何一個(gè)返回（ w，好），那么w是X的真值。 穩(wěn)定存儲(chǔ)的寫策略是： 1) 寫X的值到XL。檢查是否返回值的狀態(tài)為“好”（奇偶校驗(yàn)位是正確的）。如果不是“好”，則反復(fù)寫。如果在若干次寫嘗試之后，仍沒有成功地將X寫入XL，可以認(rèn)為在該扇區(qū)中有一個(gè)介質(zhì)故障，必須采用諸如以備用扇區(qū)代替XL這樣的補(bǔ)救。 2) 對(duì)XR重復(fù)1）。 穩(wěn)定存儲(chǔ)的讀策略是： 1) 讀XL以獲得X的值。如果返回狀態(tài)“壞”，反復(fù)讀若干次。如果最終返回帶有狀態(tài)“好”的一個(gè)值，則取這個(gè)值作為X。 2) 如果不能讀XL，用XR重復(fù)1）。,穩(wěn)定存儲(chǔ)的策略能夠校正若干不同種類的錯(cuò)誤：。 1 ) 介質(zhì)故障。在將X存入扇區(qū)XL和X

33、R后，如果兩者之一出現(xiàn)一個(gè)介質(zhì)故障并且變?yōu)橛谰貌豢勺x，總是能從另一個(gè)扇區(qū)讀取X。如果XL和XR兩者都有故障，那么我們就不能讀取X，但是兩者都發(fā)生故障的可能性是非常小的。 2 ) 寫故障。假設(shè)當(dāng)我們寫X的時(shí)候，有一個(gè)系統(tǒng)故障，例如電源斷電。有可能半個(gè)扇區(qū)可能被寫入X的部分新值，與此同時(shí)另一半扇區(qū)保留著原來(lái)的值。當(dāng)系統(tǒng)變?yōu)榭捎?，可能的情況有以下幾種： (a) 故障在寫XL時(shí)發(fā)生。那么XL的狀態(tài)是“壞”，由于沒有寫XR，它的狀態(tài)將是“好” ，這樣就能夠獲得X的舊值?？梢詫R拷貝到XL，并修復(fù)XL的故障。 (b) 故障在我們寫XL之后發(fā)生。那么，我們預(yù)計(jì)XL將有狀態(tài)“好”，并且我們可以從XL讀取X的

34、新值。注意，XR可能有狀態(tài)“壞”，如果那樣的話，應(yīng)該將XL拷貝到XR。,磁盤冗余方案,R A I D（Redundant Array of Independent Disks，冗余獨(dú)立磁盤陣列）用于減少因磁盤崩潰帶來(lái)的丟失數(shù)據(jù)的風(fēng)險(xiǎn)。 不同磁盤冗余方案都有一個(gè)或多個(gè)保存數(shù)據(jù)的磁盤（數(shù)據(jù)盤），再加上一個(gè)或多個(gè)保存信息的磁盤，這些信息完全由數(shù)據(jù)盤的內(nèi)容所決定（稱為冗余盤）。 當(dāng)一個(gè)數(shù)據(jù)盤或冗余盤發(fā)生磁盤崩潰時(shí)，其他的磁盤可用于恢復(fù)故障磁盤，從而沒有任何永久性信息丟失。,RAID 1鏡像磁盤： 該方案中，兩個(gè)磁盤稱一個(gè)磁盤為數(shù)據(jù)盤，另一個(gè)是冗余盤。冗余盤與數(shù)據(jù)盤一樣多。鏡像冗余方案中數(shù)據(jù)丟失的唯一方

35、式是，在第一個(gè)磁盤損壞正在被修復(fù)的同時(shí)，第二個(gè)磁盤也被損壞。 RAID4奇偶?jí)K： RAID 4使用多個(gè)數(shù)據(jù)盤和一個(gè)冗余盤。假設(shè)磁盤是相同的，所以我們能給每一個(gè)磁盤編號(hào)，從1到某個(gè)數(shù)n。當(dāng)然，所有磁盤上的所有塊都有著相同的二進(jìn)制位數(shù)；在冗余盤中，第i塊由所有數(shù)據(jù)盤的第i塊奇偶校驗(yàn)位組成。也就是說(shuō)，所有第i塊的第j位，包括數(shù)據(jù)盤和冗余盤，在它們中間必須有偶數(shù)個(gè)1。 盤1：1 1 1 1 0 0 0 0 盤2：1 0 1 0 1 0 1 0 盤3：0 0 1 1 1 0 0 0 冗余盤 盤4：0 1 1 0 0 0 1 0,RAID4并行讀 假設(shè)我們正在讀第一個(gè)數(shù)據(jù)盤的一個(gè)塊a，另一個(gè)請(qǐng)求進(jìn)入要讀同

36、一磁盤的一個(gè)不同的塊b。通常，必須等待第一個(gè)請(qǐng)求完成，然而，如果其余的磁盤處于空閑狀態(tài)，可通過取模2和（module-2 sum）計(jì)算出第一磁盤的塊b。 盤2：1 0 1 0 1 0 1 0 盤3：0 0 1 1 1 0 0 0 冗余盤 盤4：0 1 1 0 0 0 1 0 計(jì)算得到盤1：？,RAID4寫，需要修改數(shù)據(jù)盤和冗余盤 盤1：1 1 1 1 0 0 0 0 盤2：1 0 1 0 1 0 1 0改為 1 1 0 0 1 1 0 0 盤3：0 0 1 1 1 0 0 0 冗余盤 盤4：0 1 1 0 0 0 1 0 計(jì)算冗余盤的值 1 0 1 0 1 0 1 0 （數(shù)據(jù)盤舊值） 1 1

37、0 0 1 1 0 0 （數(shù)據(jù)盤新值） 0 1 1 0 0 0 1 0 （冗余盤舊值） 0 0 0 0 0 1 0 0 （冗余盤新值） 該方法只需要讀寫發(fā)生改變的盤和冗余盤，無(wú)需讀些其它盤，當(dāng)數(shù)據(jù)盤較多時(shí)，此種方法具有優(yōu)勢(shì)。,故障恢復(fù) 如果故障盤是冗余盤，就換進(jìn)一個(gè)新磁盤，并重新計(jì)算冗余塊。 如果故障盤是數(shù)據(jù)盤之一，那么需要換進(jìn)一個(gè)好盤，并且根據(jù)其他盤重新計(jì)算它的數(shù)據(jù)。 重新計(jì)算任何丟失數(shù)據(jù)的規(guī)則實(shí)際上是簡(jiǎn)單的，因?yàn)樗写疟P中相應(yīng)位的1的個(gè)數(shù)是偶數(shù)，它遵循如下規(guī)則： 任何位置的位是所有其他磁盤的相應(yīng)位置所有位的模2 和。 例如，盤2發(fā)生故障 盤1：1 1 1 1 0 0 0 0 盤2：？ 盤3

38、：0 0 1 1 1 0 0 0 冗余盤 盤4：0 1 1 0 0 0 1 0 計(jì)算得到1 0 1 0 1 0 1 0 優(yōu)點(diǎn)：RAID 4級(jí)策略能有效地保護(hù)數(shù)據(jù)，除非存在兩個(gè)磁盤幾乎同時(shí)崩潰 缺點(diǎn)：冗余盤的讀寫負(fù)荷過重。更新硬盤都需要讀和寫冗余盤的塊。如果有n個(gè)數(shù)據(jù)盤，那么對(duì)冗余盤的磁盤寫次數(shù)，將是任何一個(gè)數(shù)據(jù)盤平均磁盤寫次數(shù)的n倍,RAID4一種改進(jìn)：RAID 5 RAID 5把每個(gè)磁盤作為某些塊的冗余盤來(lái)處理，平衡每塊盤的讀寫負(fù)荷。 如果有n+ 1個(gè)編號(hào)為0n的磁盤，如果j是當(dāng)i被n+ 1除時(shí)的余數(shù)，則可以把盤j的第i個(gè)柱面看作冗余。 如果n = 3，有4個(gè)磁盤， 0號(hào)盤，作為編號(hào)為4、8

39、、12等柱面的冗余。 1號(hào)盤，作為編號(hào)為1、5、9等柱面的冗余。 2號(hào)盤，作為編號(hào)為2、6、10等柱面的冗余。 3號(hào)盤，作為編號(hào)為3、7、11等柱面的冗余。 結(jié)果，每個(gè)盤的讀負(fù)荷和寫負(fù)荷是一樣的。如果所有的塊有相同的可能性被寫,數(shù)據(jù)存儲(chǔ),數(shù)據(jù)元素的表示,1. 定長(zhǎng)字符串 C H A R(n)描述定長(zhǎng)字符串，它們是長(zhǎng)度為n的定長(zhǎng)字符串。 對(duì)應(yīng)于具有這種類型屬性的字段是n字節(jié)的數(shù)組。假如長(zhǎng)度小于n的字符串，則字節(jié)數(shù)組用特定的填充符號(hào)填充，填充符號(hào)的8位編碼不是S Q L字符串的合法字符。 例如， 如果一個(gè)屬性A聲明是類型C H A R( 5 )，則在所有的元組中與A對(duì)應(yīng)的字段是一個(gè)5字符數(shù)組。 如

40、果在一個(gè)元組中，對(duì)應(yīng)于屬性A的成分是“ c a t”，則這個(gè)數(shù)組的值是：c a t其中，是“填充”字符，它占據(jù)這個(gè)數(shù)組的第四和第五個(gè)字節(jié)。,2 .變長(zhǎng)字符串 V A R C H A R（n）描述變長(zhǎng)字符串 對(duì)V A R C H A R字符串有兩種常見的表示： 1) 長(zhǎng)度加內(nèi)容。 分配一個(gè)n+ 1字節(jié)的數(shù)組。第一個(gè)字節(jié)存儲(chǔ)字符串中字節(jié)數(shù)，第二個(gè)及以后的字節(jié)存儲(chǔ)字符串中的字符。 例如：3 c a t 2) 空值-終止字符串。為字符串的值分配一個(gè)n+ 1字節(jié)的數(shù)組。用字符串的字符填充 這個(gè)數(shù)組，其后跟一個(gè)空字符，它不是可以出現(xiàn)在字符串中的合法字符。這種方法的V A R C H A R字符串的表示與C

41、中字符串的表示兼容。 例如：c a t,3 .日期和時(shí)間 1）日期表示為符合某種格式的定長(zhǎng)字符串 例如，S Q L 2標(biāo)準(zhǔn)中日期表示為形如Y Y Y Y - M M - D D的1 0字符字符串，字符串1 9 4 8 - 0 5 - 1 4表示1 9 4 8年5月4日。 2）時(shí)間用字符串表示。 例如， S Q L 2標(biāo)準(zhǔn)將整秒數(shù)時(shí)間表示為形如H H : M M : S S的8字符字符串，2 0 : 1 9 : 0 2表示8 : 1 9P M零2秒。 3）更精確時(shí)間表示 例如， 8:19 PM后2 . 2 5秒在S Q L 2中表示成2 0 : 1 9 : 0 2 . 2 5。因?yàn)檫@種字符串是任

42、意長(zhǎng)的，所以我們有兩種選擇： a) 系統(tǒng)可在時(shí)間的精確度上加以限制，然后把時(shí)間作為類型VA R C H A R (n)存儲(chǔ)，n是時(shí)間可以有的最大長(zhǎng)度，即9加上秒中允許的小數(shù)位數(shù)。 b) 可把時(shí)間作為真正的變長(zhǎng)值存儲(chǔ)。,定長(zhǎng)記錄的構(gòu)造 元組由記錄表示，而記錄由各種字段組成。最簡(jiǎn)單的情況是記錄的所有字段均為定長(zhǎng)，則我們可將字段連接成記錄。,有些機(jī)器可以對(duì)主存中地址為4的倍數(shù)（或8的倍數(shù)，如果機(jī)器有6 4位處理器）的字節(jié)處開始的數(shù)據(jù)進(jìn)行更有效的讀寫。 某些數(shù)據(jù)類型，如整數(shù)，也許要求必須從4的倍數(shù)的地址處開始，而其他的數(shù)據(jù)類型，如雙精度實(shí)數(shù)，可能需要從8的倍數(shù)處開始。 為簡(jiǎn)便起見，假設(shè)對(duì)數(shù)據(jù)的唯一要求

43、是字段從地址為4的倍數(shù)的主存字節(jié)處開始，那么有： 每一條記錄在塊內(nèi)從4的倍數(shù)的字節(jié)處開始 記錄中所有的字段都從與記錄起始偏移量為4的倍數(shù)的字節(jié)處開始。,記錄首部 通常在記錄中需要保存一些信息，例如，在記錄中保存： 1) 記錄模式，或是指向D B M S中存儲(chǔ)該類記錄模式的位置的一個(gè)指針 數(shù)據(jù)庫(kù)系統(tǒng)維護(hù)模式信息（由CREATE TABLE 語(yǔ)句定義） a) 關(guān)系的屬性。 b) 屬性類型。 c) 屬性在元組中出現(xiàn)的順序。 d) 屬性或關(guān)系自身上的約束，如主碼聲明，或約束某個(gè)整數(shù)屬性的值必須在某一范圍內(nèi)。 元組的記錄首部首部設(shè)置一個(gè)指針，指向存儲(chǔ)該元組所屬關(guān)系信息。 2) 記錄長(zhǎng)度 盡管元組長(zhǎng)度可從

44、它的模式中推斷出來(lái)，但是在記錄中存儲(chǔ)長(zhǎng)度信息會(huì)更方 便些。例如，不需要細(xì)查記錄內(nèi)容，只想快速地找到下一條記錄的開始，長(zhǎng)度字段可 避免存取記錄的模式，而存取記錄模式可能要進(jìn)行的磁盤I / O 3) 時(shí)間戳，指明記錄最后一次被修改或被讀的時(shí)間以及其他可能的信息。,定長(zhǎng)記錄在塊中的放置 表示關(guān)系元組的記錄存儲(chǔ)在磁盤塊中。當(dāng)需要存取或修改記錄時(shí)，記錄（與整個(gè)塊一起）就被移進(jìn)主存。 塊首部，存儲(chǔ)諸如以下各種信息： 1) 與一個(gè)或多個(gè)其他塊的鏈接，這些塊構(gòu)成一個(gè)塊的網(wǎng)絡(luò) 2) 關(guān)于這個(gè)塊在這樣一個(gè)網(wǎng)絡(luò)中所扮演的角色的信息。 3) 關(guān)于這個(gè)塊的元組屬于哪個(gè)關(guān)系的信息。 4) 一個(gè)給出每一條記錄在塊內(nèi)偏移量的

45、“目錄”。 5) 一個(gè)“塊I D” 6) 指明塊最后一次修改和/或存取時(shí)間的時(shí)間戳。,客戶機(jī)服務(wù)器系統(tǒng)地址 1) 物理地址：物理地址是字節(jié)串，據(jù)此確定二級(jí)存儲(chǔ)系統(tǒng)內(nèi)塊或記錄的位置。 物理地址包含以下信息： (a) 存儲(chǔ)所連接的主機(jī)（如果數(shù)據(jù)庫(kù)存儲(chǔ)在多臺(tái)機(jī)器上）； (b) 塊所在的磁盤或其他設(shè)備的標(biāo)識(shí)符； (c) 磁盤的柱面號(hào)； (d) 柱面內(nèi)磁道號(hào)（磁盤有多個(gè)盤面）； (e) 磁道內(nèi)塊號(hào)； (f) 記錄起始在塊內(nèi)的偏移量。,2) 邏輯地址：每一個(gè)塊或記錄有一個(gè)“邏輯地址”，這是具有某個(gè)固定長(zhǎng)度的一個(gè)字節(jié)串。存儲(chǔ)在磁盤上一個(gè)已知位置的映射表將邏輯地址與物理地址聯(lián)系起來(lái),邏輯地址和結(jié)構(gòu)地址 映射表

46、和邏輯地址可提供了相當(dāng)大的靈活性。 例如，許多數(shù)據(jù)組織方式要求移動(dòng)記錄，或者在塊內(nèi)或者從一個(gè)塊移到另一個(gè)塊。如果我們使用映射表，則所有指向這條記錄的指針參考這個(gè)映射表，當(dāng)移動(dòng)或刪除記錄時(shí)，只需改變表中這條記錄對(duì)應(yīng)的表項(xiàng)。 邏輯地址和物理地址的多種組合得到的是結(jié)構(gòu)化的地址模式。 記錄的地址=塊的物理地址+該記錄在此塊的偏移量表項(xiàng)中的偏移量。 這種塊內(nèi)間接層次提供了邏輯地址的許多長(zhǎng)處，而不需要一個(gè)全局映射表。(注意首部表項(xiàng)是從塊的前端向后增長(zhǎng)，而記錄是從塊的后端開始放置),結(jié)構(gòu)化地址的優(yōu)點(diǎn)： 可以在塊內(nèi)移動(dòng)記錄，只需改變記錄在偏移量表中的表項(xiàng) 如果偏移量表項(xiàng)足夠大，能存儲(chǔ)這條記錄的“轉(zhuǎn)向地址”，

47、我們甚至可以允許記錄移到另一個(gè)塊。 最后，如果記錄被刪除，可選擇在它的偏移量表項(xiàng)中留下一刪除標(biāo)記。 注意記錄刪除前，指向這條記錄的指針可能已存儲(chǔ)在數(shù)據(jù)庫(kù)中的不同地方。記錄刪除后，沿指向這條記錄的指針，找到刪除標(biāo)記，然后指針要么被一個(gè)空指針代替，要么修改數(shù)據(jù)結(jié)構(gòu)以反映記錄的刪除。如果我們不留下刪除標(biāo)記，指針可能會(huì)指到一些新記錄上，產(chǎn)生意外的錯(cuò)誤結(jié)果。,數(shù)據(jù)項(xiàng)的地址 塊、記錄、對(duì)象或其他可引用的數(shù)據(jù)項(xiàng)都有兩種地址形式： 1) 它在服務(wù)器的數(shù)據(jù)庫(kù)地址空間中的地址，通常是一個(gè)8字節(jié)左右的序列，指明數(shù)據(jù)項(xiàng)在系統(tǒng)的二級(jí)存儲(chǔ)器中的地址。這種地址叫做數(shù)據(jù)庫(kù)地址。 2) 虛擬內(nèi)存中的地址（假如數(shù)據(jù)項(xiàng)正緩存在虛擬

48、內(nèi)存中），這些地址通常是4個(gè)字節(jié)。這種地址稱為數(shù)據(jù)項(xiàng)的內(nèi)存地址。 數(shù)據(jù)項(xiàng)地址的訪問 當(dāng)數(shù)據(jù)項(xiàng)位于二級(jí)存儲(chǔ)器中時(shí)，必然使用數(shù)據(jù)庫(kù)地址。當(dāng)數(shù)據(jù)項(xiàng)在主存中時(shí)，既能通過它的數(shù)據(jù)庫(kù)地址和主存地址引用它。 當(dāng)數(shù)據(jù)項(xiàng)有主存指針時(shí)，使用內(nèi)存地址更有效。 轉(zhuǎn)換表：跟蹤數(shù)據(jù)庫(kù)地址要費(fèi)時(shí)得多，需要一個(gè)表將目前在虛存中的所有數(shù)據(jù)庫(kù)地址轉(zhuǎn)換成當(dāng)前內(nèi)存地址。 轉(zhuǎn)換表與邏輯地址映射表的區(qū)別： a) 邏輯和物理地址都是數(shù)據(jù)庫(kù)地址的表示，而轉(zhuǎn)換表中內(nèi)存地址用于相應(yīng)對(duì)象在內(nèi)存中的拷貝。 b ) 數(shù)據(jù)庫(kù)中所有可訪問的數(shù)據(jù)項(xiàng)在映射表中都有表項(xiàng)，而轉(zhuǎn)換表只記載當(dāng)前在內(nèi)存中的數(shù)據(jù)項(xiàng)。,指針混寫 為避免將數(shù)據(jù)庫(kù)地址重復(fù)轉(zhuǎn)換成內(nèi)存地址的開銷

49、，現(xiàn)已提出幾種技術(shù)，統(tǒng)稱為指針混寫。 當(dāng)把塊從二級(jí)存儲(chǔ)器移到主存儲(chǔ)器中時(shí)，塊內(nèi)指針可以“混寫”，即從數(shù)據(jù)庫(kù)地址空間轉(zhuǎn)換為虛擬地址空間。因此，一個(gè)指針實(shí)際上包含： 1) 一個(gè)標(biāo)志位，指明指針目前是數(shù)據(jù)庫(kù)地址還是（混寫的）內(nèi)存地址。 2) 數(shù)據(jù)庫(kù)或內(nèi)存指針。無(wú)論當(dāng)前使用哪一種地址形式，所用空間均相同。由于內(nèi)存地址通常比數(shù)據(jù)庫(kù)地址短，指針可能不使用整個(gè)空間。,指針混寫的時(shí)機(jī) 1 .自動(dòng)混寫 塊一旦被放入內(nèi)存，我們就為它的所有指針和地址定位，并且如果這些指針和地址不在轉(zhuǎn)換表中，我們將它們放入轉(zhuǎn)換表。 2. 按需混寫 當(dāng)塊第一次被移入內(nèi)存時(shí)，所有指針都不混寫。將它的地址以及其指針的地址與相應(yīng)的內(nèi)存地址一

50、起放入轉(zhuǎn)換表。當(dāng)跟蹤某個(gè)內(nèi)存塊中的指針P時(shí)，才將它混寫。 按需混寫與自動(dòng)混寫的區(qū)別是當(dāng)塊被裝載進(jìn)內(nèi)存時(shí)，自動(dòng)混寫試圖快速、有效地混寫所有指針。但是某些混寫指針永遠(yuǎn)也用不上，花費(fèi)在混寫和不混寫指針的時(shí)間將被浪費(fèi)。 3. 不混寫 需要轉(zhuǎn)換表，以使指針可以以它們未混寫的形式被跟蹤。 4. 混寫的人工控制 在某些應(yīng)用中，應(yīng)用程序員可能會(huì)知道塊中的指針是否被跟蹤。該程序員可顯式地指明裝載進(jìn)內(nèi)存的塊中指針將被混寫，也可以只在需要時(shí)請(qǐng)求對(duì)指針進(jìn)行混寫。 例如，如果程序員知道一個(gè)塊可能被大量存取，如B樹中的根塊，那么指針將被混寫。但是，若被裝載進(jìn)內(nèi)存中的塊只使用一次，然后就從內(nèi)存中刪除，則它不被混寫。 塊返回

51、磁盤 當(dāng)塊被從主存移回到磁盤中時(shí)，塊中的任何指針必須解除混寫；即它們的內(nèi)存地址必須由相應(yīng)的數(shù)據(jù)庫(kù)地址取代。 轉(zhuǎn)換表可用于將兩種類型的指針進(jìn)行雙向聯(lián)系，給定一個(gè)內(nèi)存地址，可以找到與其對(duì)應(yīng)的數(shù)據(jù)庫(kù)地址。,變長(zhǎng)數(shù)據(jù)和記錄,具有變長(zhǎng)字段的記錄 如果記錄的一個(gè)或多個(gè)字段是變長(zhǎng)的，則可將所有定長(zhǎng)字段放在變長(zhǎng)字段之前，并在記錄首部寫入以下信息： 1) 記錄長(zhǎng)度。 2) 指向所有變長(zhǎng)字段起始處（即偏移量）的指針 下面例子中姓名和住址是邊長(zhǎng)字段,重復(fù)次數(shù)不確定的字段 如果定長(zhǎng)字段F出現(xiàn)的次數(shù)可變，可將所有字段F的放在一起，在記錄首部放一個(gè)指針，讓它指向字段F出現(xiàn)的第一個(gè)位置。 可用以下方法找到字段F出現(xiàn)的所有位

52、置：令字段F的一次出現(xiàn)占用的字節(jié)數(shù)為L(zhǎng)，然后在字段F的偏移量上加上L的所有整數(shù)倍數(shù)，從0開始而后L、2L、3L，依此類推。 例如， 元組存儲(chǔ)姓名、地址（為變長(zhǎng)字符串）和主演的影片的指針。 地理數(shù)據(jù)中，一條線包含的點(diǎn)的數(shù)量不確定,另一種表示方法 保持記錄定長(zhǎng)，而將變長(zhǎng)部分（變長(zhǎng)字段或重復(fù)次數(shù)不確定的字段）放在另一個(gè)塊上。 在記錄本身存儲(chǔ) 1) 指向每一個(gè)重復(fù)字段開始處的指針 2) 重復(fù)次數(shù)或者重復(fù)結(jié)束處。,變格式的記錄 記錄沒有固定的模式，字段或字段順序不是完全由記錄所表示元組或?qū)ο蟮年P(guān)系或類決定。 標(biāo)記字段序列 每一個(gè)標(biāo)記字段包含以下內(nèi)容： 1) 關(guān)于這個(gè)字段角色的信息，如 (a) 屬性或字段

53、名， (b) 字段類型，如果它不能從字段名和一些可用的模式信息中明顯推知，以及 (c) 字段長(zhǎng)度，如果它不能從類型明顯推知。 2) 字段值。 標(biāo)記字段的優(yōu)點(diǎn)： 1) 信息集成應(yīng)用。當(dāng)數(shù)據(jù)源很多，信息種類很多，使用標(biāo)識(shí)，只列出非空字段，可節(jié)省相當(dāng)大的空間。 2) 具有非常靈活的模式的記錄。一條記錄的許多字段會(huì)重復(fù)或根本不出現(xiàn)，那么即使我們知道模式，標(biāo)識(shí)字段也可能是有用的。例如，醫(yī)療記錄可能包含許多有關(guān)檢驗(yàn)的信息，但是可做的檢驗(yàn)數(shù)以千計(jì)，而每一個(gè)病人只有較少的檢驗(yàn)結(jié)果。 地理數(shù)據(jù)存在大量變格式記錄，比如氣象站測(cè)量記錄等,跨塊數(shù)據(jù) 記錄跨塊存儲(chǔ)的原因： 某些數(shù)據(jù)類型字段太大不能裝入一個(gè)塊中（比如音頻

54、，視頻，遙感圖像） 記錄的大小比塊的一半稍大，造成存儲(chǔ)浪費(fèi)，需要跨塊處理 出現(xiàn)在一個(gè)塊中的記錄的一部分被稱為記錄片段。 一個(gè)具有兩個(gè)或多個(gè)片段的記錄被稱為是跨塊的 不跨越塊邊界的記錄是不跨塊的。 如果記錄能跨塊，則每一條記錄和記錄片段需要一些另外的首部信息： 1) 每一條記錄或片段首部必須包含一個(gè)標(biāo)志位，指明是否為一個(gè)片段。 2) 如果是一個(gè)片段，則它需要幾個(gè)標(biāo)志位，指明是否為第一個(gè)或最后一個(gè)片段。 3) 如果對(duì)同一條記錄有下一個(gè)和/或前一個(gè)片段，則片段需要指向這樣一些其他片段的指針。,二進(jìn)制大對(duì)象（B L O B） 1. BLOB的存儲(chǔ) B L O B必須存儲(chǔ)在一系列塊中，這些塊在磁盤的一個(gè)

55、或多個(gè)柱面上順序分配，提高檢索效率。 將B L O B存儲(chǔ)在塊的鏈表中。 將B L O B進(jìn)行分割，存儲(chǔ)在幾個(gè)磁盤中，即在這些磁盤上交替存儲(chǔ)B L O B的塊。這樣就可以同時(shí)檢索B L O B的幾個(gè)塊，檢索效率提高的倍數(shù)大約等于參與分割的磁盤數(shù)。 2. BLOB的檢索 傳送記錄的“小”字段，同時(shí)允許客戶端一次一個(gè)地請(qǐng)求B L O B的塊，而與記錄的其余部分無(wú)關(guān)。 在許多應(yīng)用中，客戶端能請(qǐng)求B L O B內(nèi)的部分，而不必接收整個(gè)B L O B，這也很重要。 如果D B M S要支持這些操作，那么需要合適的索引結(jié)構(gòu)，例如，在一個(gè)電影B L O B上通過秒進(jìn)行索引。 地理數(shù)據(jù)遙感圖像金字塔處理,插入

56、記錄 記錄沒有特定的存儲(chǔ)順序：需找到一些有空閑空間的塊，或當(dāng)塊沒有空閑空間時(shí)就找一個(gè)新塊，然后將記錄放在那里 若元組必須以某個(gè)固定次序存儲(chǔ)：首先要找到那條記錄應(yīng)放置的塊。 此塊如果有空間存放這條新記錄，則在塊中滑動(dòng)記錄以在合適的地點(diǎn)得到所需的空間 此塊如果沒有有空間存放這條新記錄，則 1) 在“鄰近塊”中找空間。如果有外部指針指向需要移動(dòng)記錄，則要在偏移量表中留下一個(gè)轉(zhuǎn)發(fā)地址（forwarding address），說(shuō)明某一記錄被移到新的地址 2) 創(chuàng)建一個(gè)溢出塊。在這種模式下，每個(gè)塊B的首部有一個(gè)位置，這個(gè)位置存放一個(gè)指向溢出塊的指針，理論上屬于B的多余的記錄放入溢出塊中。B的溢出塊可以指向

57、第二個(gè)溢出塊，依此類推,刪除記錄 滑動(dòng)記錄，回收空間（右上圖） 可用空間指針列表（右下圖） 溢出塊刪除：對(duì)溢出鏈表進(jìn)行維護(hù) 懸掛指針處理：設(shè)置刪除標(biāo)志，這個(gè)刪除標(biāo)記是永久的；它必須一直保留，直到對(duì)整個(gè)數(shù)據(jù)庫(kù)進(jìn)行重構(gòu)。,修改記錄 定長(zhǎng)記錄：對(duì)存儲(chǔ)系統(tǒng)沒有影響 變長(zhǎng)記錄： 存儲(chǔ)空間發(fā)生變化，與插入和刪除處理相似，但不需要為記錄的舊版本創(chuàng)建刪除標(biāo)記。 如果修改后的記錄比其舊版本長(zhǎng)，則我們可能需要在它所在的塊中創(chuàng)建更多的空間?？赡苌婕坝涗浀幕瑒?dòng)，或創(chuàng)建一個(gè)溢出塊 如果記錄由于修改而變短，可以像刪除記錄時(shí)那樣恢復(fù)、合并空間或去除溢出塊。,索引結(jié)構(gòu),索引是這樣一種數(shù)據(jù)結(jié)構(gòu)：以記錄的特征（通常是一個(gè)或多個(gè)字

58、段的值）為輸入，并能“快速地”找出具有該特征的記錄。 索引只需查看所有可能記錄中的一小部分就能找到所需記錄。建立索引的字段（組合）稱為查找鍵，在簡(jiǎn)稱“鍵”。 索引方法： 1) 排序文件上的簡(jiǎn)單索引。 2) 非排序文件上的輔助索引。 3) B樹，一種可在任何文件 上建立索引的常用方法。 4) 散列表,順序文件上的索引,文件按索引的屬性排序，這樣的文件稱為順序文件 順序文件的索引文件：索引文件由鍵-指針對(duì)組成。 在索引文件中查找鍵K通過指針指向數(shù)據(jù)文件中查找鍵為K的記錄。 索引可以是“稠密的”，即數(shù)據(jù)文件中每個(gè)記錄在索引文件中都設(shè)有一個(gè)索引項(xiàng)。它是這樣的一系列存儲(chǔ)塊：塊中只存放記錄的鍵以及指向記錄

59、本身的指針 索引也可以是“稀疏的”，即數(shù)據(jù)文件中只有某些記錄在索引文件中表示出來(lái)，通常為每個(gè)數(shù)據(jù)塊在索引文件中設(shè)一個(gè)索引項(xiàng)。,索引查找的優(yōu)勢(shì) 1) 索引塊數(shù)量通常比數(shù)據(jù)塊數(shù)量少。 2) 由于鍵被排序，我們可以使用二分查找法來(lái)查找K。若有n個(gè)索引塊，我們只需查找l o g 2n個(gè)塊。 3) 索引文件可能足夠小，以致可以永久地存放在主存緩沖區(qū)中。要是這樣的話，查找鍵K時(shí)就只涉及主存訪問而不需執(zhí)行I / O操作。,稀疏索引查找方法 在索引中查找鍵值小于或等于K的最大鍵值。由于索引文件已按鍵排序，可以使用二分查找法來(lái)定位這個(gè)索引項(xiàng)，然后根據(jù)它的指針找到相應(yīng)的數(shù)據(jù)塊。 稠密索引與稀疏索引的差別 稀疏索引所需的索引存儲(chǔ)塊要比稠密索引少得多 稠密索引不用去檢索包含記錄的塊，就可以回答下面形式的查詢：“是否存在鍵值為K的記錄？”。鍵K在索引中的存在足以保證數(shù)據(jù)文件中鍵值為K的記錄的存在。 如果使用稀疏索引，對(duì)于同樣的查詢，卻需要執(zhí)行I / O操作去檢索可能存在鍵值為K的記錄的塊。,多級(jí)索引,索引文件本身可能占據(jù)多個(gè)存儲(chǔ)塊，可能需要執(zhí)行多次I / O操作才能得到我們所需的記錄。 通過在