1、第5章 數(shù)據(jù)庫的存儲結(jié)構(gòu)2009. 10Last update: Oct.20091Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論目錄 Contents5.1 數(shù)據(jù)庫存儲結(jié)構(gòu)多級存儲物理結(jié)構(gòu)邏輯結(jié)構(gòu)5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制索引散列簇集Last update: Oct.20092Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.1 數(shù)據(jù)庫存儲結(jié)構(gòu)一、多級存儲目前，用內(nèi)存作為數(shù)

2、據(jù)庫的存儲介質(zhì)是不合適的。內(nèi)存的容量尚不夠存儲全部的數(shù)據(jù)；內(nèi)存一般屬易失存儲器(Volatile Storage)，不適合用來存儲持久數(shù)據(jù)內(nèi)存存儲單位數(shù)據(jù)成本要比外存高得多因此，主要采用多級存儲器。二級存儲：內(nèi)存外存三級存儲Last update: Oct.20093Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.1 數(shù)據(jù)庫存儲結(jié)構(gòu)三級存儲結(jié)構(gòu)第一級：主存儲器 (main memory)高速緩沖存儲器 (cache)主存儲器 (memory)第二級：磁盤存儲器(secondary sto

3、rage)也稱為：二級存儲器 或 次級存儲器。第三級：輔助存儲器(tertiary storage)磁帶存儲器自動光盤機是一種輔助存儲設(shè)備，也稱三級存儲器。Last update: Oct.20094Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.1 數(shù)據(jù)庫存儲結(jié)構(gòu)存儲容量訪問速度訪問類型存取單位第一級存儲器100MB10GB10-8秒10-7 秒隨機字節(jié)第二級存儲器10GB103GB10毫秒30 毫秒隨機物理塊第三級存儲器106GB幾秒鐘幾分鐘順序數(shù)據(jù)塊Last update: Oct

4、.20095Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.1 數(shù)據(jù)庫存儲結(jié)構(gòu)主存儲器磁盤存儲器輔助存儲器cachememorytapeCDdisk存儲容量小大訪問速度快慢制造成本高低Last update: Oct.20096Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.1 數(shù)據(jù)庫存儲結(jié)構(gòu)磁盤的I/O操作：首先根據(jù)給出的物理塊地址定位，然后讀/寫指定磁盤塊上的數(shù)據(jù)，其存取時間開

5、銷包括：活動頭的移動時間尋道時間磁盤片的旋轉(zhuǎn)定位時間等待時間讀/寫數(shù)據(jù)時間傳輸時間物理塊是磁盤與內(nèi)存進行數(shù)據(jù)交換的基本單位，因此物理塊的大小是設(shè)計DBMS的重要參數(shù)。Last update: Oct.20097Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.1 數(shù)據(jù)庫存儲結(jié)構(gòu)磁盤的存取速度與內(nèi)存的存取速度不匹配，為了有效地支持數(shù)據(jù)庫的數(shù)據(jù)讀寫、提高數(shù)據(jù)庫性能。為此， DBMS必須在內(nèi)存開辟若干大小等于物理塊的緩沖塊或緩沖區(qū)(Buffers)，并采用數(shù)據(jù)預取(Prefetching)和延時

6、寫(Delayed Writing)技術(shù)，減少 I/O操作。即使外存（通常是硬盤）是非易失存儲器，當系統(tǒng)（包括：OS、數(shù)據(jù)庫系統(tǒng)本身、存儲介質(zhì)等）發(fā)生故障時，數(shù)據(jù)庫不可避免地會遭受破壞，因此DBMS必須提供數(shù)據(jù)后備 (Backuping)功能。 Last update: Oct.20098Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.1 數(shù)據(jù)庫存儲結(jié)構(gòu)二、物理結(jié)構(gòu)數(shù)據(jù)庫以多個文件(Files)的形式進行組織，并物理地存儲于硬盤介質(zhì)上。存儲空間及文件由DBMS的存儲管理器進行管理。(OS

7、的存儲管理和文件系統(tǒng)可為DBMS提供底層支持)。通常，一個數(shù)據(jù)庫有三種文件：數(shù)據(jù)文件(Data Files)：用于存儲數(shù)據(jù)庫中的數(shù)據(jù)與元數(shù)據(jù)，一個數(shù)據(jù)庫對應(yīng)一個或多個數(shù)據(jù)文件。日志文件(Log Files)：用于保存用戶存取數(shù)據(jù)庫的日志記錄，一個數(shù)據(jù)庫對應(yīng)一個或多個日志文件?？刂莆募?Control Files)：用于保存與數(shù)據(jù)庫有關(guān)的若干參數(shù)(如：數(shù)據(jù)庫名、數(shù)據(jù)庫數(shù)據(jù)文件和日志文件的名字和位置，數(shù)據(jù)庫的建立日期等)，一個數(shù)據(jù)庫對應(yīng)一個控制文件。Last update: Oct.20099Lecture Notes - Principles of Databases Systems. By Z

8、huoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.1 數(shù)據(jù)庫存儲結(jié)構(gòu)SGADB Buffer CacheLog BufferControl FileData FileData FileData FilesData FileLog FilesDelayed writingPrefetchingLog writingBackuping外存內(nèi)存Last update: Oct.200910Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.1 數(shù)據(jù)庫存儲結(jié)構(gòu)三、邏輯結(jié)構(gòu)數(shù)據(jù)庫用戶并非直接與數(shù)據(jù)庫的

9、物理結(jié)構(gòu)(物理存儲介質(zhì)或物理文件)打交道，DBMS的存儲管理器提供了物理邏輯的映像(Mapping)，使得用戶直接面對數(shù)據(jù)庫的邏輯結(jié)構(gòu)。邏輯結(jié)構(gòu)涉及兩個方面：數(shù)據(jù)庫的存儲空間如何邏輯地劃分與組織（即邏輯存儲空間）；用戶如何使用數(shù)據(jù)庫的數(shù)據(jù)（即用戶模式及其對象）。Last update: Oct.200911Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.1 數(shù)據(jù)庫存儲結(jié)構(gòu)三、邏輯結(jié)構(gòu)(cont.)邏輯存儲空間：（以O(shè)racle為例介紹）表空間(Table Space)：數(shù)據(jù)庫的邏輯存儲單

10、位。一個數(shù)據(jù)庫可包含一個或多個表空間；一個表空間可跨越多個磁盤分配。一般地，在數(shù)據(jù)庫初始化時，系統(tǒng)總是自動建立一個缺省表空間(如Oracle中的SYSTEM表空間)，DBA事后可定義其他表空間。段(Segment)：表空間中一種指定類型的邏輯存儲結(jié)構(gòu)。有：數(shù)據(jù)段：每個表/簇集有一個數(shù)據(jù)段，用于存儲其中的數(shù)據(jù)。索引段：每個索引有一個索引段，用于存儲索引數(shù)據(jù)?；貪L段：由DBA建立，用于臨時存儲要回滾（撤消）的信息，以便事務(wù)回滾。臨時段：當一個SQL語句需要臨時工作區(qū)時，由DBMS建立，用完后再回收。范圍(Extent)：一個段由一組范圍組成，范圍是數(shù)據(jù)庫存儲空間分配的邏輯單位。數(shù)據(jù)塊(Data B

11、lock)：一個范圍由一組連續(xù)的數(shù)據(jù)塊所組成，數(shù)據(jù)塊是DBMS進行I/O的最小物理單位，其大小可不同于OS的標準I/O塊大小。Last update: Oct.200912Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.1 數(shù)據(jù)庫存儲結(jié)構(gòu)的特點三、邏輯結(jié)構(gòu)(cont.)用戶模式及其對象模式(Schema): 每個數(shù)據(jù)庫用戶對應(yīng)一個模式。模式對象(Schema Objects): 一個模式中包含的數(shù)據(jù)邏輯結(jié)構(gòu)對象。如：表，視圖，索引，簇集，過程、觸發(fā)器等。Last update: Oct.

12、200913Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.1 數(shù)據(jù)庫存儲結(jié)構(gòu)的特點ClusterTableTableIndexTableIndexTableTableTableTableClusterTableTableIndexTableIndexTableClusterTable Tablesapce SYSTEM Tablespace TS1 Tablespace TS2DDDataFile1DataFile2DataFile3DataFile4Database ABCDisk

13、1Disk 2Disk 3User1s SchemaUser2s SchemaUser3s SchemaLast update: Oct.200914Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論目錄 Contents5.1 數(shù)據(jù)庫存儲結(jié)構(gòu)多級存儲物理結(jié)構(gòu)邏輯結(jié)構(gòu)5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制索引散列簇集Last update: Oct.200915Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分

14、 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引在數(shù)據(jù)庫中數(shù)據(jù)查找的速度是至關(guān)重要的，但是當數(shù)據(jù)庫中數(shù)據(jù)量增大時，數(shù)據(jù)查找速度就會受到影響，當數(shù)據(jù)量極大時，查找速度將會受到嚴重影響，為解決此問題需引入索引、散列和簇集技術(shù)。索引（Index）是與表或簇集相關(guān)的一種可選存儲機制，其通過一棵有序樹（如B樹）將索引鍵（Index Key, IK）值與數(shù)據(jù)塊（的地址）建立聯(lián)系，以提高數(shù)據(jù)檢索性能。 Last update: Oct.200916Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論

15、5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引一、順序文件按照某個屬性(項)的取值進行排序而構(gòu)成的數(shù)據(jù)文件被稱為順序文件。例（假設(shè)每個物理塊可以存放2條記錄）Last update: Oct.200917Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引例1設(shè)一個關(guān)系有106個元組，在每個物理塊(大小為4KB)中可存放10個這樣的元組，則該關(guān)系大約占用： 105個磁盤塊（約400MB）設(shè)該關(guān)系中的元組已經(jīng)按照主鍵值從小到大的順序構(gòu)成了一個順序文件，因此可以

16、采用二分查找法來根據(jù)主鍵值進行記錄定位。按照一個主鍵的值進行記錄定位所需要的磁盤I/O次數(shù)為： log2105 16.6 17Last update: Oct.200918Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引二、索引文件建立索引文件的目的：以一個或多個字段的索引鍵的值為輸入，能夠快速地找出具有該索引鍵值的記錄。利用索引文件進行記錄查找的過程：首先在索引文件中按照索引鍵的值進行查找，找出具有該索引鍵值的記錄指針（即記錄在數(shù)據(jù)文件中的存儲地址

17、），從而可以在數(shù)據(jù)文件中進行直接定位，讀出所需要的記錄。通過建立索引文件可以大大提高在數(shù)據(jù)文件上的記錄查找定位速度。Last update: Oct.200919Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引索引文件的大小一般都大大小于數(shù)據(jù)文件的大小。索引文件主要用于記錄的快速定位操作，在索引文件中一般只含有索引屬性上索引鍵(Index Key, IK)的值和記錄的地址(指針)。如：索引文件采用便于查找的特殊組織結(jié)構(gòu)(如B或B+樹)。在不同類型的數(shù)

18、據(jù)文件上可以建立不同的索引文件。索引鍵值1對應(yīng)記錄1的指針索引鍵值2對應(yīng)記錄2的指針索引鍵值3對應(yīng)記錄3的指針Last update: Oct.200920Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引索引鍵如是PK或UNIQUE列，稱主索引(Primary Index)，否則稱次索引(Secondary Index)。主索引由于沒有兩行在索引鍵上具有重復值，故也稱唯一索引(Unique Index)。一般地，唯一索引由DBMS自動建立，而非唯一索

19、引則需由DBA/用戶自己顯式地建立。索引鍵可以是列組，此時稱組合索引(Composite Index)。若每個索引鍵值均有對應(yīng)的索引項(Index Entry)，稱這樣的索引結(jié)構(gòu)為稠密索引(Dense Index)，否則稱非稠密索引。Last update: Oct.200921Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引三、在順序文件上的索引稠密索引非稠密索引多級索引在討論上述的三種索引文件時，我們假設(shè)其索引鍵值具有唯一性（主索引）。Last

20、update: Oct.200922Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引稠密索引(dense index)索引文件存放記錄的索引鍵值以及指向記錄本身的指針(記錄的存儲地址)，并且按照索引鍵值的順序進行排序。一個索引鍵值和一個記錄指針構(gòu)成的鍵-指針對，稱為一個索引項:稠密索引若每個索引鍵值均有對應(yīng)的索引項(Index Entry)，稱這樣的索引結(jié)構(gòu)為稠密索引。例如：索引鍵值K記錄指針PLast update: Oct.200923Lectu

21、re Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引S#SNSDSAS1LUCS18S2LICS17S3XUMA18S4LOCS18S5LINPH19S6WANGCS17S7SENMA17S8EHENPH18S#指針S1S2S3S4S5S6S7S8數(shù)據(jù)文件稠密索引Last update: Oct.200924Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論利用稠

22、密索引進行數(shù)據(jù)查找要比直接在數(shù)據(jù)文件上進行數(shù)據(jù)查找的速度快。其原因是：索引文件使用的物理塊比數(shù)據(jù)文件的少，因此磁盤I/O的時間開銷小。一般情況下，一個物理塊中可以存放的索引項的個數(shù)要遠遠大于可以存放的記錄數(shù)。索引文件中的索引項被按照索引鍵值進行了排序，因此在索引文件中可采用二分查找法來提高查找速度。這在無序的數(shù)據(jù)文件(堆文件)中是無法做到的。索引文件可能足夠小，可以放在內(nèi)存中操作，從而不必訪問磁盤。5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引Last update: Oct.200925Lecture Notes - Principles of Databases Systems. By Zhu

23、oming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引利用稠密索引查找關(guān)鍵字值為K的記錄的算法如下：采用二分查找法在索引文件中查找是否存在索引鍵值為K的索引項；如果不存在相關(guān)的索引項，則表示主鍵值為K的記錄不存在，查找失敗。否則：根據(jù)找到的索引項中的記錄指針到數(shù)據(jù)文件中進行直接定位，讀取相應(yīng)的記錄。Last update: Oct.200926Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引例2為例1中的順序數(shù)據(jù)文件建立

24、一個稠密索引。假設(shè)每個磁盤塊可以存放100個索引項，則該稠密索引共有106個索引項，需要占用：104個磁盤塊（約40MB）利用該稠密索引進行記錄定位需要的磁盤I/O次數(shù)為：log2104 + 1 13.3 + 1 15其中的1是訪問數(shù)據(jù)文件的磁盤I/O。Last update: Oct.200927Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引非稠密索引(nondense index)如果數(shù)據(jù)文件是順序文件，我們可以在索引文件中只為數(shù)據(jù)文件的每個物

25、理塊設(shè)一個索引項，記錄該物理塊中第一條數(shù)據(jù)記錄的索引鍵值及該物理塊的首地址。這樣建立起來的索引文件被稱為非稠密索引。Last update: Oct.200928Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引數(shù)據(jù)文件非稠密索引Last update: Oct.200929Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型

26、存儲機制一索引利用非稠密索引查找關(guān)鍵字值為K的記錄的算法如下：采用二分查找法在索引文件中查找索引鍵值小于或等于K，且最接近K的索引項；如果不存在相關(guān)的索引項，則表示主鍵值為K的記錄不存在(所有記錄的索引鍵值均大于K)，查找失敗。否則：根據(jù)找到的索引項中的記錄指針到數(shù)據(jù)文件中讀取相應(yīng)的物理塊 D；在物理塊 D 中利用二分查找法查找主鍵值為K的記錄。數(shù)據(jù)文件是順序文件。Last update: Oct.200930Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機

27、制一索引例3為例1中的順序數(shù)據(jù)文件再建立一個非稠密索引。由于該數(shù)據(jù)文件共占用105個磁盤塊，因此非稠密索引文件中有105個索引項，需要占用：103個磁盤塊（約4MB）利用該非稠密索引進行記錄定位需要的磁盤I/O次數(shù)為： log2103 + 1 9.97 + 1 11Last update: Oct.200931Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引稠密索引與稀疏索引的區(qū)別索引文件的定義不同非稠密索引只能用于順序文件上的索引組織。稠密索引中的

28、每個索引項對應(yīng)數(shù)據(jù)文件中的一條記錄，而非稠密索引中的每個索引項則對應(yīng)數(shù)據(jù)文件中的一個物理塊。需要的磁盤空間大小不同在記錄的查找定位功能上存在差別：稠密索引：可以直接回答是否存在鍵值為K的記錄。非稠密索引：需要額外的磁盤I/O操作，即需要將相應(yīng)的數(shù)據(jù)文件中的磁盤塊讀入內(nèi)存后才能判別該記錄是否存在。Last update: Oct.200932Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引多級索引索引文件本身也可能占據(jù)多個存儲塊，為了能夠快速找到這些索

29、引塊在磁盤中的存儲位置，需要引入新的索引結(jié)構(gòu)，即在索引文件上再建立索引，從而構(gòu)成了多級索引。由于索引文件本身是順序文件，因此索引文件上的索引結(jié)構(gòu)采用的是非稠密索引。將直接建立在數(shù)據(jù)文件上的索引（例2、例3中建立的索引）稱為第一級索引，根據(jù)第一級索引文件建立的索引稱為第二級索引，依此類推，從而可以建立一個多級索引結(jié)構(gòu)。在多級索引組織結(jié)構(gòu)中，第一級索引可以是稠密索引，也可以是非稠密索引。從第二級索引開始建立的都是非稠密索引。Last update: Oct.200933Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第

30、1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引數(shù)據(jù)文件（順序文件）第1級 稠密索引第2級 非稠密索引Last update: Oct.200934Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引數(shù)據(jù)文件（堆文件）第1級 稠密索引第2級 非稠密索引Last update: Oct.200935Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫

31、系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引數(shù)據(jù)文件（順序文件）第1級 非稠密索引第2級 非稠密索引Last update: Oct.200936Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引例4在例2中建立的稠密索引文件上再建立一個非稠密索引。由于例2中的稠密索引文件共占用104個磁盤塊，因此新建立的非稠密索引文件中有104個索引項，需要占用100個物理塊（約400KB）例5在例3中建立的非稠密索引文件上也可以再建立一個非稠密索引。由于例3

32、中的非稠密索引文件共占用103個磁盤塊，因此新建立的非稠密索引文件中有103個索引項，只需要占用：10個物理塊（約40KB）Last update: Oct.200937Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引考慮在例4和例5中所建立的第二級索引文件，由于它們只分別占用400KB和40KB的存儲空間，這樣的索引文件完全可以全部放在內(nèi)存中。因此，在這樣的索引文件上進行搜索定位不需要索引文件上的磁盤I/O操作，我們只要根據(jù)在二級索引中查找到的索引

33、項到第一級索引文件中直接讀取相應(yīng)的索引磁盤塊，并根據(jù)在該物理塊中所找到的索引項到數(shù)據(jù)文件中直接讀取相應(yīng)的數(shù)據(jù)文件物理塊或記錄。因此，根據(jù)這樣的兩級索引結(jié)構(gòu)進行記錄的查找定位只需要2次磁盤I/O操作，大大低于我們在例2和例3中所需的磁盤I/O次數(shù)（見下表）。Last update: Oct.200938Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引索引類型需要的磁盤空間（包括數(shù)據(jù)文件和索引文件）記錄查找需要的磁盤I/O次數(shù)例1無索引，直接在順序數(shù)據(jù)文

34、件上進行記錄的查找10000017例2一級稠密索引11000015例3一級非稠密索引10100011例4基于一級稠密索引的二級索引1101002例5基于一級非稠密索引的二級索引1010102Last update: Oct.200939Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引四、非順序文件中的索引結(jié)構(gòu)在數(shù)據(jù)庫系統(tǒng)中所使用的數(shù)據(jù)文件通常都是無序的（堆文件組織），因此更加需要利用上述的索引結(jié)構(gòu)來建立非順序文件上的索引，以提高記錄查找的速度。如果索

35、引鍵值在非順序數(shù)據(jù)文件中具有唯一性，則可以按照下述步驟建立其上的索引文件：首先為非順序數(shù)據(jù)文件建立第一級的稠密索引；然后再根據(jù)需要建立該稠密索引上的多級非稠密索引。Last update: Oct.200940Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引在次索引中，索引鍵值不唯一，則可以通過在第一級的稠密索引和數(shù)據(jù)文件之間加一個記錄指針桶(bucket)。此時索引項(Ki,Pi)中的記錄指針Pi不再是指向數(shù)據(jù)文件中的記錄，而是指向一個記錄指針桶，

36、在桶中存放著索引鍵值為Ki的記錄的記錄指針。在這里，記錄指針桶的大小 BSize 是預先確定的。當在數(shù)據(jù)文件中插入第一條索引鍵值為 Ki 的記錄 Ri 時，在索引文件中將生成一個新的索引項(Ki,Pi)，同時系統(tǒng)將自動申請一個大小為 BSize 的記錄指針桶 Bi，將指針 Pi 指向該記錄指針桶 Bi，同時將當前記錄 Ri 的記錄指針保存在記錄指針桶 Bi 中。當新的索引鍵值為 Ki 的記錄被加入到數(shù)據(jù)文件中時，只需要將新記錄的記錄指針加入到記錄指針桶 Bi 中。如果記錄指針桶 Bi 已滿，系統(tǒng)將申請一個新的記錄指針桶，并鏈接到原來的記錄指針桶的后面。Last update: Oct.2009

37、41Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引S#SNSDSAS1LUCS18S2LICS17S3XUMA18S4LOCS18S5LIPH19S6WACS17S7SEMA17S8ENPH18索引鍵值不唯一，且數(shù)據(jù)文件沒有按照索引鍵值排序存儲稠密索引記錄指針桶Last update: Oct.200942Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫

38、系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引索引文件本身是一個順序文件，利用索引文件或多級索引可以大大提高數(shù)據(jù)文件的訪問效率。索引順序文件的不足記錄查找算法的效率不高（log2N）；在數(shù)據(jù)文件是非順序文件，或索引鍵值的變化比較頻繁的情況下，索引順序文件自身的維護非常復雜，對索引項的插入、修改和刪除操作會導致索引項在索引文件中的大量移動。在上述情況下，如果通過引入鏈接磁盤塊的方法來減少索引項的移動，又會減低存儲空間的利用率，并最終影響到系統(tǒng)的性能。因此需要引入適合于索引文件的存儲組織的文件結(jié)構(gòu)，這就是在數(shù)據(jù)庫系統(tǒng)中廣泛使用的多級索引技術(shù)：B/B+樹索引Last update: Oct.20

39、0943Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引五、B-treeB樹(B-tree)是一種動態(tài)平衡多分樹(Dynamic Balanced Multiway Tree)。B/B+樹是一種動態(tài)、多級索引組織方法，是適合于組織存放在外存的大型磁盤文件的一種樹狀索引結(jié)構(gòu)。其中用得比較多的是B+樹。B/B+樹的結(jié)點劃分葉結(jié)點：B/B+樹的最下一級索引是樹的葉結(jié)點內(nèi)部結(jié)點：B/B+樹中的其它結(jié)點(非葉結(jié)點)，其中：根結(jié)點：B/B+樹的最上一級索引是樹的

40、根結(jié)點在B/B+樹中，由葉結(jié)點所構(gòu)成的最下面的一級索引總采用稠密索引，而其它層次上的索引則采用非稠密索引。運用B樹的索引結(jié)構(gòu)總是動態(tài)索引。B樹的維護（即索引的維護）由DBMS進行，對用戶是透明的。Last update: Oct.200944Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引B+樹中的結(jié)點每個結(jié)點占用一個物理塊，每個結(jié)點能容納 n 個鍵和 n+1 個指針，將 n 取得盡可能的大，以便在一個物理塊中存放更多的索引項。例如：設(shè)每個物理塊的大

41、小是4096個字節(jié)，每個鍵值占4個字節(jié)，每個指針占8個字節(jié)，則滿足：4n + 8(n+1) 4096的最大 n 的值是340。B+樹的結(jié)點的結(jié)構(gòu)如下：P1K1P2K2PmKmPm+1Last update: Oct.200945Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引其中：K1,K2,Km是索引關(guān)鍵字值，且K1K2Km若是葉子結(jié)點，則：(n+1)/2 m n，P1,P2, Pm是指向數(shù)據(jù)記錄的指針，Pm+1是指向其右邊的下一個葉子結(jié)點的指針。

42、其中，Pi是指向關(guān)鍵字值為Ki的數(shù)據(jù)記錄（i=1,2,m）。若是根結(jié)點，則1 m n，否則(即內(nèi)部結(jié)點)：(n-1)/2 m n其中：P1,P2, Pm,Pm+1分別指向另一棵子樹的根結(jié)點。若是非葉結(jié)點，則：對P1所指向的子樹中的任意一個索引鍵K，都有K K1對Pm+1所指向的子樹中的任意一個索引鍵K，都有K Km對Pj所指向的子樹中的任意一個索引鍵K，都有Kj-1 K KjP1K1P2K2PmKmPm+1Last update: Oct.200946Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫

43、系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引例如：有一棵秩n=3的B+樹，則每個結(jié)點最多可放3個關(guān)鍵字和4個指針，每個葉子結(jié)點至少有2個關(guān)鍵字和3個指針，每個內(nèi)部結(jié)點至少有1個關(guān)鍵字和2個指針。Last update: Oct.200947Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引Last update: Oct.200948Lecture Notes - Principles of Databases Systems. By Zhuom

44、ing Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引例：設(shè)索引鍵值集為：5，10，13，14，18，31，33， 40，43，51，58，59，62，67，72，73，74，86則Oracle B*樹的索引結(jié)構(gòu)示意圖為： Last update: Oct.200949Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引S 3 5 ROWID 10 ROWID 13 ROWID14,18,3133,40,4351,58,5962

45、,67,7273,74,86I 2 13 31 I 2 59 72 I 1 43行數(shù)據(jù)ROWID行數(shù)據(jù)ROWID行數(shù)據(jù)ROWID行數(shù)據(jù)ROWID行數(shù)據(jù)行數(shù)據(jù)簇集索引主索引ROWIDsROWIDsROWIDs次索引索引集順序集索引段數(shù)據(jù)段Last update: Oct.200950Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引注：Oracle中的ROWID是16進制位串：. 數(shù)據(jù)文件號 數(shù)據(jù)塊中的行片號 數(shù)據(jù)塊在數(shù)據(jù)文件中的地址ROWID是系統(tǒng)附加

46、在表行上的偽列（Pseudo Columm）： SELECT * FROM emp WHERE ROWID = 0000DC5.0001.0001; SELECT ROWID, ename FROM emp WHERE empno=100;Last update: Oct.200951Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一索引利弊利當表的容量較大時（需占較多數(shù)據(jù)塊時），索引能明顯提高數(shù)據(jù)查詢性能。最理想的塊I/O次數(shù)為：B樹深度+1。索引特別適

47、合于指定行查詢和范圍查找。弊增加了系統(tǒng)維護的開銷，特別是當表的數(shù)據(jù)需頻繁更新時。Last update: Oct.200952Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論目錄 Contents5.1 數(shù)據(jù)庫存儲結(jié)構(gòu)多級存儲物理結(jié)構(gòu)邏輯結(jié)構(gòu)5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制索引散列簇集Last update: Oct.200953Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2

48、關(guān)系數(shù)據(jù)庫中表的典型存儲機制一散列散列（Hash）是與表或簇集相關(guān)的一種可選存儲機制，由于可通過一個Hash函數(shù)將散列鍵（Hash Key）的值映射成一個數(shù)據(jù)塊的地址，給出散列鍵的值Ki立即可通過h (Ki)得到其對應(yīng)的存儲物理塊地址，從而可明顯改進數(shù)據(jù)檢索的性能。Hash Key的值Kih(Ki)數(shù)據(jù)文件Last update: Oct.200954Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一散列靜態(tài)散列的實現(xiàn)方法建立數(shù)據(jù)文件的散列鍵K以及該鍵值的

49、集合 K1, K2 , Kn 建立磁盤物理存儲單位桶(Bucket)以及桶地址的集合 b1, b2, , bm 。一個桶可以存放多條記錄（或記錄指針）一個桶可以是一個磁盤物理塊，也可以是比磁盤塊還大的物理空間。設(shè)計散列函數(shù)hash(Ki)以建立數(shù)據(jù)文件中散列鍵的值與桶（桶地址）之間的對應(yīng)關(guān)系，即一個Ki通過hash(Ki)必能找到唯一的一個桶地址。設(shè)計良好的散列函數(shù)將使得n個指定項值被平均分配到m個桶中去。Last update: Oct.200955Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫

50、系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一散列K1，K2，Knb1，b2，bmh(Ki)散列鍵值集合桶地址集合在散列技術(shù)中，桶的空間大小是固定的，即一個桶中可以存放的記錄（指針）數(shù)是固定的。但是在實際應(yīng)用中，記錄在指定項值上的分布往往是不均衡的，從而使得在某些桶中存在空間浪費現(xiàn)象，而另外一些桶則存在空間溢出問題。當一個桶的空間溢出時，需要通過鏈接的方法申請“溢出桶”與其相聯(lián)，以達到擴大桶空間的目的。Last update: Oct.200956Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)

51、引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一散列靜態(tài)散列技術(shù)優(yōu)點按Hash鍵值訪問數(shù)據(jù)，速度快缺點Hash鍵值映射的地址空間有限；用Hash鍵值尋址時，同一個Hash鍵值可能對應(yīng)多個記錄，不同的Hash鍵值可能映射到同一個地址。只對Hash鍵值到記錄的訪問有效，對其他類型的訪問不一定有效處理變長記錄不便很難找到通用的Hash函數(shù)當桶（Bucket）裝滿后的溢出處理較為復雜等原因，在數(shù)據(jù)經(jīng)常變動的數(shù)據(jù)庫環(huán)境中不宜使用，故使用動態(tài)散列（桶的數(shù)目可以分動態(tài)變化；桶可分裂/合并）較多。Last update: Oct.200957Lecture Notes - Principles of Databas

52、es Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一散列在理想下，基于散列鍵的單行查詢只需一次I/O即可。但散列帶來好處的情況并不多，例如：Oracle就如此，以至于把“散列”就說成是“散列簇集” 。散列簇集(Hash Cluster)，即對簇表的行在簇集鍵列上運用Hash函數(shù)進行散列，以決定相應(yīng)數(shù)據(jù)塊的物理地址。Oracle提供缺省的Hash函數(shù)，支持單列/列組上的散列簇集。用戶也可以自己提供Hash函數(shù)，但此時有限制：簇集鍵/散列鍵必須由單列組成，且只允許取整數(shù)值。Last update: Oct.200958Lecture Notes - Principles of Databases Systems. By Zhuoming Xu 第1部分 數(shù)據(jù)庫系統(tǒng)引論5.2 關(guān)系數(shù)據(jù)庫中表的典型存儲機制一散列利弊利若Hash值對每行是唯一的，此時使用散