數(shù)據(jù)庫系統(tǒng)教程DBS：第六章 數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)

第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)

6.1文件組織

6.3文件結(jié)構(gòu)

6.3索引技術(shù)第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.1文件組織在外存，數(shù)據(jù)庫以文件形式組織，文件由記錄組成。記錄是數(shù)據(jù)庫的基本數(shù)據(jù)單位記錄由若干字段組成文件組織有兩種方式：

定長記錄：每個(gè)記錄占固定長度的字節(jié)數(shù)變長記錄：記錄的長度可變記錄在物理塊上的分配：不跨塊：每個(gè)記錄完整地存在一個(gè)物理塊中

跨塊：一個(gè)記錄可以分開存儲(chǔ)在不同物理塊中第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.2文件組織◆刪除記錄的三種處理方式

（1）把被刪除的記錄依次移上來。（2）把文件中最后的記錄填補(bǔ)到刪除記錄的位置。（3）把被刪除的結(jié)點(diǎn)用指針鏈接起來

6.1.1定長記錄的處理

第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.3文件結(jié)構(gòu)變長記錄的字節(jié)串表示形式（1）每條記錄尾部添加“記錄尾標(biāo)識(shí)符”（2）記錄開始添加記錄長度字段分槽式頁結(jié)構(gòu)（以塊為單位進(jìn)行存儲(chǔ)）

塊首部：記錄數(shù)目、指向自由空間尾部的指針，每個(gè)記錄的開始位置和大小

自由空間：從后往前使用空間（pp.圖6.6）6.1.2變長記錄處理

◆文件結(jié)構(gòu)能適應(yīng)數(shù)據(jù)的動(dòng)態(tài)變化，提供快速訪問路徑◆共享→文件結(jié)構(gòu)能提供多種訪問路徑、方便并發(fā)控制、恢復(fù)、安全控制

◆文件結(jié)構(gòu)能適應(yīng)數(shù)據(jù)量的增長◆

4種文件結(jié)構(gòu)： 堆文件（HeapFile） 順序文件(SequentialFile) 散列文件(HashingFile) 聚集文件(ClusteringFile)

6.2、文件結(jié)構(gòu)

第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.3文件結(jié)構(gòu)三、文件的基本類型記錄的存放：記錄按其插入的先后次序存放存取路徑：順序搜索－－按記錄的自然次序，順序查找所需記錄特點(diǎn)：適用于查詢所有或相當(dāng)多的記錄的訪問類型適于做小文件的文件結(jié)構(gòu)其它場合下查詢效率低，I/O和CPU的開銷大記錄的插入方便，刪除困難

1.堆文件(HeapFile)

第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.3文件結(jié)構(gòu)記錄的存放：根據(jù)查找鍵的值的順序存儲(chǔ)記錄的文件存取路徑：如果是查找鍵，順序查找或者二分查找；如果非查找鍵則順序查找。特點(diǎn)：在順序文件初始建立時(shí)，可以保持物理順序和查找鍵值的順序一致，但經(jīng)過多次插入或刪除操作后，就很難維持這種一致狀態(tài)。2.順序文件(SequentialFile)第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.3文件結(jié)構(gòu)記錄的存放：將記錄的某一屬性（一般為PK）即散列鍵用散列函數(shù)直接映射成記錄的地址，記錄按此地址存放存取路徑：按散列鍵訪問特點(diǎn)：只對(duì)散列鍵到記錄的訪問有效在需要快速查找的特殊場合(數(shù)據(jù)目錄和鎖表查詢)有效散列鍵映射的地址空間(桶)固定，文件大了溢出，小了浪費(fèi)不便處理變長記錄好的散列函數(shù)難找分成靜態(tài)散列和動(dòng)態(tài)散列（PP.201散列技術(shù)）3.散列文件(hashingfile)第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.3文件結(jié)構(gòu)3.聚集文件(clusteringfile)定義－－個(gè)文件存儲(chǔ)多個(gè)關(guān)系的記錄，不同關(guān)系中有聯(lián)系的記錄存于一個(gè)物理塊或相鄰區(qū)域也適用于經(jīng)常進(jìn)行連接操作的多個(gè)關(guān)系

S1WANG20MS2LIU21FS3CHEN22M例：關(guān)系S關(guān)系SCS1C180S1C270S3C190S3C285S3C395S1WANG20MS1C180S1C270S3C190S3C285S3C395S2LIU21FS3CHEN22M聚集文件：第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.3文件結(jié)構(gòu)

6.1文件組織

6.2文件結(jié)構(gòu)

6.3索引技術(shù)第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.4索引技術(shù)索引：為了加快對(duì)記錄的查找而建立的外存文件結(jié)構(gòu)。一個(gè)索引文件由兩個(gè)部分：主文件和索引，主文件即原始文件，我們考慮主文件是順序文件的情況，對(duì)應(yīng)同一主文件可以建立幾套不同的索引。根據(jù)索引中查找鍵值的順序和主文件的順序?qū)?yīng)關(guān)系可以分成主索引和輔助索引。主索引：如果索引中查找鍵值的順序與主文件的順序一致，這種索引成為主索引。輔助索引項(xiàng)：如果索引中查找鍵值的順序與主文件的順序不一致，這種索引成為輔助索引。索引記錄：索引文件由索引記錄組成，每個(gè)索引記錄主要包括索引鍵和指針。6.3索引技術(shù)◆每個(gè)原始文件只有一個(gè)主索引◆兩種常見實(shí)現(xiàn)方法： 對(duì)于主文件的每一個(gè)查找鍵建立一個(gè)索引記錄－－稠密索引（PP.191圖6.13） 對(duì)于主文件的若干個(gè)查找鍵建立一個(gè)索引記錄－－稀疏索引（PP.191圖6.14）性能分析：稠密索引查找較快，稀疏索引查找較慢；稠密索引消耗空間大，稀疏索引消耗空間少；多級(jí)索引：形成樹形結(jié)構(gòu)（頂層稀疏索引+底層稠密索引）一、主索引第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.4索引技術(shù)◆索引文件的實(shí)現(xiàn)方式二、輔助索引◆為每個(gè)查找鍵值建立一個(gè)索引項(xiàng)，內(nèi)容包括一個(gè)查找鍵值和一個(gè)指針，但這個(gè)指針不是指向主文件中的記錄，而是指向一個(gè)桶，桶內(nèi)存放指向同一個(gè)查找鍵值的主記錄的指針（圖6.16）。一般是在非主鍵的屬性上建立的索引。第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.4索引技術(shù)三、多級(jí)索引結(jié)構(gòu)→平衡樹(balancedtree)B+樹1.B＋樹實(shí)現(xiàn)的主索引(1)文件結(jié)構(gòu)非葉結(jié)點(diǎn)

…

…

…

…

…

……

…

……葉結(jié)點(diǎn)STSH結(jié)點(diǎn)(物理塊)結(jié)點(diǎn)(物理塊)根結(jié)點(diǎn)葉結(jié)點(diǎn)第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.4索引技術(shù)非葉結(jié)點(diǎn)K0…Kn-1→索引健值,K0<K1<…<

Kn-1不一定是實(shí)際鍵值P0…Pn

→指針

P0

P1……

PnK0K1

PiKn-1

Ki◆

結(jié)點(diǎn)結(jié)構(gòu)：◆

級(jí)間關(guān)系：每個(gè)鍵值都大于其左側(cè)指針指向的下級(jí)結(jié)點(diǎn)中存儲(chǔ)的鍵值都小于或等于其右側(cè)指針指向的下級(jí)結(jié)點(diǎn)中存儲(chǔ)的鍵值非葉結(jié)點(diǎn)

葉結(jié)點(diǎn)STSH第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.4索引技術(shù)

設(shè)要找索引鍵值Kx所對(duì)應(yīng)的記錄◆

搜索方法：從根結(jié)點(diǎn)開始，依以下規(guī)則自上而下地搜索：若Kx<K0則沿P0所指的結(jié)點(diǎn)向下搜索若Kx≥Kn-1則沿Pn

所指的結(jié)點(diǎn)向下搜索若Ki-1≤Kx<Ki

則沿Pi所指的結(jié)點(diǎn)向下搜索第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.4索引技術(shù)非葉結(jié)點(diǎn)

葉結(jié)點(diǎn)STSH

P0

P1……

PnK0K1

PiKn-1

Ki前、后向指針用于雙向連接葉結(jié)點(diǎn)tid(元組標(biāo)識(shí)符)→指向記錄的指針＝塊號(hào)＋記錄在塊中的指針號(hào)K0…Kn-1→索引健值：K0<K1<…<

Kn-1

是文件中實(shí)際存在的鍵值，升序葉結(jié)點(diǎn)◆

處于樹的同一級(jí)上

前向指針

后向指針…

tidn-1K0Kn-1

tid0◆結(jié)點(diǎn)結(jié)構(gòu)：◆

搜索方法：從SH開始從ST開始從非葉結(jié)點(diǎn)檢索到的某一鍵值開始，向左右搜索

STSH第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.4索引技術(shù)設(shè)：為m叉樹，通常每個(gè)物理塊存儲(chǔ)一個(gè)結(jié)點(diǎn)則：

m＝物理塊大小/索引項(xiàng)長度◆除葉節(jié)點(diǎn)外，若節(jié)點(diǎn)有J個(gè)健值，則有J+1個(gè)指針和

J+1顆子樹，m為結(jié)點(diǎn)的指針數(shù)上限◆每個(gè)結(jié)點(diǎn)最多有(m－1)個(gè)鍵值(m顆子樹)◆根結(jié)點(diǎn)至少有1個(gè)鍵值(兩顆子樹)◆其它非葉結(jié)點(diǎn)至少有(m－1)/2個(gè)鍵值◆所有葉節(jié)點(diǎn)都處在樹的同一級(jí)上→樹始終保持平衡說明：(m－1)/2指大于它的最小整數(shù)(2)B＋樹的規(guī)定第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.4索引技術(shù)(3)B＋樹的主要特點(diǎn)-索引項(xiàng)數(shù)與樹的高度可以動(dòng)態(tài)地隨著數(shù)據(jù)的變化而消長-搜索所需的I/O次數(shù)取決于樹的高度-I/O次數(shù)與m及索引鍵的不同值數(shù)N有關(guān)

㏒p(N),P為>=m/2的最小整數(shù)第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.4索引技術(shù)(4)B＋保持平衡的算法

插入記錄(設(shè)此記錄的索引鍵值為KX)：

◆

按前述搜索方法，從根向下搜索至相應(yīng)的葉結(jié)點(diǎn)

(對(duì)于主索引，在搜索中若發(fā)現(xiàn)與KX值相等的鍵值則出錯(cuò))◆若該葉節(jié)點(diǎn)未滿(少于m－1個(gè)鍵值)：則將鍵值KX和該記錄的tid

插入該葉結(jié)點(diǎn)

若被插入的葉節(jié)點(diǎn)已滿(有m－1個(gè)鍵值)

：將該葉結(jié)點(diǎn)分裂為二，分別有m/2個(gè)鍵值向系統(tǒng)再申請一個(gè)物理塊其父結(jié)點(diǎn)也需增加一個(gè)鍵值必要的話父結(jié)點(diǎn)也要分裂，直至根結(jié)點(diǎn)(樹增加一級(jí))第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.4索引技術(shù)例1：引起索引結(jié)點(diǎn)分裂的插入操作：第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.4索引技術(shù)插入索引鍵值“JIANG”3階B＋樹索引第一步：搜索HELIU第二步：分裂葉結(jié)點(diǎn)插入JIANG第三步：父結(jié)點(diǎn)插入新

結(jié)點(diǎn)最小鍵值

可能分裂第四步：向上至根結(jié)點(diǎn)WEN

ZHANGLOULOUHELIU

ZHANGZHOUWENJIANG<WENJIANG<LOUHELIUJIANG

LIULOU刪除記錄(設(shè)此記錄的索引鍵值為KX)：

◆按前述搜索方法，從根向下搜索至相應(yīng)的葉結(jié)點(diǎn)

◆刪除對(duì)應(yīng)的索引項(xiàng)

◆若刪除后葉節(jié)點(diǎn)的索引項(xiàng)數(shù)<(m-1)/2：

-若任一相鄰葉結(jié)點(diǎn)中索引項(xiàng)數(shù)>(m-1)/2

移一個(gè)索引項(xiàng)到被刪除葉結(jié)點(diǎn)，以滿足≥(m-1)/2條件

-若相鄰葉結(jié)點(diǎn)中項(xiàng)數(shù)都＝(m-1)/2

與任一相鄰葉結(jié)點(diǎn)合并為一個(gè)有m-2項(xiàng)的葉結(jié)點(diǎn),

與此同時(shí)父節(jié)點(diǎn)中減少一個(gè)鍵值，有可能導(dǎo)致父結(jié)點(diǎn)合并，直至根結(jié)點(diǎn)(樹少一級(jí))第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.4索引技術(shù)例2：引起索引結(jié)點(diǎn)合并的刪除操作：第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.4索引技術(shù)刪除索引鍵值“LIU”3階B＋樹索引WEN

ZHANGLIULOULOU

ZHANGZHOUWEN

HE

JIANGLIULOU

例2：引起索引結(jié)點(diǎn)合并的刪除操作：第六章數(shù)據(jù)庫的存儲(chǔ)結(jié)構(gòu)6.4索引技術(shù)刪除索引鍵值“LIU”圖3階B＋樹索引刪除索引鍵值“WEN”WEN

ZHANGLOU

ZHANGZHOUWEN

HE

JIANGLOU第一步：搜索WEN第二步：刪除WEN第三步：父結(jié)點(diǎn)刪除

指針，合并第四步：向上至根結(jié)點(diǎn)LOUZHANG

WEN

2.B＋樹實(shí)現(xiàn)的次索引次索引：一個(gè)索引鍵值可對(duì)應(yīng)多個(gè)記錄(多個(gè)tid)，且數(shù)量可變（非聚集)