第6章DB的存儲(chǔ)結(jié)構(gòu)(2008)

1、1第第6章章 DB的存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)2第第6章章 數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)v6.1 文件組織文件組織v6.2 文件結(jié)構(gòu)文件結(jié)構(gòu)v6.3 索引技術(shù)索引技術(shù)v6.4 散列技術(shù)散列技術(shù)v6.5 多鍵訪問(wèn)多鍵訪問(wèn)v6.6 小結(jié)小結(jié)3前前 言言v前面幾章，主要強(qiáng)調(diào)數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)。在關(guān)系模前面幾章，主要強(qiáng)調(diào)數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)。在關(guān)系模型中，我們把數(shù)據(jù)庫(kù)看成關(guān)系的匯集。數(shù)據(jù)庫(kù)系統(tǒng)型中，我們把數(shù)據(jù)庫(kù)看成關(guān)系的匯集。數(shù)據(jù)庫(kù)系統(tǒng)的一個(gè)目標(biāo)是使用戶能簡(jiǎn)單、方便、容易地存取數(shù)的一個(gè)目標(biāo)是使用戶能簡(jiǎn)單、方便、容易地存取數(shù)據(jù)庫(kù)中的數(shù)據(jù)。用戶訪問(wèn)數(shù)據(jù)庫(kù)，不必關(guān)心數(shù)據(jù)庫(kù)據(jù)庫(kù)中的數(shù)據(jù)。用戶訪問(wèn)數(shù)據(jù)庫(kù)，不必關(guān)心數(shù)據(jù)庫(kù)的

2、存儲(chǔ)結(jié)構(gòu)和具體的實(shí)現(xiàn)方式。但是，用戶如能了的存儲(chǔ)結(jié)構(gòu)和具體的實(shí)現(xiàn)方式。但是，用戶如能了解數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)，那么對(duì)于數(shù)據(jù)庫(kù)就會(huì)有一個(gè)解數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)，那么對(duì)于數(shù)據(jù)庫(kù)就會(huì)有一個(gè)比較完整的了解，拓寬知識(shí)面。比較完整的了解，拓寬知識(shí)面。v本章先介紹文件組織形式，然后介紹以及常用的索本章先介紹文件組織形式，然后介紹以及常用的索引組織和散列組織。引組織和散列組織。46.1 文件組織文件組織v6.1.1 定長(zhǎng)記錄定長(zhǎng)記錄v6.1.2 變長(zhǎng)記錄變長(zhǎng)記錄v在外存中，數(shù)據(jù)庫(kù)以文件形式組織，而文件由記在外存中，數(shù)據(jù)庫(kù)以文件形式組織，而文件由記錄組成。文件結(jié)構(gòu)由操作系統(tǒng)的文件系統(tǒng)提供和管錄組成。文件結(jié)構(gòu)由操作系統(tǒng)的

3、文件系統(tǒng)提供和管理。那么邏輯文件中的記錄在物理文件中將如何實(shí)理。那么邏輯文件中的記錄在物理文件中將如何實(shí)現(xiàn)。這是本節(jié)所討論的問(wèn)題?，F(xiàn)。這是本節(jié)所討論的問(wèn)題。v一般，文件組織有兩種方式，一種是把記錄設(shè)計(jì)一般，文件組織有兩種方式，一種是把記錄設(shè)計(jì)成定長(zhǎng)格式，另一種是變長(zhǎng)格式，下面分別討論。成定長(zhǎng)格式，另一種是變長(zhǎng)格式，下面分別討論。5v為關(guān)系模式為關(guān)系模式EMP（ENAME，ENO，SALARY）可）可以設(shè)計(jì)一個(gè)文件，記錄格式如下：以設(shè)計(jì)一個(gè)文件，記錄格式如下：TYPE EMP_TYPE = RECORDENAME：CHAR(10)；ENO：CHAR(10)；SALARY：REAL； ENDv假設(shè)

4、一個(gè)實(shí)數(shù)占假設(shè)一個(gè)實(shí)數(shù)占8個(gè)字節(jié)，那么每個(gè)記錄占個(gè)字節(jié)，那么每個(gè)記錄占28個(gè)字個(gè)字節(jié)。可以像圖節(jié)?？梢韵駡D6.1那樣把記錄依次組織起來(lái)。一個(gè)職那樣把記錄依次組織起來(lái)。一個(gè)職工可以為幾個(gè)部門工作，因此可以有幾個(gè)工號(hào)。工可以為幾個(gè)部門工作，因此可以有幾個(gè)工號(hào)。6.1.1 定長(zhǎng)記錄（定長(zhǎng)記錄（1）66.1.1 定長(zhǎng)記錄（定長(zhǎng)記錄（2）v在系統(tǒng)運(yùn)行時(shí)，有兩個(gè)問(wèn)在系統(tǒng)運(yùn)行時(shí)，有兩個(gè)問(wèn)題需考慮：題需考慮：如果要?jiǎng)h除一個(gè)記錄，如果要?jiǎng)h除一個(gè)記錄，那么必須在被刪位置上填那么必須在被刪位置上填補(bǔ)一個(gè)記錄，或者設(shè)法使補(bǔ)一個(gè)記錄，或者設(shè)法使文件忽略該位置。文件忽略該位置。除非每塊的大小恰好是除非每塊的大小恰好是28

5、的倍數(shù)，否則可能有的的倍數(shù)，否則可能有的記錄橫跨兩個(gè)塊。讀記錄橫跨兩個(gè)塊。讀 / 寫(xiě)寫(xiě)這樣的記錄就要訪問(wèn)兩個(gè)這樣的記錄就要訪問(wèn)兩個(gè)塊。塊。記錄記錄0LIUA-102 600記錄記錄1WENB-306 700記錄記錄2HEF-257 800記錄記錄3 ZHANG A-214 600記錄記錄4 ZHOUC-343 750記錄記錄5LIUB-215 800記錄記錄6LOUB-428 850記錄記錄7 ZHANG B-467 600記錄記錄8LIUC-333 400圖圖6.1 定長(zhǎng)記錄的文件定長(zhǎng)記錄的文件76.1.1 定長(zhǎng)記錄（定長(zhǎng)記錄（3）v1刪除操作時(shí)的考慮刪除操作時(shí)的考慮v刪除一個(gè)記錄，可采用下

6、面刪除一個(gè)記錄，可采用下面三種方法之一實(shí)現(xiàn)：三種方法之一實(shí)現(xiàn)：v（1） 把被刪記錄后的記錄把被刪記錄后的記錄一次移上來(lái)一次移上來(lái)v例如在圖例如在圖6.1中，要?jiǎng)h除記錄中，要?jiǎng)h除記錄2，那么要把記錄，那么要把記錄38依次移依次移上來(lái)，如圖上來(lái)，如圖6.2所示。這時(shí)刪所示。這時(shí)刪除一個(gè)記錄平均要移動(dòng)文件除一個(gè)記錄平均要移動(dòng)文件中的一半記錄。中的一半記錄。記錄記錄0LIUA-102 600記錄記錄1WENB-306 700記錄記錄3 ZHANGA-214 600記錄記錄4 ZHOU C-343 750記錄記錄5LIUB-215 800記錄記錄6LOUB-428 850記錄記錄7 ZHANG B-46

7、7 600記錄記錄8LIUC-333 400圖圖6.2 把被刪記錄后的把被刪記錄后的記錄依次移上來(lái)記錄依次移上來(lái) 86.1.1 定長(zhǎng)記錄（定長(zhǎng)記錄（4）v（2） 把文件中最后一把文件中最后一個(gè)記錄填補(bǔ)到被刪記錄個(gè)記錄填補(bǔ)到被刪記錄位置，如圖位置，如圖6.3所示。所示。v這兩種方法都要移動(dòng)結(jié)這兩種方法都要移動(dòng)結(jié)點(diǎn)，操作不靈活。由于點(diǎn)，操作不靈活。由于數(shù)據(jù)庫(kù)中刪除操作總是數(shù)據(jù)庫(kù)中刪除操作總是少于插入操作，因此我少于插入操作，因此我們可以采用下面方式實(shí)們可以采用下面方式實(shí)現(xiàn)。現(xiàn)。記錄記錄0LIUA-102 600記錄記錄1WENB-306 700記錄記錄8LIUC-333 400記錄記錄3 ZHAN

8、GA-214 600記錄記錄4 ZHOU C-343 750記錄記錄5LIUB-215 800記錄記錄6LOUB-428 850記錄記錄7 ZHANG B-467 600圖圖6.3 把最后一個(gè)記錄把最后一個(gè)記錄填補(bǔ)到被刪記錄位置填補(bǔ)到被刪記錄位置9v（3） 把被刪結(jié)點(diǎn)用指針把被刪結(jié)點(diǎn)用指針鏈接起來(lái)鏈接起來(lái)v在每個(gè)記錄中增加一個(gè)指在每個(gè)記錄中增加一個(gè)指針，在文件中增設(shè)一個(gè)文針，在文件中增設(shè)一個(gè)文件首部。文件如圖件首部。文件如圖6.4所示。所示。v這種方式較好。但要注意，這種方式較好。但要注意，是否還有指針指向被刪記是否還有指針指向被刪記錄。在錄。在DB中，被指針指向中，被指針指向的記錄稱為的記錄

9、稱為“被拴記錄被拴記錄”。如果不小心把被拴記錄刪如果不小心把被拴記錄刪掉，那么指向該記錄的指掉，那么指向該記錄的指針成了針成了“懸掛指針懸掛指針”。懸。懸掛指針指向的空間稱為掛指針指向的空間稱為“垃圾垃圾”，即該空間別人，即該空間別人無(wú)法使用而又被空閑著。無(wú)法使用而又被空閑著。6.1.1 定長(zhǎng)記錄（定長(zhǎng)記錄（5）文件文件首部首部記錄記錄0LIUA-102 600記錄記錄1記錄記錄2HEF-257 800記錄記錄3 ZHANG A-214 600記錄記錄4記錄記錄5LIUB-215 800記錄記錄6記錄記錄7 ZHANG B-467 600記錄記錄8LIUC-333 400圖圖6.4 刪除記錄刪

10、除記錄1、4、6后的文件結(jié)構(gòu)后的文件結(jié)構(gòu)10v2插入操作時(shí)的考慮插入操作時(shí)的考慮v如果采用把被刪記錄鏈接起來(lái)的方法，那么插入操如果采用把被刪記錄鏈接起來(lái)的方法，那么插入操作可采用下列方法：作可采用下列方法：v在空閑記錄鏈表的第一個(gè)空閑記錄中，填上插入記在空閑記錄鏈表的第一個(gè)空閑記錄中，填上插入記錄的值，同時(shí)使首部指針指向下一個(gè)空閑記錄；如錄的值，同時(shí)使首部指針指向下一個(gè)空閑記錄；如果空閑記錄鏈表為空，那么只能把新記錄插到文件果空閑記錄鏈表為空，那么只能把新記錄插到文件尾。尾。v定長(zhǎng)記錄文件的插入操作比較簡(jiǎn)單，因?yàn)椴迦胗涗浂ㄩL(zhǎng)記錄文件的插入操作比較簡(jiǎn)單，因?yàn)椴迦胗涗浀拈L(zhǎng)度與被刪記錄的長(zhǎng)度是相等的

11、。在變長(zhǎng)記錄文的長(zhǎng)度與被刪記錄的長(zhǎng)度是相等的。在變長(zhǎng)記錄文件中操作就復(fù)雜了。件中操作就復(fù)雜了。6.1.1 定長(zhǎng)記錄（定長(zhǎng)記錄（6）11v在在DBS中，有時(shí)需要文件中的記錄是變長(zhǎng)格式。中，有時(shí)需要文件中的記錄是變長(zhǎng)格式。v例如，一個(gè)文件存儲(chǔ)了多種不同的記錄類型記錄；文件中允例如，一個(gè)文件存儲(chǔ)了多種不同的記錄類型記錄；文件中允許記錄類型的記錄是變長(zhǎng)的；允許記錄中某個(gè)字段可以出現(xiàn)許記錄類型的記錄是變長(zhǎng)的；允許記錄中某個(gè)字段可以出現(xiàn)重復(fù)組等等。重復(fù)組等等。v例如圖例如圖6.1的文件也可以設(shè)計(jì)成變長(zhǎng)記錄格式：的文件也可以設(shè)計(jì)成變長(zhǎng)記錄格式：TYPE EMP_LIST=RECORD ENAME：CHAR（

12、10）；）； ENO_INFO：ARRAY1. OFRECORD ENO：CHAR（10）；）； SALARY：REAL；END ENDv此處定義（此處定義（ENO，SALARY）作為成分元素組成一個(gè)數(shù)組，）作為成分元素組成一個(gè)數(shù)組，成分具體個(gè)數(shù)視實(shí)際情況而定。成分具體個(gè)數(shù)視實(shí)際情況而定。6.1.2 變長(zhǎng)記錄（變長(zhǎng)記錄（1）126.1.2 變長(zhǎng)記錄（變長(zhǎng)記錄（2）v變長(zhǎng)記錄的表示有字節(jié)串形式和定長(zhǎng)形式兩種。變長(zhǎng)記錄的表示有字節(jié)串形式和定長(zhǎng)形式兩種。v1變長(zhǎng)記錄的字節(jié)串表示形式變長(zhǎng)記錄的字節(jié)串表示形式這種形式是把每個(gè)記錄看成連續(xù)的字節(jié)串，然后在每這種形式是把每個(gè)記錄看成連續(xù)的字節(jié)串，然后在每個(gè)記

13、錄的尾部附加個(gè)記錄的尾部附加“記錄尾標(biāo)識(shí)符記錄尾標(biāo)識(shí)符”（）。圖）。圖6.1的定長(zhǎng)的定長(zhǎng)記錄文件可以用圖記錄文件可以用圖6.5的格式表示。的格式表示。0LIUA-102 600 B-215 800 C-333 4001WEN B-306 7002HEF-257 8003 ZHANGA-214 600 B-467 6004ZHOU C-343 7505LOUB-428 850圖圖6.5 變長(zhǎng)記錄的字節(jié)串表示形式變長(zhǎng)記錄的字節(jié)串表示形式13v字節(jié)串表現(xiàn)形式的另一種方式是在記錄的開(kāi)始加一個(gè)記錄長(zhǎng)字節(jié)串表現(xiàn)形式的另一種方式是在記錄的開(kāi)始加一個(gè)記錄長(zhǎng)度的字段來(lái)實(shí)現(xiàn)，而不是使用在記錄尾加標(biāo)志符的方法。度的

14、字段來(lái)實(shí)現(xiàn)，而不是使用在記錄尾加標(biāo)志符的方法。v字節(jié)串表示形式有兩個(gè)缺點(diǎn)：字節(jié)串表示形式有兩個(gè)缺點(diǎn)：v（1） 由于各記錄的長(zhǎng)度不一，因此被刪記錄的位置難以重由于各記錄的長(zhǎng)度不一，因此被刪記錄的位置難以重新使用。既使制訂許多技術(shù)規(guī)則，仍然會(huì)導(dǎo)致磁盤(pán)中出現(xiàn)大新使用。既使制訂許多技術(shù)規(guī)則，仍然會(huì)導(dǎo)致磁盤(pán)中出現(xiàn)大量小的空間（即量小的空間（即“碎片碎片”）浪費(fèi)了。）浪費(fèi)了。v（2） 如果文件中的記錄要伸長(zhǎng)，很難實(shí)現(xiàn)。必須要把記錄如果文件中的記錄要伸長(zhǎng)，很難實(shí)現(xiàn)。必須要把記錄移到他處才能伸長(zhǎng)。如果要伸長(zhǎng)的記錄是移到他處才能伸長(zhǎng)。如果要伸長(zhǎng)的記錄是“被拴記錄被拴記錄”，那，那么移動(dòng)的代價(jià)是很大的。么移動(dòng)的代

15、價(jià)是很大的。v由于上述兩個(gè)缺點(diǎn)，現(xiàn)在一般不使用字節(jié)串表現(xiàn)形式。在實(shí)由于上述兩個(gè)缺點(diǎn)，現(xiàn)在一般不使用字節(jié)串表現(xiàn)形式。在實(shí)際中，往往使用的是一種改進(jìn)的字節(jié)串表現(xiàn)形式，稱為際中，往往使用的是一種改進(jìn)的字節(jié)串表現(xiàn)形式，稱為“分分槽式頁(yè)結(jié)構(gòu)槽式頁(yè)結(jié)構(gòu)”（slotted page structure），如圖），如圖6.6所示。所示。6.1.2 變長(zhǎng)記錄（變長(zhǎng)記錄（3）14v在每塊的開(kāi)始處設(shè)置一個(gè)在每塊的開(kāi)始處設(shè)置一個(gè)“塊首部塊首部”，其中包括下列信息：，其中包括下列信息： 塊中記錄數(shù)目塊中記錄數(shù)目 指向塊中自由空間尾部的指針指向塊中自由空間尾部的指針 登記每個(gè)記錄的開(kāi)始位置和大小的信息登記每個(gè)記錄的開(kāi)始位

16、置和大小的信息6.1.2 變長(zhǎng)記錄（變長(zhǎng)記錄（4）塊首部塊首部記錄大小記錄大小 記錄數(shù)目記錄數(shù)目自由空間自由空間記錄位置記錄位置自由空間尾部自由空間尾部圖圖6.6 分槽式頁(yè)結(jié)構(gòu)分槽式頁(yè)結(jié)構(gòu)15v在塊中實(shí)際記錄緊連著，并靠近塊尾部存放。塊中在塊中實(shí)際記錄緊連著，并靠近塊尾部存放。塊中自由空間也緊連著，在塊的中間。插入總是從自由自由空間也緊連著，在塊的中間。插入總是從自由空間尾部開(kāi)始，并在塊首部登錄其插入記錄的開(kāi)始空間尾部開(kāi)始，并在塊首部登錄其插入記錄的開(kāi)始位置和大小。位置和大小。v記錄刪除時(shí)只要在塊首部該記錄的大小登記處改為記錄刪除時(shí)只要在塊首部該記錄的大小登記處改為-1即可。更進(jìn)一步，可以把被

17、刪記錄左邊的記錄移即可。更進(jìn)一步，可以把被刪記錄左邊的記錄移過(guò)來(lái)填補(bǔ)，使實(shí)際記錄仍然緊連著。當(dāng)然此時(shí)塊首過(guò)來(lái)填補(bǔ)，使實(shí)際記錄仍然緊連著。當(dāng)然此時(shí)塊首部記錄的信息也要修改。記錄的伸縮也可使用這樣部記錄的信息也要修改。記錄的伸縮也可使用這樣的方法。在塊中移動(dòng)記錄的代價(jià)也不太高，這是因的方法。在塊中移動(dòng)記錄的代價(jià)也不太高，這是因?yàn)橐粔K的大小最多只有為一塊的大小最多只有4KB。v在分槽式頁(yè)結(jié)構(gòu)中，要求其它指針不能直接指向記在分槽式頁(yè)結(jié)構(gòu)中，要求其它指針不能直接指向記錄本身，而是指向塊首部中的記錄信息登記項(xiàng)，這錄本身，而是指向塊首部中的記錄信息登記項(xiàng)，這樣塊中記錄的移動(dòng)就獨(dú)立與外界因素了。樣塊中記錄的移

18、動(dòng)就獨(dú)立與外界因素了。6.1.2 變長(zhǎng)記錄（變長(zhǎng)記錄（5）16v2變長(zhǎng)記錄的定長(zhǎng)表示形式變長(zhǎng)記錄的定長(zhǎng)表示形式在文件系統(tǒng)中往往是使用一個(gè)或多個(gè)定長(zhǎng)記錄在文件系統(tǒng)中往往是使用一個(gè)或多個(gè)定長(zhǎng)記錄來(lái)表示變長(zhǎng)記錄的方法。具體實(shí)現(xiàn)時(shí)有兩種技術(shù)：來(lái)表示變長(zhǎng)記錄的方法。具體實(shí)現(xiàn)時(shí)有兩種技術(shù)：預(yù)留空間和指針技術(shù)。預(yù)留空間和指針技術(shù)。v（1） 預(yù)留空間的方法預(yù)留空間的方法取所有變長(zhǎng)記錄中最長(zhǎng)的一個(gè)記錄的長(zhǎng)度作為取所有變長(zhǎng)記錄中最長(zhǎng)的一個(gè)記錄的長(zhǎng)度作為存儲(chǔ)空間的記錄長(zhǎng)度，來(lái)存儲(chǔ)變長(zhǎng)記錄。如果變長(zhǎng)存儲(chǔ)空間的記錄長(zhǎng)度，來(lái)存儲(chǔ)變長(zhǎng)記錄。如果變長(zhǎng)記錄短于存儲(chǔ)記錄長(zhǎng)度，那么在多余空間處填上某記錄短于存儲(chǔ)記錄長(zhǎng)度，那么在多余

19、空間處填上某個(gè)特定的空值或記錄尾標(biāo)志符。例如圖個(gè)特定的空值或記錄尾標(biāo)志符。例如圖6.5的字節(jié)串的字節(jié)串表現(xiàn)形式可以用圖表現(xiàn)形式可以用圖6.7的預(yù)留空間方法實(shí)現(xiàn)。這方法的預(yù)留空間方法實(shí)現(xiàn)。這方法一般使用在大多數(shù)記錄的長(zhǎng)度接近最大長(zhǎng)度時(shí)才使一般使用在大多數(shù)記錄的長(zhǎng)度接近最大長(zhǎng)度時(shí)才使用，否則使用時(shí)空間浪費(fèi)很大。用，否則使用時(shí)空間浪費(fèi)很大。6.1.2 變長(zhǎng)記錄（變長(zhǎng)記錄（6）176.1.2 變長(zhǎng)記錄（變長(zhǎng)記錄（7）圖圖6.7 變長(zhǎng)記錄變長(zhǎng)記錄的預(yù)留空間的預(yù)留空間表示形式表示形式0 0LIULIU A-102A-102 600600 B-215B-215 800800 C-333C-333 40040

20、01 1WENWEN B-306B-306 7007002 2HEHEF-257F-257 8008003 3 ZHANGZHANGA-214A-214 600600 B-467B-467 6006004 4 ZHOUZHOU C-343C-343 7507505 5LOULOU B-428B-428 850850v（2） 指針形式指針形式v如果記錄的長(zhǎng)度相差很大，那么可用指針形式實(shí)現(xiàn)變長(zhǎng)記錄如果記錄的長(zhǎng)度相差很大，那么可用指針形式實(shí)現(xiàn)變長(zhǎng)記錄的定長(zhǎng)表示形式。在每個(gè)記錄后加一個(gè)指針字段，圖的定長(zhǎng)表示形式。在每個(gè)記錄后加一個(gè)指針字段，圖6.5的文的文件可以用圖件可以用圖6.8來(lái)表示。來(lái)表示。v使

21、用改進(jìn)的指針形式，在一個(gè)文件中使用兩種塊，固定塊和使用改進(jìn)的指針形式，在一個(gè)文件中使用兩種塊，固定塊和溢出塊。圖溢出塊。圖6.9表示文件的固定塊和溢出塊結(jié)構(gòu)。表示文件的固定塊和溢出塊結(jié)構(gòu)。18圖圖6.8 變長(zhǎng)記錄的變長(zhǎng)記錄的指針表示方式指針表示方式6.1.2 變長(zhǎng)記錄（變長(zhǎng)記錄（8）圖圖6.9 固定塊和固定塊和溢出塊的結(jié)構(gòu)溢出塊的結(jié)構(gòu)固固定定塊塊0LIUA-102 6001WENB-306 7002HEF-257 8003 ZHANGA-214 6004 ZHOU C-343 7505B-215 8006LOUB-428 8507B-467 6008C-333 400溢溢出出塊塊LIULIU

22、A-102A-102 600600WENWEN B-306B-306 700700HEHEF-257F-257 800800ZHANGZHANGA-214A-214 600600ZHOUZHOU C-343C-343 750750LOULOU B-428B-428 850850B-215B-215 800800C-333C-333 400400B-467B-467 600600196.2 文件結(jié)構(gòu)文件結(jié)構(gòu) v6.2.1 四種文件結(jié)構(gòu)四種文件結(jié)構(gòu)v6.2.2 順序文件順序文件v6.2.3 聚集文件聚集文件20v文件結(jié)構(gòu)主要有下列四種形式：文件結(jié)構(gòu)主要有下列四種形式：v（1）堆文件（）堆文件（he

23、ap file）記錄可以放在文件的任何位置上。一般，以輸入順序?yàn)橛涗浛梢苑旁谖募娜魏挝恢蒙稀Ｒ话?，以輸入順序?yàn)樾?。記錄的存?chǔ)順序與關(guān)鍵碼沒(méi)有直接的聯(lián)系。刪除操作只序。記錄的存儲(chǔ)順序與關(guān)鍵碼沒(méi)有直接的聯(lián)系。刪除操作只是加個(gè)刪除標(biāo)志，新插入記錄總是在文件尾。是加個(gè)刪除標(biāo)志，新插入記錄總是在文件尾。v（2）順序文件（）順序文件（sequential file）記錄是按查找鍵值升序或降序的順序存儲(chǔ)的。記錄是按查找鍵值升序或降序的順序存儲(chǔ)的。v（3）散列文件（）散列文件（hashing file）據(jù)記錄的某個(gè)屬性值通過(guò)散列函數(shù)求得的值作為記錄的據(jù)記錄的某個(gè)屬性值通過(guò)散列函數(shù)求得的值作為記錄的存儲(chǔ)地址（

24、即存儲(chǔ)地址（即“塊號(hào)塊號(hào)”）。這個(gè)技術(shù)通常與索引技術(shù)連用。）。這個(gè)技術(shù)通常與索引技術(shù)連用。v（4）聚集文件（）聚集文件（clustering file）一個(gè)文件可以存儲(chǔ)多個(gè)關(guān)系的記錄。不同關(guān)系中有聯(lián)系一個(gè)文件可以存儲(chǔ)多個(gè)關(guān)系的記錄。不同關(guān)系中有聯(lián)系的記錄存儲(chǔ)在同一塊內(nèi)，可以提高查找速度和的記錄存儲(chǔ)在同一塊內(nèi)，可以提高查找速度和I / O速度。速度。v本節(jié)介紹順序文件和聚集文件，散列文件在本節(jié)介紹順序文件和聚集文件，散列文件在6.4節(jié)中介紹。節(jié)中介紹。6.2.1 四種文件結(jié)構(gòu)四種文件結(jié)構(gòu)21v根據(jù)查找鍵的值的順序存儲(chǔ)記根據(jù)查找鍵的值的順序存儲(chǔ)記錄的文件稱為順序文件。在文錄的文件稱為順序文件。在文

25、件中，每個(gè)記錄增加一個(gè)指針件中，每個(gè)記錄增加一個(gè)指針字段，根據(jù)查找鍵值的大小用字段，根據(jù)查找鍵值的大小用指針把記錄鏈接起來(lái)。指針把記錄鏈接起來(lái)。v文件初始建立時(shí)，存儲(chǔ)記錄盡文件初始建立時(shí)，存儲(chǔ)記錄盡可能使物理順序和查找鍵值的可能使物理順序和查找鍵值的順序一致。順序一致。v圖圖6.10是順序文件的例子，記是順序文件的例子，記錄按錄按ENAME值升序排列。順值升序排列。順序文件可以很方便地按查找鍵序文件可以很方便地按查找鍵的值的大小順序讀出所有的記的值的大小順序讀出所有的記錄。錄。6.2.2 順序文件（順序文件（1）HEHE F-257F-257 800800LIULIU A-102A-102 6

26、00600LIULIU B-215B-215 800800LIULIU C-333C-333 400400LOULOU B-428B-428 850850WENWEN B-306B-306 700700ZHANGZHANGA-214A-214 600600ZHANGZHANGB-467B-467 600600ZHOUZHOU C-343C-343 750750圖圖6.10 順序文件順序文件22v刪除操作可以通過(guò)修改指針實(shí)刪除操作可以通過(guò)修改指針實(shí)現(xiàn)，被刪記錄鏈接成一個(gè)自由現(xiàn)，被刪記錄鏈接成一個(gè)自由空間，以便插入時(shí)使用?？臻g，以便插入時(shí)使用。v插入操作包括定位和插入兩步：插入操作包括定位和插入兩

27、步：v（1）定位：在指針鏈中，找）定位：在指針鏈中，找到插入的位置，即插入記錄應(yīng)到插入的位置，即插入記錄應(yīng)插在哪個(gè)記錄的前面。插在哪個(gè)記錄的前面。v（2）插入：在找到記錄的塊）插入：在找到記錄的塊內(nèi)，如果有空閑記錄，那么在內(nèi)，如果有空閑記錄，那么在該位置插入新記錄，并加入到該位置插入新記錄，并加入到指針鏈中；如果無(wú)空閑記錄，指針鏈中；如果無(wú)空閑記錄，那么就只能插入到溢出塊中。那么就只能插入到溢出塊中。v在圖在圖6.10中，插入一個(gè)新記錄中，插入一個(gè)新記錄（MA，B-547，500），就得），就得到圖到圖6.11。6.2.2 順序文件（順序文件（2）HEF-257 800LIUA-102 600

28、LIUB-215 800LIUC-333 400LOUB-428 850WEN B-306 700ZHANGA-214 600ZHANGB-467 600ZHOU C-343 750MAB-547 500圖圖6.11 插入一個(gè)記錄插入一個(gè)記錄后的順序文件后的順序文件23v在小型在小型DBS中，數(shù)據(jù)量小，每個(gè)關(guān)系處理成一個(gè)文件。這種中，數(shù)據(jù)量小，每個(gè)關(guān)系處理成一個(gè)文件。這種文件稱為單記錄類型文件，文件中每個(gè)記錄都是定長(zhǎng)的。文文件稱為單記錄類型文件，文件中每個(gè)記錄都是定長(zhǎng)的。文件之間是分離的，沒(méi)有聯(lián)系。件之間是分離的，沒(méi)有聯(lián)系。v隨著數(shù)據(jù)量的增大，系統(tǒng)的性能和查詢速度日益下降。此時(shí)隨著數(shù)據(jù)量的增大

29、，系統(tǒng)的性能和查詢速度日益下降。此時(shí)應(yīng)采用新的文件結(jié)構(gòu)，稱為應(yīng)采用新的文件結(jié)構(gòu)，稱為“聚集文件聚集文件”。這種變化允許一。這種變化允許一個(gè)文件由多個(gè)關(guān)系的記錄組成，即多記錄類型文件。聚集文個(gè)文件由多個(gè)關(guān)系的記錄組成，即多記錄類型文件。聚集文件的管理由件的管理由DBS實(shí)現(xiàn)。實(shí)現(xiàn)。v例如教學(xué)數(shù)據(jù)庫(kù)中關(guān)系例如教學(xué)數(shù)據(jù)庫(kù)中關(guān)系S（SNO，SNAME，AGE，SEX）和）和SC（SNO，CNO，SCORE），如果將每個(gè)關(guān)系組織成一個(gè)），如果將每個(gè)關(guān)系組織成一個(gè)文件，那么查找學(xué)生的成績(jī)，就要做連接操作：文件，那么查找學(xué)生的成績(jī)，就要做連接操作：SELECT S.SNO，SNAME，CNO，GRADEFRO

30、M S，SCWHERE S.SNO = SC.SNO；6.2.3 聚集文件（聚集文件（1）24v在圖在圖6.12中，關(guān)系中，關(guān)系S和和SC如圖（如圖（a）、（）、（b）所示，）所示，S和和SC的的元組混合放在一起，如圖（元組混合放在一起，如圖（c）所示。即使一個(gè)學(xué)生的成績(jī)）所示。即使一個(gè)學(xué)生的成績(jī)信息很多，一塊訪不下，那么也是放在相鄰的塊內(nèi)。為了進(jìn)信息很多，一塊訪不下，那么也是放在相鄰的塊內(nèi)。為了進(jìn)一步提高查詢速度，我們可以在文件中建立以查詢學(xué)生信息一步提高查詢速度，我們可以在文件中建立以查詢學(xué)生信息為主的鏈表，在圖為主的鏈表，在圖6.12的（的（c）中已表示。）中已表示。6.2.3 聚集文件

31、（聚集文件（2）S1 WANG 20 MS1 C1 80S1 WANG 20 MS2LIU21 FS1 C2 70S1C180S3 CHEN 22 MS3 C1 90S1C270S3 C2 85S2LIU21 FS3 C3 95S3 CHEN 22 MS3C190S3C285S3C395（a）關(guān)系）關(guān)系S （b）關(guān)系）關(guān)系SC 圖圖6.12 聚集文件例子聚集文件例子（c）聚集文件）聚集文件 256.3 索引技術(shù)索引技術(shù)v6.3.1 索引機(jī)制索引機(jī)制v6.3.2 有序索引的分類有序索引的分類v6.3.3 主索引主索引v6.3.4 輔助索引輔助索引v6.3.5 B+樹(shù)索引文件樹(shù)索引文件v6.3.6

32、 B樹(shù)索引文件樹(shù)索引文件26v根據(jù)記錄中某種排序順序建立的索引，稱為有序索引。根據(jù)記錄中某種排序順序建立的索引，稱為有序索引。v在索引技術(shù)中，用戶可根據(jù)下面五個(gè)方面選擇各種實(shí)現(xiàn)方法：在索引技術(shù)中，用戶可根據(jù)下面五個(gè)方面選擇各種實(shí)現(xiàn)方法： 存取類型：用戶是根據(jù)屬性值找記錄，還是根據(jù)屬性值的范存取類型：用戶是根據(jù)屬性值找記錄，還是根據(jù)屬性值的范圍找記錄。圍找記錄。 存取時(shí)間；查找記錄所花費(fèi)的時(shí)間。存取時(shí)間；查找記錄所花費(fèi)的時(shí)間。 插入時(shí)間；插入新記錄所花費(fèi)的時(shí)間，應(yīng)包括兩部份，找到插入時(shí)間；插入新記錄所花費(fèi)的時(shí)間，應(yīng)包括兩部份，找到正確的位置插入新記錄所花時(shí)間和修改索引結(jié)構(gòu)所花時(shí)間。正確的位置插入

33、新記錄所花時(shí)間和修改索引結(jié)構(gòu)所花時(shí)間。 刪除時(shí)間；也應(yīng)包括兩部分，找到被刪記錄刪除所花時(shí)間和刪除時(shí)間；也應(yīng)包括兩部分，找到被刪記錄刪除所花時(shí)間和修改索引結(jié)構(gòu)所花時(shí)間。修改索引結(jié)構(gòu)所花時(shí)間。 索引空間開(kāi)銷。索引空間開(kāi)銷。v在索引中，用于找記錄的屬性集稱為查找鍵。應(yīng)注意，查找在索引中，用于找記錄的屬性集稱為查找鍵。應(yīng)注意，查找鍵不一定是主鍵（候選鍵、超鍵），前者的值允許重復(fù)，而鍵不一定是主鍵（候選鍵、超鍵），前者的值允許重復(fù)，而后者的值不允許重復(fù)。后者的值不允許重復(fù)。6.3.1 索引機(jī)制索引機(jī)制27v索引文件由兩個(gè)部分組成：索引和主文件。由于主文件記錄索引文件由兩個(gè)部分組成：索引和主文件。由于主文

34、件記錄多、數(shù)據(jù)量大并且占據(jù)大量物理塊，因此在主文件中查找，多、數(shù)據(jù)量大并且占據(jù)大量物理塊，因此在主文件中查找，速度是很慢的。如果對(duì)記錄建立索引，那么相對(duì)主文件而言，速度是很慢的。如果對(duì)記錄建立索引，那么相對(duì)主文件而言，索引空間小，因而查找速度就快。索引空間小，因而查找速度就快。v這里考慮的主文件是指順序文件，文件按某個(gè)屬性值大小的這里考慮的主文件是指順序文件，文件按某個(gè)屬性值大小的順序排列。對(duì)主文件可以建立幾套不同的索引。順序排列。對(duì)主文件可以建立幾套不同的索引。v如果索引的查找鍵值的順序與主文件的順序一致，那么這種如果索引的查找鍵值的順序與主文件的順序一致，那么這種索引稱為主索引，也稱為聚集

35、索引。一般，主索引的查找鍵索引稱為主索引，也稱為聚集索引。一般，主索引的查找鍵往往是文件的主鍵。往往是文件的主鍵。v如果查找鍵的值的順序與主文件的順序不一致，那么這種索如果查找鍵的值的順序與主文件的順序不一致，那么這種索引稱為輔助索引，或非聚集索引。引稱為輔助索引，或非聚集索引。6.3.2 有序索引的分類有序索引的分類28v當(dāng)索引查找鍵值的順序與主文件順序一致時(shí)，這種索引文件當(dāng)索引查找鍵值的順序與主文件順序一致時(shí)，這種索引文件稱為稱為“索引順序文件索引順序文件”。這種文件既適用隨機(jī)處理，也適用。這種文件既適用隨機(jī)處理，也適用順序處理。下面以圖順序處理。下面以圖6.10的順序文件為例介紹主索引以

36、及稠的順序文件為例介紹主索引以及稠密索引、稀疏索引和多級(jí)索引三種實(shí)現(xiàn)方法。密索引、稀疏索引和多級(jí)索引三種實(shí)現(xiàn)方法。v1稠密索引和稀疏索引稠密索引和稀疏索引v對(duì)于主索引，可以采用下面兩種實(shí)現(xiàn)方法：對(duì)于主索引，可以采用下面兩種實(shí)現(xiàn)方法：v（1） 稠密索引（稠密索引（dense index）：對(duì)于主文件中每一個(gè)查找）：對(duì)于主文件中每一個(gè)查找鍵值建立一個(gè)索引記錄（索引項(xiàng)），索引記錄包括查找鍵值鍵值建立一個(gè)索引記錄（索引項(xiàng)），索引記錄包括查找鍵值和指向具有該值的記錄鏈表中第一個(gè)記錄的指針。這種索引和指向具有該值的記錄鏈表中第一個(gè)記錄的指針。這種索引稱為稱為“稠密索引稠密索引”。讀者應(yīng)注意，在有些教材中稠

37、密索引定。讀者應(yīng)注意，在有些教材中稠密索引定義為對(duì)主文件中每個(gè)記錄建立一個(gè)索引記錄，與我們的提法義為對(duì)主文件中每個(gè)記錄建立一個(gè)索引記錄，與我們的提法有區(qū)別。有區(qū)別。v圖圖6.13是為圖是為圖6.10的順序文件建立的稠密索引。的順序文件建立的稠密索引。6.3.3 主索引（主索引（1）296.3.3 主索引（主索引（2）圖圖6.13 稠密索引稠密索引HELIULOUWENZHANGZHOUHEF-257 800LIUA-102 600LIUB-215 800LIUC-333 400LOUB-428 850WENB-306 700ZHANG A-214 600ZHANG B-467 600ZHOU

38、C-343 750306.3.3 主索引（主索引（3）v（2） 稀疏索引（稀疏索引（sparse index）：在主文件中，對(duì)若干個(gè)）：在主文件中，對(duì)若干個(gè)查找鍵值才建立一個(gè)索引記錄，此時(shí)索引記錄的內(nèi)容仍和查找鍵值才建立一個(gè)索引記錄，此時(shí)索引記錄的內(nèi)容仍和稠密索引一樣。這種索引稱為稠密索引一樣。這種索引稱為“稀疏索引稀疏索引”。v圖圖6.14為圖為圖6.10的順序文件建立的稀疏索引。的順序文件建立的稀疏索引。HELOUZHANGHEF-257 800LIUA-102 600LIUB-215 800LIUC-333 400LOUB-428 850WENB-306 700ZHANGA-214 60

39、0ZHANG B-467 600ZHOU C-343 750圖圖6.14 稀疏索引稀疏索引31v相比之下，在帶稠密索引的主文件中，查找速度較快；而帶相比之下，在帶稠密索引的主文件中，查找速度較快；而帶稀疏索引的文件中查找較慢，但稀疏索引的空間較小，因此稀疏索引的文件中查找較慢，但稀疏索引的空間較小，因此插入、刪除操作時(shí)指針的維護(hù)量相對(duì)要少些。插入、刪除操作時(shí)指針的維護(hù)量相對(duì)要少些。v系統(tǒng)設(shè)計(jì)者應(yīng)在存取時(shí)間和空間開(kāi)銷方面權(quán)衡，選擇何種索系統(tǒng)設(shè)計(jì)者應(yīng)在存取時(shí)間和空間開(kāi)銷方面權(quán)衡，選擇何種索引。有一個(gè)折衷的辦法，可把兩種索引結(jié)合起來(lái)。引。有一個(gè)折衷的辦法，可把兩種索引結(jié)合起來(lái)。v首先為順序文件的每一

40、塊建立一個(gè)索引記錄，得到一個(gè)以塊首先為順序文件的每一塊建立一個(gè)索引記錄，得到一個(gè)以塊為基本單位的稠密索引，然后再在稠密索引基礎(chǔ)上建立一個(gè)為基本單位的稠密索引，然后再在稠密索引基礎(chǔ)上建立一個(gè)稀疏索引。查找時(shí)，先在稀疏索引中找到記錄所在的范圍，稀疏索引。查找時(shí)，先在稀疏索引中找到記錄所在的范圍，然后在稠密索引中確定記錄在哪一塊，最后在主文件的塊中然后在稠密索引中確定記錄在哪一塊，最后在主文件的塊中順序查找，找到所在的主記錄。這種方法實(shí)際已是二級(jí)索引順序查找，找到所在的主記錄。這種方法實(shí)際已是二級(jí)索引了。了。6.3.3 主索引（主索引（4）32v2多級(jí)索引多級(jí)索引v即使采用稀疏索引，可能建成的索引還

41、是很大，以即使采用稀疏索引，可能建成的索引還是很大，以至于查詢效率不高。至于查詢效率不高。v解決這個(gè)問(wèn)題的方法是對(duì)主索引再建立一級(jí)稀疏索解決這個(gè)問(wèn)題的方法是對(duì)主索引再建立一級(jí)稀疏索引。即對(duì)每個(gè)索引塊建立一個(gè)索引記錄（如圖引。即對(duì)每個(gè)索引塊建立一個(gè)索引記錄（如圖6.15所所示）。示）。v圖圖6.15是一個(gè)二級(jí)索引例子。此時(shí)外層索引塊可常駐是一個(gè)二級(jí)索引例子。此時(shí)外層索引塊可常駐內(nèi)存，在找記錄時(shí)內(nèi)層索引塊只要讀內(nèi)存，在找記錄時(shí)內(nèi)層索引塊只要讀1次就行。如果次就行。如果外層索引塊的數(shù)目太多，不能全部進(jìn)內(nèi)存，那么可外層索引塊的數(shù)目太多，不能全部進(jìn)內(nèi)存，那么可對(duì)最外層索引再往外建一層索引。這就形成了多級(jí)

42、對(duì)最外層索引再往外建一層索引。這就形成了多級(jí)索引技術(shù)。索引技術(shù)。6.3.3 主索引（主索引（5）336.3.3 主索引（主索引（6）圖圖6.15 二級(jí)稀疏索引二級(jí)稀疏索引外層索引外層索引內(nèi)層索引內(nèi)層索引索引塊索引塊0數(shù)據(jù)塊數(shù)據(jù)塊0索引塊索引塊1數(shù)據(jù)塊數(shù)據(jù)塊134v3索引的更新：在索引文件中，主記錄的插入或刪除可能會(huì)索引的更新：在索引文件中，主記錄的插入或刪除可能會(huì)引起索引的修改。在只有一級(jí)的索引中索引的修改算法如下引起索引的修改。在只有一級(jí)的索引中索引的修改算法如下所述。所述。v（1） 刪除操作刪除操作為了在主文件中刪除一個(gè)記錄，首先要找到被刪記錄，才為了在主文件中刪除一個(gè)記錄，首先要找到被刪

43、記錄，才能執(zhí)行刪除操作。能執(zhí)行刪除操作。如果符合查找鍵值的記錄在文件中只有一個(gè)，那么被刪記如果符合查找鍵值的記錄在文件中只有一個(gè)，那么被刪記錄刪除后，肯定要修改索引。錄刪除后，肯定要修改索引。如果要修改索引，對(duì)于稠密索引，要從索引中刪除被刪記如果要修改索引，對(duì)于稠密索引，要從索引中刪除被刪記錄相應(yīng)的索引記錄；對(duì)于稀疏索引，如果被刪記錄的查找鍵錄相應(yīng)的索引記錄；對(duì)于稀疏索引，如果被刪記錄的查找鍵值在索引塊中出現(xiàn)，那么用主文件中被刪記錄的下一個(gè)主記值在索引塊中出現(xiàn)，那么用主文件中被刪記錄的下一個(gè)主記錄的查找鍵值錄的查找鍵值A(chǔ)替換，如果替換，如果A已在索引塊中出現(xiàn)，那么被刪記已在索引塊中出現(xiàn)，那么被

44、刪記錄的相應(yīng)索引記錄應(yīng)從索引塊中刪除。錄的相應(yīng)索引記錄應(yīng)從索引塊中刪除。6.3.3 主索引（主索引（7）35v（2） 插入操作插入操作首先，用插入記錄的查找鍵值找到插入位置。首先，用插入記錄的查找鍵值找到插入位置。 如果是稠密索引并且查找鍵值在索引塊中未出現(xiàn)過(guò)，那么如果是稠密索引并且查找鍵值在索引塊中未出現(xiàn)過(guò)，那么要把插入記錄的查找鍵值插入到索引塊中。要把插入記錄的查找鍵值插入到索引塊中。 如果是稀疏索引，每一個(gè)數(shù)據(jù)塊對(duì)應(yīng)一個(gè)索引記錄，那么如果是稀疏索引，每一個(gè)數(shù)據(jù)塊對(duì)應(yīng)一個(gè)索引記錄，那么在數(shù)據(jù)塊能放得下新記錄時(shí)，不必修改索引。如果要加入新在數(shù)據(jù)塊能放得下新記錄時(shí)，不必修改索引。如果要加入新的

45、數(shù)據(jù)塊，那么插入記錄的查找鍵值將成為新數(shù)據(jù)塊的第一的數(shù)據(jù)塊，那么插入記錄的查找鍵值將成為新數(shù)據(jù)塊的第一個(gè)查找鍵值，并將在索引塊中插入一個(gè)新的索引記錄。個(gè)查找鍵值，并將在索引塊中插入一個(gè)新的索引記錄。v在多級(jí)索引時(shí)在多級(jí)索引時(shí),可以采取類似的辦法。在插入、刪除主記錄時(shí)，可以采取類似的辦法。在插入、刪除主記錄時(shí)，最低一級(jí)索引的修改方法如上所述。如果第二級(jí)索引（外層）最低一級(jí)索引的修改方法如上所述。如果第二級(jí)索引（外層）要修改，那么把第一級(jí)索引（內(nèi)層）看成順序文件。在第一要修改，那么把第一級(jí)索引（內(nèi)層）看成順序文件。在第一級(jí)索引中插入或刪除一個(gè)索引記錄時(shí)，第二級(jí)索引的修改也級(jí)索引中插入或刪除一個(gè)索引

46、記錄時(shí)，第二級(jí)索引的修改也像上面敘述的方法一樣。以此類推。像上面敘述的方法一樣。以此類推。6.3.3 主索引（主索引（8）36v在主索引中，我們可以方便、快速地根據(jù)某個(gè)查找鍵值找記在主索引中，我們可以方便、快速地根據(jù)某個(gè)查找鍵值找記錄。如果我們要根據(jù)另一個(gè)查找鍵值尋找主文件的記錄，那錄。如果我們要根據(jù)另一個(gè)查找鍵值尋找主文件的記錄，那么可以用輔助索引方法實(shí)現(xiàn)。么可以用輔助索引方法實(shí)現(xiàn)。v在主索引中，具有相同查找鍵值的記錄在同一塊中或相鄰的在主索引中，具有相同查找鍵值的記錄在同一塊中或相鄰的塊中，因而查找速度較快。而在輔助索引中，具有相同查找塊中，因而查找速度較快。而在輔助索引中，具有相同查找鍵

47、值的記錄將分散在文件的各處，因而查找速度較慢，并且鍵值的記錄將分散在文件的各處，因而查找速度較慢，并且查找時(shí)無(wú)法利用主文件中按主索引鍵值建立的指針鏈。查找時(shí)無(wú)法利用主文件中按主索引鍵值建立的指針鏈。v輔助索引可采用下面的方法實(shí)現(xiàn)：仍然為每個(gè)查找鍵值建立輔助索引可采用下面的方法實(shí)現(xiàn)：仍然為每個(gè)查找鍵值建立一個(gè)索引記錄，內(nèi)容包括查找鍵值和一個(gè)指針。但這個(gè)指針一個(gè)索引記錄，內(nèi)容包括查找鍵值和一個(gè)指針。但這個(gè)指針不指向主文件中的記錄，而是指向一個(gè)桶（不指向主文件中的記錄，而是指向一個(gè)桶（bucket），桶內(nèi)），桶內(nèi)存放指向具有同一查找鍵值的主記錄的指針。例如在圖存放指向具有同一查找鍵值的主記錄的指針。

48、例如在圖6.10的順序文件中，可以對(duì)屬性的順序文件中，可以對(duì)屬性SALARY建立一個(gè)輔助索引，其建立一個(gè)輔助索引，其結(jié)構(gòu)如圖結(jié)構(gòu)如圖6.16所示。所示。6.3.4 輔助索引（輔助索引（1）376.3.4 輔助索引（輔助索引（2）圖圖6.16 輔助索引例子輔助索引例子400600700750800850HEF-257 800LIUA-102 600LIUB-215 800LIUC-333 400LOUB-428 850WENB-306 700ZHANG A-214 600ZHANG B-467 600ZHOU C-343 75038v在主索引中可以采取順序查找方法。在輔助索引中，由于同在主索引中

49、可以采取順序查找方法。在輔助索引中，由于同一個(gè)查找鍵值的記錄分散在文件的各處，因此以輔助索引查一個(gè)查找鍵值的記錄分散在文件的各處，因此以輔助索引查找鍵順序掃描文件是行不通的，每讀一個(gè)記錄幾乎都要執(zhí)行找鍵順序掃描文件是行不通的，每讀一個(gè)記錄幾乎都要執(zhí)行讀一塊到內(nèi)存的操作。讀一塊到內(nèi)存的操作。v輔助索引都是稠密索引，不可能是稀疏索引結(jié)構(gòu)。在主記錄輔助索引都是稠密索引，不可能是稀疏索引結(jié)構(gòu)。在主記錄插入或刪除時(shí)，都要修改輔助索引，修改的方法與主索引的插入或刪除時(shí)，都要修改輔助索引，修改的方法與主索引的方法類似。方法類似。v輔助索引機(jī)制曾在輔助索引機(jī)制曾在20世紀(jì)世紀(jì)60年代中期廣泛流行，倒排文件系年

50、代中期廣泛流行，倒排文件系統(tǒng)就是建立了許多輔助索引的文件系統(tǒng)。輔助索引改善了系統(tǒng)就是建立了許多輔助索引的文件系統(tǒng)。輔助索引改善了系統(tǒng)的查詢效率和查詢方式，但是也給系統(tǒng)帶來(lái)很大的負(fù)擔(dān)。統(tǒng)的查詢效率和查詢方式，但是也給系統(tǒng)帶來(lái)很大的負(fù)擔(dān)。數(shù)據(jù)庫(kù)應(yīng)用設(shè)計(jì)者應(yīng)在查詢效率和修改的代價(jià)方面作出權(quán)衡，數(shù)據(jù)庫(kù)應(yīng)用設(shè)計(jì)者應(yīng)在查詢效率和修改的代價(jià)方面作出權(quán)衡，以選擇合適的索引結(jié)構(gòu)。以選擇合適的索引結(jié)構(gòu)。6.3.4 輔助索引（輔助索引（3）39v1平衡樹(shù)的概念平衡樹(shù)的概念v為了改善索引結(jié)構(gòu)的性能，可以采用多級(jí)索引，目前廣泛流為了改善索引結(jié)構(gòu)的性能，可以采用多級(jí)索引，目前廣泛流行的一種技術(shù)，稱為平衡樹(shù)（行的一種技術(shù)，

51、稱為平衡樹(shù)（Balanced tree）技術(shù)。數(shù)據(jù)庫(kù)）技術(shù)。數(shù)據(jù)庫(kù)技術(shù)中平衡樹(shù)的形式定義如下所述。技術(shù)中平衡樹(shù)的形式定義如下所述。v定義定義6.1 一棵一棵m階平衡樹(shù)或者為空，或者滿足以下條件：階平衡樹(shù)或者為空，或者滿足以下條件： 每個(gè)結(jié)點(diǎn)至多有每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)；棵子樹(shù)； 根結(jié)點(diǎn)或?yàn)槿~結(jié)點(diǎn)，或至少有兩棵子樹(shù)；根結(jié)點(diǎn)或?yàn)槿~結(jié)點(diǎn)，或至少有兩棵子樹(shù)； 每個(gè)非葉結(jié)點(diǎn)至少有每個(gè)非葉結(jié)點(diǎn)至少有 m/2 棵子樹(shù)；棵子樹(shù)； 從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的每一條路徑都有同樣的長(zhǎng)度，即從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的每一條路徑都有同樣的長(zhǎng)度，即 葉結(jié)點(diǎn)在同一層次上。葉結(jié)點(diǎn)在同一層次上。v平衡樹(shù)又分為兩類：平衡樹(shù)又分為兩類：B+樹(shù)和樹(shù)

52、和B樹(shù)。下面先介紹樹(shù)。下面先介紹B+樹(shù)。樹(shù)。6.3.5 B+樹(shù)索引文件（樹(shù)索引文件（1）406.3.5 B+樹(shù)索引文件（樹(shù)索引文件（2）v2B+樹(shù)的結(jié)構(gòu)樹(shù)的結(jié)構(gòu)在實(shí)際使用中，在實(shí)際使用中，B+樹(shù)有很多形式，下面介紹其中的一種。樹(shù)有很多形式，下面介紹其中的一種。v一棵一棵m階階B+樹(shù)是平衡樹(shù)，按下列方式組織：樹(shù)是平衡樹(shù)，按下列方式組織：（1） 每個(gè)結(jié)點(diǎn)中至多有每個(gè)結(jié)點(diǎn)中至多有m-1個(gè)查找鍵值個(gè)查找鍵值K1，K2，Km-1，m個(gè)指針個(gè)指針P1，P2，Pm，如圖，如圖6.17所示。所示。P1K1P2Pm-1Km-1Pm圖圖6.17 B+樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)41v（2） 葉結(jié)點(diǎn)的組織方式葉結(jié)點(diǎn)的組

53、織方式v葉結(jié)點(diǎn)中的指針（葉結(jié)點(diǎn)中的指針（1im-1）指向主文件中的記錄。譬如指針）指向主文件中的記錄。譬如指針Pi指向查找鍵值為指向查找鍵值為Ki的主記錄。的主記錄。v如果查找鍵恰好是主文件的主鍵，那么葉結(jié)點(diǎn)中的指針直接如果查找鍵恰好是主文件的主鍵，那么葉結(jié)點(diǎn)中的指針直接指向主文件中的記錄。如果查找鍵不是主文件的主鍵，并且指向主文件中的記錄。如果查找鍵不是主文件的主鍵，并且查找鍵值的順序也不是主文件的順序，那么葉結(jié)點(diǎn)中的指針查找鍵值的順序也不是主文件的順序，那么葉結(jié)點(diǎn)中的指針指向一個(gè)桶，桶中存放指向具有該查找鍵值的主記錄的指針。指向一個(gè)桶，桶中存放指向具有該查找鍵值的主記錄的指針。v每個(gè)葉結(jié)點(diǎn)

54、中至少應(yīng)有每個(gè)葉結(jié)點(diǎn)中至少應(yīng)有 （m-1）/2 個(gè)查找鍵，至多有個(gè)查找鍵，至多有m-1個(gè)查找鍵，并且查找鍵值不允許重復(fù)。如果個(gè)查找鍵，并且查找鍵值不允許重復(fù)。如果B+樹(shù)索引是稠密樹(shù)索引是稠密索引，那么每個(gè)查找鍵值必須在某個(gè)葉結(jié)點(diǎn)中出現(xiàn)。索引，那么每個(gè)查找鍵值必須在某個(gè)葉結(jié)點(diǎn)中出現(xiàn)。v葉結(jié)點(diǎn)中最后一個(gè)指針葉結(jié)點(diǎn)中最后一個(gè)指針Pm，指向下一個(gè)葉結(jié)點(diǎn)（按查找鍵值，指向下一個(gè)葉結(jié)點(diǎn)（按查找鍵值順序）。這樣可以很方便地在主文件進(jìn)行順序訪問(wèn)。順序）。這樣可以很方便地在主文件進(jìn)行順序訪問(wèn)。v圖圖6.18表示表示3階階B+樹(shù)的葉結(jié)點(diǎn)結(jié)構(gòu)。樹(shù)的葉結(jié)點(diǎn)結(jié)構(gòu)。6.3.5 B+樹(shù)索引文件（樹(shù)索引文件（3）426.3.

55、5 B+樹(shù)索引文件（樹(shù)索引文件（4）圖圖6.18 3階階B+樹(shù)的樹(shù)的葉結(jié)點(diǎn)結(jié)構(gòu)葉結(jié)點(diǎn)結(jié)構(gòu)葉結(jié)點(diǎn)葉結(jié)點(diǎn)HELIUHEF-257800LIUA-102600LIUB-215800LIUC-333400下一個(gè)葉結(jié)點(diǎn)下一個(gè)葉結(jié)點(diǎn)主文件主文件v（3） 非葉結(jié)點(diǎn)的組織方式非葉結(jié)點(diǎn)的組織方式B+樹(shù)中的非葉結(jié)點(diǎn)形成了葉結(jié)點(diǎn)上的一個(gè)多級(jí)稀樹(shù)中的非葉結(jié)點(diǎn)形成了葉結(jié)點(diǎn)上的一個(gè)多級(jí)稀疏索引。每個(gè)非葉結(jié)點(diǎn)（不包括根結(jié)點(diǎn)）中至少有疏索引。每個(gè)非葉結(jié)點(diǎn)（不包括根結(jié)點(diǎn)）中至少有 m/2 個(gè)個(gè)指針，至多有指針，至多有m個(gè)指針。指針的數(shù)目稱為結(jié)點(diǎn)的個(gè)指針。指針的數(shù)目稱為結(jié)點(diǎn)的“扇出端數(shù)扇出端數(shù)”（fanout）。圖）。圖6.19

56、是一個(gè)完整的是一個(gè)完整的3階階B+樹(shù)索引。圖樹(shù)索引。圖6.20是一個(gè)是一個(gè)5階階B+樹(shù)索引的例子。樹(shù)索引的例子。43圖圖6.19 3階階B+樹(shù)索引樹(shù)索引6.3.5 B+樹(shù)索引文件（樹(shù)索引文件（5）圖圖6.20 5階階B+樹(shù)索引樹(shù)索引WENHELIULOUWEN ZHANG ZHOUZHANGLOUWENHELIULOUWENZHANGZHOU44v3B+樹(shù)的查詢樹(shù)的查詢v如果用戶要檢索查找鍵值為如果用戶要檢索查找鍵值為K的所有記錄，那么首先在根結(jié)的所有記錄，那么首先在根結(jié)點(diǎn)中找大于點(diǎn)中找大于K的最小查找鍵值（設(shè)為的最小查找鍵值（設(shè)為Ki），然后沿著），然后沿著Ki左邊的左邊的指針指針Pi到達(dá)第

57、二層的結(jié)點(diǎn)。如果根結(jié)點(diǎn)中有到達(dá)第二層的結(jié)點(diǎn)。如果根結(jié)點(diǎn)中有n個(gè)指針，并且個(gè)指針，并且KKn-1，那么就沿著指針，那么就沿著指針Pn到達(dá)第二層的結(jié)點(diǎn)。在第二層的結(jié)到達(dá)第二層的結(jié)點(diǎn)。在第二層的結(jié)點(diǎn)，用類似的方法找到一個(gè)指針，進(jìn)入第三層的結(jié)點(diǎn)點(diǎn)，用類似的方法找到一個(gè)指針，進(jìn)入第三層的結(jié)點(diǎn)一一直到進(jìn)入直到進(jìn)入B+樹(shù)的葉結(jié)點(diǎn)，找到一個(gè)指針直接指向主文件的記樹(shù)的葉結(jié)點(diǎn)，找到一個(gè)指針直接指向主文件的記錄，或指向一個(gè)桶（存放指向主文件記錄的指針）。最后把錄，或指向一個(gè)桶（存放指向主文件記錄的指針）。最后把所需記錄找到。所需記錄找到。v如果文件中查找鍵值有如果文件中查找鍵值有W個(gè)值，那么對(duì)于個(gè)值，那么對(duì)于m階階

58、B+樹(shù)而言，從樹(shù)而言，從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長(zhǎng)度不超過(guò)根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長(zhǎng)度不超過(guò) log m/2 （W） 。6.3.5 B+樹(shù)索引文件（樹(shù)索引文件（6）45v例例6.2 討論討論B+樹(shù)索引查詢中查詢次數(shù)與文件的存儲(chǔ)塊數(shù)的關(guān)系。樹(shù)索引查詢中查詢次數(shù)與文件的存儲(chǔ)塊數(shù)的關(guān)系。如果在如果在B+樹(shù)索引中，每塊存儲(chǔ)一個(gè)結(jié)點(diǎn)，占樹(shù)索引中，每塊存儲(chǔ)一個(gè)結(jié)點(diǎn)，占4096字節(jié)。字節(jié)。如果查找鍵的長(zhǎng)度為如果查找鍵的長(zhǎng)度為32字節(jié)，指針仍為字節(jié)，指針仍為8字節(jié)，那么每塊大約字節(jié)，那么每塊大約可存儲(chǔ)可存儲(chǔ)100個(gè)查找鍵值和指針，即個(gè)查找鍵值和指針，即m約為約為100。在在m為為100時(shí)，如果文件中查找鍵有時(shí)，如果文

59、件中查找鍵有100萬(wàn)個(gè)值，那么一次萬(wàn)個(gè)值，那么一次查找需讀索引塊的數(shù)目為查找需讀索引塊的數(shù)目為 log50（1000000） =4。如果。如果B+樹(shù)索引的根結(jié)點(diǎn)常駐內(nèi)存，那么查找時(shí)只需再讀三個(gè)索引塊即樹(shù)索引的根結(jié)點(diǎn)常駐內(nèi)存，那么查找時(shí)只需再讀三個(gè)索引塊即可。可。 vB+樹(shù)的結(jié)構(gòu)與內(nèi)存中普遍使用的二叉排序樹(shù)的主要區(qū)別是結(jié)點(diǎn)樹(shù)的結(jié)構(gòu)與內(nèi)存中普遍使用的二叉排序樹(shù)的主要區(qū)別是結(jié)點(diǎn)的大小以及樹(shù)的高度。在二叉排序樹(shù)中，每個(gè)結(jié)點(diǎn)很小，只有的大小以及樹(shù)的高度。在二叉排序樹(shù)中，每個(gè)結(jié)點(diǎn)很小，只有一個(gè)鍵值和兩個(gè)指針。而一個(gè)鍵值和兩個(gè)指針。而B(niǎo)+樹(shù)中，每個(gè)結(jié)點(diǎn)很大，可以是磁盤(pán)樹(shù)中，每個(gè)結(jié)點(diǎn)很大，可以是磁盤(pán)上的一個(gè)塊

60、，包含更多查找鍵值和指針。二叉排序樹(shù)顯得瘦而上的一個(gè)塊，包含更多查找鍵值和指針。二叉排序樹(shù)顯得瘦而高，而高，而B(niǎo)+樹(shù)顯得胖而矮。樹(shù)顯得胖而矮。6.3.5 B+樹(shù)索引文件（樹(shù)索引文件（7）46v4B+樹(shù)的更新樹(shù)的更新在在B+樹(shù)索引文件中插入主記錄時(shí)，有可能葉結(jié)點(diǎn)要分裂，樹(shù)索引文件中插入主記錄時(shí)，有可能葉結(jié)點(diǎn)要分裂，并引起上層結(jié)點(diǎn)的分裂和并引起上層結(jié)點(diǎn)的分裂和B+樹(shù)層數(shù)的增加。在刪除主記錄時(shí)，樹(shù)層數(shù)的增加。在刪除主記錄時(shí)，這有可能出現(xiàn)相反的現(xiàn)象。下面就是否出現(xiàn)分裂與合并情況這有可能出現(xiàn)相反的現(xiàn)象。下面就是否出現(xiàn)分裂與合并情況分別討論。分別討論。v（1）不引起索引結(jié)點(diǎn)分裂的插入操作）不引起索引結(jié)點(diǎn)分