第14講數(shù)據(jù)庫的存儲管理

1、第6章 數(shù)據(jù)庫的存儲管理 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 文件的組織結(jié)構(gòu) 邏輯文件中的數(shù)據(jù)在物理文件中如何存儲邏輯文件中的數(shù)據(jù)在物理文件中如何存儲 文件的存儲結(jié)構(gòu) 邏輯文件中的數(shù)據(jù)在磁盤存儲器上如何存放邏輯文件中的數(shù)據(jù)在磁盤存儲器上如何存放 文件的存取方法 針對某種存儲結(jié)構(gòu)的文件怎樣去查找、插入和針對某種存儲結(jié)構(gòu)的文件怎樣去查找、插入和刪除記錄等問題。刪除記錄等問題。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 數(shù)據(jù)庫存儲管理的數(shù)據(jù) 磁盤上數(shù)據(jù)的存儲 文件的組織結(jié)構(gòu) 文件的存儲結(jié)構(gòu) 索引文件的概念第第14講講 數(shù)

2、據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫存儲管理的數(shù)據(jù) 數(shù)據(jù)庫系統(tǒng)實現(xiàn)的一個重要問題 如何以最優(yōu)的形式組織和存放數(shù)據(jù)庫中大量有如何以最優(yōu)的形式組織和存放數(shù)據(jù)庫中大量有結(jié)構(gòu)的綜合性的持久數(shù)據(jù)結(jié)構(gòu)的綜合性的持久數(shù)據(jù) 最優(yōu)是指最優(yōu)是指 存儲效率高，節(jié)省空間存儲效率高，節(jié)省空間 存取效率高，代價低存取效率高，代價低第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫存儲管理的數(shù)據(jù) 數(shù)據(jù)庫的存儲管理的基本問題 數(shù)據(jù)庫是大量有結(jié)構(gòu)的相關(guān)的持久數(shù)據(jù)集合。數(shù)據(jù)庫是大量有結(jié)構(gòu)的相關(guān)的持久數(shù)據(jù)集合。 存儲在存儲介質(zhì)上的數(shù)據(jù)被組織為記錄文件存儲在存儲介質(zhì)上的數(shù)據(jù)被組織為記錄文件

3、每個記錄是數(shù)據(jù)值的一個集合每個記錄是數(shù)據(jù)值的一個集合 數(shù)據(jù)值描述了有關(guān)實體、實體屬性及其聯(lián)系數(shù)據(jù)值描述了有關(guān)實體、實體屬性及其聯(lián)系 存儲存儲4個方面的數(shù)據(jù)個方面的數(shù)據(jù) 數(shù)據(jù)描述數(shù)據(jù)描述，即數(shù)據(jù)外模式、模式、內(nèi)模式，即數(shù)據(jù)外模式、模式、內(nèi)模式 數(shù)據(jù)本身數(shù)據(jù)本身 數(shù)據(jù)之間的聯(lián)系數(shù)據(jù)之間的聯(lián)系 存取路徑存取路徑第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫存儲管理的數(shù)據(jù) 數(shù)據(jù)庫系統(tǒng)存儲的數(shù)據(jù) 數(shù)據(jù)描述數(shù)據(jù)描述 系統(tǒng)運行時所涉及的各種系統(tǒng)運行時所涉及的各種對象及其屬性對象及其屬性的描述信息的描述信息 描述數(shù)據(jù)庫結(jié)構(gòu)及其約束的數(shù)據(jù)庫模式、視圖、存描述數(shù)據(jù)庫結(jié)構(gòu)及其約束的數(shù)據(jù)庫模

4、式、視圖、存取路徑（索引、散列等）、訪問權(quán)限以及數(shù)據(jù)庫狀取路徑（索引、散列等）、訪問權(quán)限以及數(shù)據(jù)庫狀態(tài)信息的記錄和統(tǒng)計。態(tài)信息的記錄和統(tǒng)計。 系統(tǒng)中系統(tǒng)中對象之間關(guān)系對象之間關(guān)系的描述信息的描述信息 包括各級模式間的映射關(guān)系、用戶與子模式間的對包括各級模式間的映射關(guān)系、用戶與子模式間的對應(yīng)關(guān)系等應(yīng)關(guān)系等第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫存儲管理的數(shù)據(jù) 數(shù)據(jù)庫系統(tǒng)存儲的數(shù)據(jù) 數(shù)據(jù)描述數(shù)據(jù)描述 有關(guān)數(shù)據(jù)的描述（稱為元數(shù)據(jù)）存儲在數(shù)據(jù)庫的數(shù)有關(guān)數(shù)據(jù)的描述（稱為元數(shù)據(jù)）存儲在數(shù)據(jù)庫的數(shù)據(jù)字典中。據(jù)字典中。 數(shù)據(jù)字典是數(shù)據(jù)庫系統(tǒng)運作的基礎(chǔ)，任何數(shù)據(jù)庫操數(shù)據(jù)字典是數(shù)據(jù)

5、庫系統(tǒng)運作的基礎(chǔ)，任何數(shù)據(jù)庫操作都要參照數(shù)據(jù)字典的內(nèi)容。作都要參照數(shù)據(jù)字典的內(nèi)容。 關(guān)系數(shù)據(jù)庫中數(shù)據(jù)字典的組織通常與數(shù)據(jù)本身的組關(guān)系數(shù)據(jù)庫中數(shù)據(jù)字典的組織通常與數(shù)據(jù)本身的組織相同?？椣嗤?按內(nèi)容的不同在邏輯上組織為若干張表，在物理上按內(nèi)容的不同在邏輯上組織為若干張表，在物理上就對應(yīng)若干文件而不是一個文件。由于每個文件中就對應(yīng)若干文件而不是一個文件。由于每個文件中存放數(shù)據(jù)量不大，可簡單地用順序文件來組織。存放數(shù)據(jù)量不大，可簡單地用順序文件來組織。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫存儲管理的數(shù)據(jù) 數(shù)據(jù)庫系統(tǒng)存儲的數(shù)據(jù) 數(shù)據(jù)及數(shù)據(jù)間的聯(lián)系數(shù)據(jù)及數(shù)據(jù)間的聯(lián)系 在

6、在RDBMS中數(shù)據(jù)和數(shù)據(jù)之間的聯(lián)系兩者組織方式中數(shù)據(jù)和數(shù)據(jù)之間的聯(lián)系兩者組織方式相同。相同。 數(shù)據(jù)和數(shù)據(jù)之間的聯(lián)系都用一種數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)和數(shù)據(jù)之間的聯(lián)系都用一種數(shù)據(jù)結(jié)構(gòu)“表表”來表示。來表示。 在數(shù)據(jù)庫的物理組織中，每一個表通常對應(yīng)一種文在數(shù)據(jù)庫的物理組織中，每一個表通常對應(yīng)一種文件存儲結(jié)構(gòu)。件存儲結(jié)構(gòu)。 文件存儲結(jié)構(gòu)是定義一個關(guān)系表文件中記錄的特定文件存儲結(jié)構(gòu)是定義一個關(guān)系表文件中記錄的特定組織形式組織形式 。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫存儲管理的數(shù)據(jù) 數(shù)據(jù)庫系統(tǒng)存儲的數(shù)據(jù) 存取路徑存取路徑 是實現(xiàn)數(shù)據(jù)訪問和存儲的基本手段。在關(guān)系數(shù)據(jù)庫是實現(xiàn)數(shù)據(jù)訪問

7、和存儲的基本手段。在關(guān)系數(shù)據(jù)庫中是指訪問一個關(guān)系表文件中記錄集合的特殊技術(shù)中是指訪問一個關(guān)系表文件中記錄集合的特殊技術(shù)。 存取路徑基于表存儲結(jié)構(gòu)，或基于所選擇的表上可存取路徑基于表存儲結(jié)構(gòu)，或基于所選擇的表上可用的索引。用的索引。 索引是附屬的數(shù)據(jù)庫結(jié)構(gòu)，可能是單獨存儲的一個索引是附屬的數(shù)據(jù)庫結(jié)構(gòu)，可能是單獨存儲的一個文件，它支持對表中行的快速訪問。文件，它支持對表中行的快速訪問。 存取路徑的物理組織通常采用存取路徑的物理組織通常采用B+樹類文件結(jié)構(gòu)和樹類文件結(jié)構(gòu)和HASH類文件結(jié)構(gòu)。類文件結(jié)構(gòu)。 在關(guān)系數(shù)據(jù)庫中，存取路徑和數(shù)據(jù)是分離的，對用在關(guān)系數(shù)據(jù)庫中，存取路徑和數(shù)據(jù)是分離的，對用戶是隱蔽

8、的。戶是隱蔽的。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫存儲管理的數(shù)據(jù) 數(shù)據(jù)庫系統(tǒng)存儲的數(shù)據(jù) 存儲存儲4個方面的數(shù)據(jù)個方面的數(shù)據(jù) 數(shù)據(jù)描述數(shù)據(jù)描述，即數(shù)據(jù)外模式、模式、內(nèi)模式，即數(shù)據(jù)外模式、模式、內(nèi)模式 數(shù)據(jù)本身數(shù)據(jù)本身 數(shù)據(jù)之間的聯(lián)系數(shù)據(jù)之間的聯(lián)系 存取路徑存取路徑 數(shù)據(jù)庫系統(tǒng)中的這些數(shù)據(jù)都要采用一定的文件數(shù)據(jù)庫系統(tǒng)中的這些數(shù)據(jù)都要采用一定的文件組織來組織、存儲起來組織來組織、存儲起來 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 SQL Server的的存儲架構(gòu)存儲架構(gòu)數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫存儲管理的數(shù)據(jù)第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理

9、SQL Server的存儲架構(gòu)數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫存儲管理的數(shù)據(jù)第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 SQL Server的存儲架構(gòu)數(shù)據(jù)庫存儲管理的數(shù)據(jù)數(shù)據(jù)庫存儲管理的數(shù)據(jù)第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 數(shù)據(jù)庫存儲管理的數(shù)據(jù) 磁盤上數(shù)據(jù)的存儲 文件的組織結(jié)構(gòu) 文件的存儲結(jié)構(gòu) 索引文件的概念第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的存儲 計算機存儲系統(tǒng)的層次結(jié)構(gòu)寄存器寄存器高速緩存高速緩存主存儲器主存儲器磁盤緩存磁盤緩存固定磁盤固定磁盤可移動存儲介質(zhì)可移動存儲介質(zhì)第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的

10、存儲管理 磁盤的物理特性S磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的存儲第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 磁盤的物理特性 容量容量 磁盤的總?cè)萘看疟P的總?cè)萘?盤面數(shù)盤面數(shù)每盤面的磁道數(shù)每盤面的磁道數(shù)每磁道的扇區(qū)數(shù)每磁道的扇區(qū)數(shù)每扇區(qū)的字節(jié)數(shù)。目前磁盤的容量可以達到每扇區(qū)的字節(jié)數(shù)。目前磁盤的容量可以達到1TB 。 存取時間存取時間 從發(fā)出讀從發(fā)出讀/寫請求到數(shù)據(jù)傳輸開始這一段時間寫請求到數(shù)據(jù)傳輸開始這一段時間 數(shù)據(jù)傳輸速率數(shù)據(jù)傳輸速率 磁頭傳輸數(shù)據(jù)的速率，取決于盤片的旋轉(zhuǎn)速度和盤片表面的位磁頭傳輸數(shù)據(jù)的速率，取決于盤片的旋轉(zhuǎn)速度和盤片表面的位密度。每秒可達幾十兆字節(jié)。密度。每秒可達幾十兆字節(jié)。

11、磁盤的可靠性磁盤的可靠性 用平均故障時間來說明磁盤無故障連續(xù)運行的特性。一般在用平均故障時間來說明磁盤無故障連續(xù)運行的特性。一般在38萬小時（萬小時（3.49.1年）內(nèi)不出故障。年）內(nèi)不出故障。磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的存儲第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 磁盤的物理特性 存取時間存取時間 尋道時間（磁頭定位）尋道時間（磁頭定位） 磁頭定位于包含扇區(qū)磁頭定位于包含扇區(qū)S的柱面的柱面上方所用的時間。平均尋道時上方所用的時間。平均尋道時間是間是110ms。 旋轉(zhuǎn)延遲時間旋轉(zhuǎn)延遲時間 磁頭處于柱面的上方到定位扇磁頭處于柱面的上方到定位扇區(qū)區(qū)S的開始處的上方。平均約的開始處的上方。平均

12、約需轉(zhuǎn)半圈的時間，需轉(zhuǎn)半圈的時間，110ms。 傳輸時間傳輸時間 盤片旋轉(zhuǎn)經(jīng)過扇區(qū)盤片旋轉(zhuǎn)經(jīng)過扇區(qū)S所花費的所花費的時間，受旋轉(zhuǎn)時間的限制。時間，受旋轉(zhuǎn)時間的限制。1msS磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的存儲第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 磁盤上數(shù)據(jù)的緩沖存取磁盤上數(shù)據(jù)的緩沖存取 磁盤是一種低速設(shè)備磁盤是一種低速設(shè)備 通常情況下，訪問一個扇區(qū)的時間是通常情況下，訪問一個扇區(qū)的時間是10ms級。級。 CPU可以利用訪問一個扇區(qū)的時間執(zhí)行成百上千條指令?？梢岳迷L問一個扇區(qū)的時間執(zhí)行成百上千條指令。 優(yōu)化主存和磁盤之間的信息流以優(yōu)化一個數(shù)據(jù)庫系統(tǒng)的優(yōu)化主存和磁盤之間的信息流以優(yōu)化一個數(shù)

13、據(jù)庫系統(tǒng)的性能。性能。 DBMS通過在內(nèi)存中開辟通過在內(nèi)存中開辟“緩沖區(qū)緩沖區(qū)”，采用，采用“預(yù)先讀延預(yù)先讀延遲寫遲寫”的磁盤緩沖存取技術(shù)來匹配磁盤和內(nèi)存的存取速的磁盤緩沖存取技術(shù)來匹配磁盤和內(nèi)存的存取速度。度。 磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的存儲第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 磁盤上數(shù)據(jù)的緩沖存取磁盤上數(shù)據(jù)的緩沖存取 磁盤塊和磁盤緩沖區(qū)磁盤塊和磁盤緩沖區(qū) 數(shù)據(jù)在磁盤上以稱為數(shù)據(jù)在磁盤上以稱為“塊塊”的定長存儲單位形式的定長存儲單位形式組織。組織。 塊是一個磁道上順序存儲的多個相鄰扇區(qū)。只需塊是一個磁道上順序存儲的多個相鄰扇區(qū)。只需一次時間延遲來將磁頭定位于包含該塊的起始處一次時

14、間延遲來將磁頭定位于包含該塊的起始處。 塊（也稱作塊（也稱作“頁頁”）是內(nèi)、外存數(shù)據(jù)交換的基本）是內(nèi)、外存數(shù)據(jù)交換的基本單位。單位。 磁盤中的塊稱為磁盤中的塊稱為“物理磁盤塊物理磁盤塊”（或（或“磁盤塊磁盤塊”），內(nèi)存中臨時存放磁盤塊內(nèi)容的塊稱為），內(nèi)存中臨時存放磁盤塊內(nèi)容的塊稱為“緩沖緩沖塊塊”，所有的內(nèi)存，所有的內(nèi)存“緩沖塊緩沖塊”組成了組成了“磁盤緩沖磁盤緩沖區(qū)區(qū)”。 磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的存儲第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 磁盤上數(shù)據(jù)的緩沖存取磁盤上數(shù)據(jù)的緩沖存取 磁盤塊和磁盤緩沖區(qū)磁盤塊和磁盤緩沖區(qū) 典型的磁盤塊的大小為典型的磁盤塊的大小為464KB 磁盤塊應(yīng)足

15、夠大，以便能容得下特定應(yīng)用所要訪問的記磁盤塊應(yīng)足夠大，以便能容得下特定應(yīng)用所要訪問的記錄從而避免對磁盤的另一次訪問。錄從而避免對磁盤的另一次訪問。 磁盤塊增大，數(shù)據(jù)的傳輸時間會增加，大的磁盤塊要求磁盤塊增大，數(shù)據(jù)的傳輸時間會增加，大的磁盤塊要求內(nèi)存中有大的緩沖區(qū)，而且也可能大大地超出應(yīng)用實際內(nèi)存中有大的緩沖區(qū)，而且也可能大大地超出應(yīng)用實際要訪問的信息（如超出一個表所包含的信息）。要訪問的信息（如超出一個表所包含的信息）。磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的存儲第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 磁盤上數(shù)據(jù)的緩沖存取磁盤上數(shù)據(jù)的緩沖存取 緩沖區(qū)管理器緩沖區(qū)管理器 負責(zé)為數(shù)據(jù)庫上的查詢等處理過

16、程提供內(nèi)存緩沖負責(zé)為數(shù)據(jù)庫上的查詢等處理過程提供內(nèi)存緩沖區(qū)空間分配和管理的子系統(tǒng)。區(qū)空間分配和管理的子系統(tǒng)。 職責(zé)是使處理過程得到它們所需的內(nèi)存，并且盡職責(zé)是使處理過程得到它們所需的內(nèi)存，并且盡可能縮小延遲和減少不可滿足的要求?？赡芸s小延遲和減少不可滿足的要求。磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的存儲第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫緩沖區(qū)數(shù)據(jù)庫緩沖區(qū)DiskMemoryX InputOutputI/O操作操作程序工作區(qū)程序工作區(qū) Read（X) Write(X)X 磁盤上數(shù)據(jù)的緩沖存取磁盤上數(shù)據(jù)的緩沖存取 緩沖區(qū)管理器緩沖區(qū)管理器 磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的存儲緩沖區(qū)管理器緩沖區(qū)

17、管理器第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 磁盤上數(shù)據(jù)的緩沖存取磁盤上數(shù)據(jù)的緩沖存取 緩沖區(qū)管理器緩沖區(qū)管理器 使用緩沖使用緩沖-替換策略對磁盤緩沖區(qū)進行維護。替換策略對磁盤緩沖區(qū)進行維護。 原則：最近被訪問的磁盤塊是活動的，它在不久的將來被原則：最近被訪問的磁盤塊是活動的，它在不久的將來被再次引用的概率很高，所以這個磁盤塊應(yīng)保存在磁盤緩沖再次引用的概率很高，所以這個磁盤塊應(yīng)保存在磁盤緩沖區(qū)中。區(qū)中。 最近最少使用（最近最少使用（LRU，Least Recently Used）策略其規(guī)）策略其規(guī)則就是丟出最長時間沒有讀或?qū)戇^的塊。一般來說，長時則就是丟出最長時間沒有讀或?qū)戇^的塊。一般

18、來說，長時間沒有使用的緩沖塊比那些最近被訪問過的緩沖塊有更小間沒有使用的緩沖塊比那些最近被訪問過的緩沖塊有更小的最近訪問的可能性，的最近訪問的可能性，LRU是一個有效的策略。是一個有效的策略。 近年來在主要的操作系統(tǒng)和數(shù)據(jù)庫系統(tǒng)中，一種改進的自近年來在主要的操作系統(tǒng)和數(shù)據(jù)庫系統(tǒng)中，一種改進的自適應(yīng)緩存管理替換算法適應(yīng)緩存管理替換算法LIRS（Low Inter-Reference recency Set）及其近似實現(xiàn)方法逐步取代了）及其近似實現(xiàn)方法逐步取代了LRU，更新，更新了存儲管理的關(guān)鍵技術(shù)。了存儲管理的關(guān)鍵技術(shù)。磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的存儲第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管

19、理 磁盤上數(shù)據(jù)的緩沖存取磁盤上數(shù)據(jù)的緩沖存取 緩沖區(qū)管理器緩沖區(qū)管理器 I/O 操作操作（Input或或Output操作）是由操作系統(tǒng)中的操作）是由操作系統(tǒng)中的文件系統(tǒng)完成的，數(shù)據(jù)庫管理系統(tǒng)只需要調(diào)用操作文件系統(tǒng)完成的，數(shù)據(jù)庫管理系統(tǒng)只需要調(diào)用操作系統(tǒng)的這一功能。系統(tǒng)的這一功能。 數(shù)據(jù)庫存儲在一個數(shù)據(jù)庫存儲在一個Megatron 747磁盤上，它能夠以磁盤上，它能夠以11ms級別的時間讀取級別的時間讀取16KB的磁盤塊。在的磁盤塊。在11ms中，一個現(xiàn)代處中，一個現(xiàn)代處理器可以執(zhí)行幾百萬的指令。因此在主存中執(zhí)行搜索的附理器可以執(zhí)行幾百萬的指令。因此在主存中執(zhí)行搜索的附加時間將比塊訪問時間的加時

20、間將比塊訪問時間的1%還要少，可以安全地忽略之還要少，可以安全地忽略之。 磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的存儲 加速數(shù)據(jù)庫操作，提高數(shù)據(jù)庫的性能的關(guān)鍵技術(shù)是安加速數(shù)據(jù)庫操作，提高數(shù)據(jù)庫的性能的關(guān)鍵技術(shù)是安排好數(shù)據(jù)，使得當(dāng)某一個磁盤塊中有數(shù)據(jù)被訪問時，大排好數(shù)據(jù)，使得當(dāng)某一個磁盤塊中有數(shù)據(jù)被訪問時，大約在同時很有可能該塊上的其他數(shù)據(jù)也需要被訪問。約在同時很有可能該塊上的其他數(shù)據(jù)也需要被訪問。 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 數(shù)據(jù)庫系統(tǒng)所要解決的問題數(shù)據(jù)庫系統(tǒng)所要解決的問題 記錄如何存儲在數(shù)據(jù)文件中，使得應(yīng)用所要訪問的記記錄如何存儲在數(shù)據(jù)文件中，使得應(yīng)用所要訪問的記錄盡量在相同的磁盤塊

21、上，應(yīng)用訪問所需的磁盤錄盡量在相同的磁盤塊上，應(yīng)用訪問所需的磁盤I/O操操作次數(shù)最少；作次數(shù)最少； 怎樣盡快找到記錄所在的磁盤塊，使得找到該記錄所怎樣盡快找到記錄所在的磁盤塊，使得找到該記錄所需磁盤需磁盤I/O操作次數(shù)最少。操作次數(shù)最少。磁盤上數(shù)據(jù)的存儲磁盤上數(shù)據(jù)的存儲文件存儲結(jié)構(gòu)文件存儲結(jié)構(gòu)文件存取方法文件存取方法第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 數(shù)據(jù)庫存儲管理的數(shù)據(jù) 磁盤上數(shù)據(jù)的存儲 文件的組織結(jié)構(gòu) 文件的存儲結(jié)構(gòu) 索引文件的概念第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 在磁盤上，數(shù)據(jù)庫以文件形式組織，文件由記錄組成。 記錄表示一個數(shù)據(jù)對

22、象（例如元組）在磁盤塊記錄表示一個數(shù)據(jù)對象（例如元組）在磁盤塊中的連續(xù)字節(jié)存放。中的連續(xù)字節(jié)存放。 每條記錄由一些字段（相關(guān)數(shù)據(jù)值或數(shù)據(jù)項）集合每條記錄由一些字段（相關(guān)數(shù)據(jù)值或數(shù)據(jù)項）集合組成。字段名及其相應(yīng)數(shù)據(jù)類型的值集合即構(gòu)成了組成。字段名及其相應(yīng)數(shù)據(jù)類型的值集合即構(gòu)成了一個記錄類型或記錄格式定義。一個記錄類型或記錄格式定義。 表示數(shù)據(jù)庫（關(guān)系）中數(shù)據(jù)對象的記錄放在一表示數(shù)據(jù)庫（關(guān)系）中數(shù)據(jù)對象的記錄放在一個或多個磁盤塊中。個或多個磁盤塊中。文件的組織結(jié)構(gòu)文件的組織結(jié)構(gòu)第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的組織結(jié)構(gòu)文件的組織結(jié)構(gòu) 記錄的物理表示 定長記錄定長記錄 定長記錄是最

23、基本、最常見的記錄存儲方式。定長記錄是最基本、最常見的記錄存儲方式。 在定長記錄中，記錄的每個字段的長度都是固定的在定長記錄中，記錄的每個字段的長度都是固定的。系統(tǒng)可以確定每個字段相對于記錄開始位置的起。系統(tǒng)可以確定每個字段相對于記錄開始位置的起始字節(jié)位置，定位字段值。始字節(jié)位置，定位字段值。 變長記錄變長記錄 文件中的不同記錄的大?。ㄗ止?jié)數(shù)）不同文件中的不同記錄的大小（字節(jié)數(shù)）不同 。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的組織結(jié)構(gòu)文件的組織結(jié)構(gòu) 定長記錄對于關(guān)系模式對于關(guān)系模式 S（SNO，SN，SEX，SB，SD）若進行如下定義：若進行如下定義：CREATE TABLE S（

24、SNO CHAR （10）PRIMARY KEY， SN CHAR（20） NOT NULL， SEX CHAR（2），）， SB DATETIME， SD CHAR（20），）， CHECK （SEX IN （男男，女女） ）；）； 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的組織結(jié)構(gòu)文件的組織結(jié)構(gòu) 定長記錄一個定長的S記錄的格式 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的組織結(jié)構(gòu)文件的組織結(jié)構(gòu) 定長記錄定長記錄在磁盤塊中的一種存儲方式 塊首部存儲如下一些信息：與一個或多個其他相關(guān)塊的鏈接。與一個或多個其他相關(guān)塊的鏈接。塊中的元組屬于哪個關(guān)系的信息。塊中的元組屬于哪個關(guān)系的

25、信息。一個給出每一條記錄在塊內(nèi)的偏移量的一個給出每一條記錄在塊內(nèi)的偏移量的“目錄目錄”；指明最后一次修改和指明最后一次修改和/ /或存取塊的時間戳?；虼嫒K的時間戳。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的組織結(jié)構(gòu)文件的組織結(jié)構(gòu) 變長記錄 文件記錄均屬于同一記錄類型，但有一個或多文件記錄均屬于同一記錄類型，但有一個或多個字段是大小變化的個字段是大小變化的 不同類型的相關(guān)記錄在磁盤塊中聚集存儲，文不同類型的相關(guān)記錄在磁盤塊中聚集存儲，文件包含不同的記錄類型的記錄等。件包含不同的記錄類型的記錄等。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的組織結(jié)構(gòu)文件的組織結(jié)構(gòu) 變長記錄 在變

26、長記錄中的字段存在如下不同格式：在變長記錄中的字段存在如下不同格式： 大小變化的數(shù)據(jù)項大小變化的數(shù)據(jù)項 重復(fù)字段重復(fù)字段 如果在一個對象的記錄中存儲關(guān)聯(lián)的對象的記錄，則有多少對象如果在一個對象的記錄中存儲關(guān)聯(lián)的對象的記錄，則有多少對象被關(guān)聯(lián)到指定對象，則在該記錄中就會存儲多少關(guān)聯(lián)的記錄。被關(guān)聯(lián)到指定對象，則在該記錄中就會存儲多少關(guān)聯(lián)的記錄。 可變格式的記錄可變格式的記錄 有時無法事先確定記錄的字段是什么，或每一個字段出現(xiàn)多少次有時無法事先確定記錄的字段是什么，或每一個字段出現(xiàn)多少次。比如表示一個。比如表示一個XML元素的一條記錄，該元素的一條記錄，該XML元素可沒有任何約元素可沒有任何約束，或

27、可能有重復(fù)的子元素和可選屬性等。束，或可能有重復(fù)的子元素和可選屬性等。 極大的字段極大的字段 現(xiàn)代現(xiàn)代DBMS支持屬性值非常大的屬性，字段可能是一些非結(jié)構(gòu)化支持屬性值非常大的屬性，字段可能是一些非結(jié)構(gòu)化的大對象數(shù)據(jù)，如圖像、數(shù)字視頻或音頻流，或者自由文本，被的大對象數(shù)據(jù)，如圖像、數(shù)字視頻或音頻流，或者自由文本，被稱為稱為BLOB（Binary Large Objects，二進制大對象）。，二進制大對象）。 例如，一個電影記錄可能有一個例如，一個電影記錄可能有一個2G大小的大小的MPEG編碼字段，還有編碼字段，還有一些普通的字段，比如電影標(biāo)題等。一些普通的字段，比如電影標(biāo)題等。第第14講講 數(shù)據(jù)

28、庫的存儲管理數(shù)據(jù)庫的存儲管理文件的組織結(jié)構(gòu)文件的組織結(jié)構(gòu) 變長記錄對于關(guān)系模式對于關(guān)系模式 S（SNO，SN，SEX，SB，SD）若進行如下定義：若進行如下定義：CREATE TABLE S（SNO CHAR （10）PRIMARY KEY， SN VARCHAR（20） NOT NULL， SEX CHAR（2），）， SB DATATIME， SD VARCHAR（20），）， CHECK （SEX IN （男男，女女） ）；）； 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的組織結(jié)構(gòu)文件的組織結(jié)構(gòu) 變長記錄 具有變長字符串的S記錄格式 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理

29、文件的組織結(jié)構(gòu)文件的組織結(jié)構(gòu) 變長記錄變長記錄在磁盤塊中的一種有偏移量表的存儲方式 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 數(shù)據(jù)庫存儲管理的數(shù)據(jù) 磁盤上數(shù)據(jù)的存儲 文件的組織結(jié)構(gòu) 文件的存儲結(jié)構(gòu) 索引文件的概念第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu) 數(shù)據(jù)庫文件的存儲結(jié)構(gòu)形式 堆文件堆文件 順序文件順序文件 聚集文件聚集文件 散列文件散列文件第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu) 堆文件 最簡單的數(shù)據(jù)文件結(jié)構(gòu)。最簡單的數(shù)據(jù)文件結(jié)構(gòu)。 數(shù)據(jù)記錄之間沒有特定的順序，文件行的順序數(shù)據(jù)記錄之間

30、沒有特定的順序，文件行的順序是任意的。是任意的。 將一條新記錄插入到文件中，只需找到一個有一些將一條新記錄插入到文件中，只需找到一個有一些空閑空間的塊，或當(dāng)塊沒有空閑空間時就找一個新空閑空間的塊，或當(dāng)塊沒有空閑空間時就找一個新塊，然后將記錄存儲在那里。塊，然后將記錄存儲在那里。 對于新建立的文件，記錄按照其插入的先后順序存對于新建立的文件，記錄按照其插入的先后順序存放，新產(chǎn)生的記錄行能有效地追加在文件的尾部。放，新產(chǎn)生的記錄行能有效地追加在文件的尾部。 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu) 堆文件 優(yōu)點優(yōu)點 實現(xiàn)簡單，不需要特殊處理。實現(xiàn)簡單，不需要特殊處

31、理。 適用于對表的查詢涉及所有行，且行的訪問順序并適用于對表的查詢涉及所有行，且行的訪問順序并不重要的訪問。不重要的訪問。 缺點缺點 查詢效率低，對常見的兩類查詢（等值查詢和范圍查詢效率低，對常見的兩類查詢（等值查詢和范圍查詢）無任何優(yōu)勢。查詢）無任何優(yōu)勢。 刪除操作只是加一個刪除標(biāo)記，導(dǎo)致存儲空間的浪刪除操作只是加一個刪除標(biāo)記，導(dǎo)致存儲空間的浪費，搜索時間變長。費，搜索時間變長。 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu) 堆文件 用用F表示一個文件所占的磁盤塊數(shù)，插入、刪除和查表示一個文件所占的磁盤塊數(shù)，插入、刪除和查詢的平均磁盤詢的平均磁盤I/O次數(shù)為次數(shù)

32、為F/2。若表中沒有相同的記錄。若表中沒有相同的記錄存在，需要磁盤存在，需要磁盤I/O次數(shù)將是次數(shù)將是F。 【例】設(shè)一個關(guān)系有106個元組，在每個磁盤塊中可存放10個這樣的元組記錄，則該關(guān)系大約占用105個磁盤塊。 若該關(guān)系中的元組構(gòu)成了一個堆文件，進行記錄定位所若該關(guān)系中的元組構(gòu)成了一個堆文件，進行記錄定位所需要的磁盤需要的磁盤I/O次數(shù)為：次數(shù)為： 105 /2或或 105第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu) 順序文件 按關(guān)系中某些屬性值的排序順序存儲記錄的文按關(guān)系中某些屬性值的排序順序存儲記錄的文件稱為順序文件，排序所基于的屬性稱為排序件稱為順序文件

33、，排序所基于的屬性稱為排序?qū)傩裕ㄗ侄危傩裕ㄗ侄危?。關(guān)系表S按屬性SNO進行順序存儲 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu) 順序文件 優(yōu)點優(yōu)點 如果查找條件是基于排序?qū)傩缘闹担蓪Υ疟P文件如果查找條件是基于排序?qū)傩缘闹?，可對磁盤文件進行二分查找，得到比線性查找更快的存取速度。進行二分查找，得到比線性查找更快的存取速度。假設(shè)文件共有假設(shè)文件共有F塊，二分查找一般只需存取塊，二分查找一般只需存取log2F 。 如果查找屬性與排序?qū)傩韵嗤?，則可高效地完成等如果查找屬性與排序?qū)傩韵嗤?，則可高效地完成等值查詢和范圍查詢。值查詢和范圍查詢。第第14講講 數(shù)據(jù)庫的存儲

34、管理數(shù)據(jù)庫的存儲管理 【例例】設(shè)一個關(guān)系有設(shè)一個關(guān)系有106個元組，在每個磁盤塊中個元組，在每個磁盤塊中可存放可存放10個這樣的元組，則該關(guān)系大約占用個這樣的元組，則該關(guān)系大約占用105個磁盤塊。個磁盤塊。 若該關(guān)系中的元組已經(jīng)按照主鍵值從小到大的若該關(guān)系中的元組已經(jīng)按照主鍵值從小到大的順序構(gòu)成了一個順序文件。順序構(gòu)成了一個順序文件。 按照一個主鍵值進行記錄定位所需要的磁盤按照一個主鍵值進行記錄定位所需要的磁盤I/O次數(shù)為：次數(shù)為： log2105 16.6 17 順序文件文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu)第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu) 順序文件 缺點缺點

35、 插入和刪除操作要保持插入和刪除操作要保持記錄的存儲是有序的記錄的存儲是有序的，代價很大。，代價很大。 在塊中滑動記錄以在合適的地點得到所需的空間，將新記在塊中滑動記錄以在合適的地點得到所需的空間，將新記錄插入到塊中，并在此塊的偏移量表中添加指向此記錄的錄插入到塊中，并在此塊的偏移量表中添加指向此記錄的新指針。如果塊中沒有空間用于新記錄的存儲，可能就要新指針。如果塊中沒有空間用于新記錄的存儲，可能就要到到“鄰近塊鄰近塊”中找空間或創(chuàng)建一個溢出塊。如果要刪除一中找空間或創(chuàng)建一個溢出塊。如果要刪除一個記錄，則執(zhí)行相反的操作，回收記錄空間，記錄在塊中個記錄，則執(zhí)行相反的操作，回收記錄空間，記錄在塊中

36、滑動，讓塊中間總有一個未用的區(qū)域?；瑒?，讓塊中間總有一個未用的區(qū)域。 不能滑動記錄，則需要在塊首部維護一個可用空間列表，不能滑動記錄，則需要在塊首部維護一個可用空間列表，當(dāng)向塊中插入一條新記錄時，可知道可用區(qū)域在哪里。刪當(dāng)向塊中插入一條新記錄時，可知道可用區(qū)域在哪里。刪除記錄時，通常的方法是在記錄處放一個刪除標(biāo)記，并一除記錄時，通常的方法是在記錄處放一個刪除標(biāo)記，并一直保留到對整個數(shù)據(jù)庫進行重構(gòu)。直保留到對整個數(shù)據(jù)庫進行重構(gòu)。 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu) 順序文件 缺點缺點 插入和刪除操作要保持插入和刪除操作要保持記錄的存儲是有序的記錄的存儲是有

37、序的，代價，代價很大。很大。在文件中，為每個記錄增加一個指針字段，根據(jù)在文件中，為每個記錄增加一個指針字段，根據(jù)屬性值的大小用指針把記錄連接起來。屬性值的大小用指針把記錄連接起來。 對于刪除操作，可通過修改指針實現(xiàn)。而將被刪記錄對于刪除操作，可通過修改指針實現(xiàn)。而將被刪記錄鏈接成一個自由空間，以便插入新記錄時使用。鏈接成一個自由空間，以便插入新記錄時使用。 對于插入操作，在指針鏈中找到插入的位置（應(yīng)插到對于插入操作，在指針鏈中找到插入的位置（應(yīng)插到哪個記錄的前面），在找到記錄的塊內(nèi)，如果有自由哪個記錄的前面），在找到記錄的塊內(nèi)，如果有自由空間，那么就在該位置插入新記錄，并加入到指針鏈空間，那么

38、就在該位置插入新記錄，并加入到指針鏈中；如果無自由空間，那么就只能插入到溢出塊中。中；如果無自由空間，那么就只能插入到溢出塊中。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu) 順序文件 順序文件初始建立時，一般存儲記錄的物理順順序文件初始建立時，一般存儲記錄的物理順序和排序鍵值的順序一致，以便訪問數(shù)據(jù)時減序和排序鍵值的順序一致，以便訪問數(shù)據(jù)時減少對磁盤塊的操作次數(shù)。少對磁盤塊的操作次數(shù)。 多次插入和刪除操作后，很難維持這種一致的多次插入和刪除操作后，很難維持這種一致的狀態(tài)。此時應(yīng)該對文件重組，使其物理順序和狀態(tài)。此時應(yīng)該對文件重組，使其物理順序和排序鍵值的順序一致，

39、以提高查找速度。排序鍵值的順序一致，以提高查找速度。 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu) 聚集文件 聚集，又稱聚簇（聚集，又稱聚簇（cluster）。）。 文件中元組緊縮到能存儲這些元組的盡可能少文件中元組緊縮到能存儲這些元組的盡可能少的塊中。通常聚集文件把某個或某些屬性（稱的塊中。通常聚集文件把某個或某些屬性（稱為聚集碼，為聚集碼，cluster key）上具有相同值的元組）上具有相同值的元組集中存放在連續(xù)的物理塊中。集中存放在連續(xù)的物理塊中。 聚集功能可以大大提高按聚集碼進行查詢的效聚集功能可以大大提高按聚集碼進行查詢的效率。率。 第第14講講 數(shù)據(jù)

40、庫的存儲管理數(shù)據(jù)庫的存儲管理文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu) 聚集文件 聚集功能不但適用于單個關(guān)系，也適用于經(jīng)常聚集功能不但適用于單個關(guān)系，也適用于經(jīng)常進行連接操作的多個關(guān)系。即把多個連接關(guān)系進行連接操作的多個關(guān)系。即把多個連接關(guān)系的元組按連接屬性值聚集存放（連接屬性為聚的元組按連接屬性值聚集存放（連接屬性為聚集碼），從而大大提高連接操作的效率。集碼），從而大大提高連接操作的效率。SELECT S.SNO，SN，CNO，GRADE FROM S，SC WHERE S.SNO=SC.SNO；第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu) 聚集文件第第14講講 數(shù)據(jù)庫的存儲

41、管理數(shù)據(jù)庫的存儲管理文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu) 散列文件 根據(jù)記錄的屬性值根據(jù)記錄的屬性值K（一般為主鍵（一般為主鍵)，使用一，使用一個散列函數(shù)個散列函數(shù)h（hash function，又稱哈希函，又稱哈希函數(shù)）計算得到的函數(shù)值數(shù)）計算得到的函數(shù)值h(K)確定確定記錄的地址記錄的地址，對記錄進行存儲和訪問。該屬性稱為散列，對記錄進行存儲和訪問。該屬性稱為散列鍵（或散列字段）。鍵（或散列字段）。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 散列文件 使用桶（使用桶（bucket）作為基本的存儲單位，桶可）作為基本的存儲單位，桶可以是磁盤中的塊，也可以是比較大的空間。以是磁盤中的塊，也可以是比

42、較大的空間。文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu)H(Ki)H(Ki)H(Ki)一個桶中存放散一個桶中存放散列函數(shù)值相同的列函數(shù)值相同的多個記錄多個記錄桶內(nèi)記錄的散列鍵桶內(nèi)記錄的散列鍵值可能是不相同的值可能是不相同的第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu) 散列文件 優(yōu)點優(yōu)點 根據(jù)散列鍵值可以直接得到記錄的磁盤塊地址，根據(jù)散列鍵值可以直接得到記錄的磁盤塊地址，I/O操作次數(shù)少，訪問性能很高。操作次數(shù)少，訪問性能很高。 如果絕大多數(shù)桶都只由單個塊組成，那么一般的查如果絕大多數(shù)桶都只由單個塊組成，那么一般的查詢只需一次磁盤詢只需一次磁盤I/O，文件的插入和刪除也只需要兩，文

43、件的插入和刪除也只需要兩次磁盤次磁盤I/O。 缺點缺點 只適用于按散列鍵訪問記錄。只適用于按散列鍵訪問記錄。 存在地址沖突問題。存在地址沖突問題。 在實際應(yīng)用中，記錄在散列鍵值上的分布往往是不在實際應(yīng)用中，記錄在散列鍵值上的分布往往是不均衡的，在某些桶中存在空間浪費現(xiàn)象，而在另外均衡的，在某些桶中存在空間浪費現(xiàn)象，而在另外一些桶中則存在空間溢出問題。一些桶中則存在空間溢出問題。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理 數(shù)據(jù)庫存儲管理的數(shù)據(jù) 磁盤上數(shù)據(jù)的存儲 文件的組織結(jié)構(gòu) 文件的存儲結(jié)構(gòu) 索引文件的概念第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件

44、的概念索引文件的概念 索引的概念 關(guān)系數(shù)據(jù)文件中某屬性（組）上的索引是一關(guān)系數(shù)據(jù)文件中某屬性（組）上的索引是一種種數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)，它提供了在，它提供了在該屬性（組）上該屬性（組）上快快速查找具有某個特定值的元組的方法。速查找具有某個特定值的元組的方法。 索引可以建立在記錄的某一屬性或者屬性組索引可以建立在記錄的某一屬性或者屬性組上，這個屬性或者屬性組就被稱為上，這個屬性或者屬性組就被稱為索引鍵索引鍵。 針對某個屬性建立索引，就是根據(jù)此屬性值針對某個屬性建立索引，就是根據(jù)此屬性值將記錄進行將記錄進行邏輯排序邏輯排序（有序索引）。（有序索引）。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文

45、件的概念索引文件的概念 索引的概念 索引結(jié)構(gòu)可以存儲在一個單獨的文件中，索引結(jié)構(gòu)可以存儲在一個單獨的文件中，該文件稱為索引文件。該文件稱為索引文件。 存放記錄的索引鍵值以及指向記錄本身的指針存放記錄的索引鍵值以及指向記錄本身的指針(記錄的存儲地址記錄的存儲地址)，并且按照索引鍵值的順序，并且按照索引鍵值的順序進行排序。進行排序。 索引文件的每一條記錄被稱為索引文件的每一條記錄被稱為索引項索引項，索引項，索引項是一個索引鍵值和一個記錄指針構(gòu)成的鍵是一個索引鍵值和一個記錄指針構(gòu)成的鍵-指指針對針對 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 索引的作用 使用索引可以

46、明顯加快數(shù)據(jù)查詢的速度。使用索引可以明顯加快數(shù)據(jù)查詢的速度。 索引記錄中只含有索引鍵值和地址指針，索引文件索引記錄中只含有索引鍵值和地址指針，索引文件所占磁盤塊數(shù)量通常比數(shù)據(jù)文件的少，一般可一次所占磁盤塊數(shù)量通常比數(shù)據(jù)文件的少，一般可一次讀入內(nèi)存。讀入內(nèi)存。 索引項是經(jīng)過排序的，可以使用二分查找法來查找索引項是經(jīng)過排序的，可以使用二分查找法來查找索引鍵值所在記錄。索引鍵值所在記錄。 通過索引可以大大減少了對磁盤的通過索引可以大大減少了對磁盤的I/O操作次數(shù)，節(jié)操作次數(shù)，節(jié)約處理查詢的時間，加快查詢速度。約處理查詢的時間，加快查詢速度。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念

47、索引文件的概念 索引的概念 【例例】 考慮在例考慮在例4-1中的中的“學(xué)生學(xué)生-課程課程”數(shù)據(jù)庫數(shù)據(jù)庫中進行如下查詢：中進行如下查詢：SELECT *FROM SWHERE SEX=女女 AND SD=計算機系計算機系；關(guān)系中可能存在關(guān)系中可能存在10000個學(xué)生元組，但只有大約個學(xué)生元組，但只有大約200人是計算機系的，其中女同學(xué)只有人是計算機系的，其中女同學(xué)只有50個左右。個左右。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 索引的概念 【例例】在例在例4-1中的中的“學(xué)生學(xué)生-課程課程”數(shù)據(jù)庫中增加數(shù)據(jù)庫中增加一個專業(yè)系的關(guān)系模式一個專業(yè)系的關(guān)系模式D（DN

48、，DD），其中），其中DN為專業(yè)系名稱，為專業(yè)系名稱，DD為系主任姓名。對于如為系主任姓名。對于如下查詢下查詢SELECT DDFROM S，DWHERE SNO=s06 AND S.SD=D.DN； 查詢要求找出學(xué)號為查詢要求找出學(xué)號為“s06”的學(xué)生所在系主的學(xué)生所在系主任的名字。任的名字。 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 索引的分類 聚集索引和非聚集索引聚集索引和非聚集索引 稠密索引和稀疏索引稠密索引和稀疏索引 多級索引多級索引第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 聚集索引和非聚集索引 如果在數(shù)據(jù)文件的相同

49、的屬性或?qū)傩越M上，索如果在數(shù)據(jù)文件的相同的屬性或?qū)傩越M上，索引記錄和數(shù)據(jù)記錄都是有序的，則稱該有序索引記錄和數(shù)據(jù)記錄都是有序的，則稱該有序索引為引為聚集索引聚集索引（聚簇索引，（聚簇索引，Clustered Index），否則就稱之為），否則就稱之為非聚集索引非聚集索引（非聚簇索引，（非聚簇索引，Unclustered Index）。）。 “聚集索引聚集索引”的建立會使數(shù)據(jù)文件中記錄的物的建立會使數(shù)據(jù)文件中記錄的物理順序與索引記錄的排列順序一致。理順序與索引記錄的排列順序一致。 數(shù)據(jù)文件最多只能在數(shù)據(jù)文件最多只能在一個排序鍵一個排序鍵上排序，上排序，最多最多只有只有一個聚集索引，聚集索引通常又

50、稱做一個聚集索引，聚集索引通常又稱做主索主索引引，非聚集索引通常稱做，非聚集索引通常稱做輔助索引輔助索引（或次索引（或次索引）。）。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 聚集索引和非聚集索引聚集索引 非聚集索引 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 聚簇索引和非聚簇索引 在聚簇索引中，在聚簇索引中， 物理位置上相近的索引項在一定物理位置上相近的索引項在一定程度上預(yù)示相應(yīng)數(shù)據(jù)記錄的索引鍵值也很近。程度上預(yù)示相應(yīng)數(shù)據(jù)記錄的索引鍵值也很近。 可加快按某屬性列進行范圍查詢的效率?？杉涌彀茨硨傩粤羞M行范圍查詢的效率?！纠恳粋€

51、數(shù)據(jù)文件可能存儲在一個數(shù)據(jù)文件可能存儲在10000個磁盤塊上，但對一個特定的查詢個磁盤塊上，但對一個特定的查詢（等值查詢或范圍查詢）來說，只有（等值查詢或范圍查詢）來說，只有100條記錄滿足條件。條記錄滿足條件。如果數(shù)據(jù)存儲在如果數(shù)據(jù)存儲在沒有索引文件的堆文件沒有索引文件的堆文件中，可能需要中，可能需要1000010000次次I/OI/O操作；操作；如果在這個查詢的如果在這個查詢的WHERE WHERE 子句的查找屬性上有一個子句的查找屬性上有一個非聚集索引非聚集索引是可用的，那么檢是可用的，那么檢索這個數(shù)據(jù)文件最多只需要索這個數(shù)據(jù)文件最多只需要100100次次I/OI/O操作。操作。如果在查

52、找屬性上有一個如果在查找屬性上有一個聚集索引聚集索引是可用的，且每個磁盤塊平均包含是可用的，且每個磁盤塊平均包含2020條數(shù)據(jù)記條數(shù)據(jù)記錄，可能只需要錄，可能只需要5 5次次I/OI/O操作，檢索操作，檢索5 5個磁盤塊。個磁盤塊。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 聚簇索引和非聚簇索引 某些數(shù)據(jù)庫系統(tǒng)中聚簇索引總是與數(shù)據(jù)文件集某些數(shù)據(jù)庫系統(tǒng)中聚簇索引總是與數(shù)據(jù)文件集成為一種存儲結(jié)構(gòu)。成為一種存儲結(jié)構(gòu)。 索引項包含數(shù)據(jù)記錄，由語句索引項包含數(shù)據(jù)記錄，由語句CREATE TABLE創(chuàng)建創(chuàng)建表時同時創(chuàng)建。表時同時創(chuàng)建。 非聚簇索引存儲在一個單獨的文件中，由語

53、句非聚簇索引存儲在一個單獨的文件中，由語句CREATE INDEX來創(chuàng)建。來創(chuàng)建。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 聚簇索引和非聚簇索引 定義基本表同時創(chuàng)建索引的語句格式為定義基本表同時創(chuàng)建索引的語句格式為 CREATE TABLE( |AS ,) PRIMARY KEY CLUSTERED|NON CLUSTERED 定義該屬性列為主鍵并建立聚簇或非聚簇索引。定義該屬性列為主鍵并建立聚簇或非聚簇索引。 PRIMARY KEY CLUSTERED |NONCLUSTERED () 定義定義為表為表的主鍵并建立聚簇或非聚簇索引。的主鍵并建立聚簇或非聚簇索

54、引。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 聚簇索引和非聚簇索引 建立索引的語句格式建立索引的語句格式CREATE UNIQUE CLUSTERDE INDEX ON (,.) 其他參數(shù)其他參數(shù); UNIQUE表示該索引的每一索引值只對應(yīng)唯一的數(shù)據(jù)記錄。表示該索引的每一索引值只對應(yīng)唯一的數(shù)據(jù)記錄。 CLUSTER表示要建立的索引是聚簇索引。表示要建立的索引是聚簇索引。 “其他參數(shù)其他參數(shù)”是與物理存儲有關(guān)的參數(shù)。是與物理存儲有關(guān)的參數(shù)。 PAD-INDEX：為每一內(nèi)部結(jié)點頁指定分配空間大小。：為每一內(nèi)部結(jié)點頁指定分配空間大小。 FILEFACTOR=:指定葉

55、子數(shù)和索引的充滿度。指定葉子數(shù)和索引的充滿度。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 聚簇索引和非聚簇索引第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 聚簇索引和非聚簇索引第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 稠密索引和稀疏索引 按照索引對數(shù)據(jù)庫記錄的覆蓋程度按照索引對數(shù)據(jù)庫記錄的覆蓋程度 稠密索引（稠密索引（Dense Indices） 稀疏索引（稀疏索引（Sparse Indices）第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 稠密索引和稀疏索引 稠密索引

56、的定義（一）稠密索引的定義（一） 索引鍵為數(shù)據(jù)文件的候選鍵，可為數(shù)據(jù)文件中的索引鍵為數(shù)據(jù)文件的候選鍵，可為數(shù)據(jù)文件中的每一條記錄建立一個索引記錄（索引項）。每一條記錄建立一個索引記錄（索引項）。 基于堆文件的候選鍵建立的稠密索引 （非聚集索引）基于候選鍵排序的順序文件上的稠密索引 （聚集索引）第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 稠密索引和稀疏索引 稠密索引的定義（二）稠密索引的定義（二） 索引鍵為數(shù)據(jù)文件的非候選鍵，且數(shù)據(jù)文件為索索引鍵為數(shù)據(jù)文件的非候選鍵，且數(shù)據(jù)文件為索引鍵上的順序文件，則為數(shù)據(jù)文件中具有相同索引鍵上的順序文件，則為數(shù)據(jù)文件中具有相同索

57、引鍵值的記錄建立一個索引記錄，索引記錄包括引鍵值的記錄建立一個索引記錄，索引記錄包括索引鍵值和指向具有該值的記錄鏈表中第一個記索引鍵值和指向具有該值的記錄鏈表中第一個記錄的指針。錄的指針?；诜呛蜻x鍵排序的順序文件上的稠密索引（聚集索引） 第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 稠密索引和稀疏索引 稠密索引的定義（三）稠密索引的定義（三） 索引鍵為數(shù)據(jù)文件的非候選鍵，且數(shù)據(jù)文件為非索引鍵為數(shù)據(jù)文件的非候選鍵，且數(shù)據(jù)文件為非順序文件（堆文件），或數(shù)據(jù)文件中記錄順序由順序文件（堆文件），或數(shù)據(jù)文件中記錄順序由其他屬性上主索引確定的，而不是按輔助索引的其他屬性上主

58、索引確定的，而不是按輔助索引的索引鍵順序物理存儲的，因此索引文件中要存放索引鍵順序物理存儲的，因此索引文件中要存放指向數(shù)據(jù)文件中具有該索引鍵值的所有記錄的指指向數(shù)據(jù)文件中具有該索引鍵值的所有記錄的指針。針。基于堆文件的非候選鍵建立的稠密索引 （輔助索引）第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 稠密索引和稀疏索引 稠密索引的定義（三）稠密索引的定義（三） 通過在稠密索引和數(shù)據(jù)文件之間加一個記錄指針通過在稠密索引和數(shù)據(jù)文件之間加一個記錄指針桶（桶（bucket）來節(jié)省存儲空間）來節(jié)省存儲空間 。 可以在不訪問數(shù)據(jù)文件記錄的前提下利用桶的指針來幫助回答一些查詢和減

59、少一些I/O開銷。 比如，當(dāng)查詢有多個條件，而每個條件都有一個可用的輔助索引時，可通過在主存中將指針集合求交來找到滿足所有條件的指針，然后只需要檢索交集中指針指向的記錄。第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 稠密索引和稀疏索引 稀疏索引的定義稀疏索引的定義 對于順序數(shù)據(jù)文件，可以在索引文件中只為數(shù)據(jù)文對于順序數(shù)據(jù)文件，可以在索引文件中只為數(shù)據(jù)文件的每個磁盤塊設(shè)一個鍵件的每個磁盤塊設(shè)一個鍵-指針對，來記錄該磁盤塊指針對，來記錄該磁盤塊中第一條數(shù)據(jù)記錄的索引鍵值及該磁盤塊的首地址中第一條數(shù)據(jù)記錄的索引鍵值及該磁盤塊的首地址?；诤蜻x鍵排序的順序文件上的稀疏索引

60、（聚集索引） 基于非候選鍵排序的順序文件上的稀疏索引 （聚集索引）第第14講講 數(shù)據(jù)庫的存儲管理數(shù)據(jù)庫的存儲管理索引文件的概念索引文件的概念 稠密索引和稀疏索引 稀疏索引稀疏索引 稀疏索引必須是聚集的稀疏索引必須是聚集的有序文件才允許定位不被索引引用的記錄。有序文件才允許定位不被索引引用的記錄。 查找一條鍵值為查找一條鍵值為K的記錄，首先在索引文件中找到的記錄，首先在索引文件中找到索引鍵值小于等于索引鍵值小于等于K的索引項中索引鍵值最大的索的索引項中索引鍵值最大的索引項。然后根據(jù)這個索引項的指針找到記錄所在磁引項。然后根據(jù)這個索引項的指針找到記錄所在磁盤塊，在調(diào)入內(nèi)存的磁盤塊中進行搜索，以找到