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

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

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

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

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

5、的倍數(shù)，否則可能有的的倍數(shù)，否則可能有的記錄橫跨兩個塊。讀記錄橫跨兩個塊。讀 / 寫寫這樣的記錄就要訪問兩個這樣的記錄就要訪問兩個塊。塊。記錄記錄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 定長記錄的文件定長記錄的文件76.1.1 定長記錄（定長記錄（3）v1刪除操作時的考慮刪除操作時的考慮v刪除一個記錄，可采用下

6、面刪除一個記錄，可采用下面三種方法之一實現(xiàn)：三種方法之一實現(xiàn)：v（1） 把被刪記錄后的記錄把被刪記錄后的記錄一次移上來一次移上來v例如在圖例如在圖6.1中，要刪除記錄中，要刪除記錄2，那么要把記錄，那么要把記錄38依次移依次移上來，如圖上來，如圖6.2所示。這時刪所示。這時刪除一個記錄平均要移動文件除一個記錄平均要移動文件中的一半記錄。中的一半記錄。記錄記錄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 把被刪記錄后的把被刪記錄后的記錄依次移上來記錄依次移上來 86.1.1 定長記錄（定長記錄（4）v（2） 把文件中最后一把文件中最后一個記錄填補(bǔ)到被刪記錄個記錄填補(bǔ)到被刪記錄位置，如圖位置，如圖6.3所示。所示。v這兩種方法都要移動結(jié)這兩種方法都要移動結(jié)點(diǎn)，操作不靈活。由于點(diǎn)，操作不靈活。由于數(shù)據(jù)庫中刪除操作總是數(shù)據(jù)庫中刪除操作總是少于插入操作，因此我少于插入操作，因此我們可以采用下面方式實們可以采用下面方式實現(xiàn)?，F(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 把最后一個記錄把最后一個記錄填補(bǔ)到被刪記錄位置填補(bǔ)到被刪記錄位置9v（3） 把被刪結(jié)點(diǎn)用指針把被刪結(jié)點(diǎn)用指針鏈接起來鏈接起來v在每個記錄中增加一個指在每個記錄中增加一個指針，在文件中增設(shè)一個文針，在文件中增設(shè)一個文件首部。文件如圖件首部。文件如圖6.4所示。所示。v這種方式較好。但要注意，這種方式較好。但要注意，是否還有指針指向被刪記是否還有指針指向被刪記錄。在錄。在DB中，被指針指向中，被指針指向的記錄稱為的記錄

9、稱為“被拴記錄被拴記錄”。如果不小心把被拴記錄刪如果不小心把被拴記錄刪掉，那么指向該記錄的指掉，那么指向該記錄的指針成了針成了“懸掛指針懸掛指針”。懸。懸掛指針指向的空間稱為掛指針指向的空間稱為“垃圾垃圾”，即該空間別人，即該空間別人無法使用而又被空閑著。無法使用而又被空閑著。6.1.1 定長記錄（定長記錄（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插入操作時的考慮插入操作時的考慮v如果采用把被刪記錄鏈接起來的方法，那么插入操如果采用把被刪記錄鏈接起來的方法，那么插入操作可采用下列方法：作可采用下列方法：v在空閑記錄鏈表的第一個空閑記錄中，填上插入記在空閑記錄鏈表的第一個空閑記錄中，填上插入記錄的值，同時使首部指針指向下一個空閑記錄；如錄的值，同時使首部指針指向下一個空閑記錄；如果空閑記錄鏈表為空，那么只能把新記錄插到文件果空閑記錄鏈表為空，那么只能把新記錄插到文件尾。尾。v定長記錄文件的插入操作比較簡單，因為插入記錄定長記錄文件的插入操作比較簡單，因為插入記錄的長度與被刪記錄的長度是相等的

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

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

13、錄的尾部附加個記錄的尾部附加“記錄尾標(biāo)識符記錄尾標(biāo)識符”（）。圖）。圖6.1的定長的定長記錄文件可以用圖記錄文件可以用圖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 變長記錄的字節(jié)串表示形式變長記錄的字節(jié)串表示形式13v字節(jié)串表現(xiàn)形式的另一種方式是在記錄的開始加一個記錄長字節(jié)串表現(xiàn)形式的另一種方式是在記錄的開始加一個記錄長度的字段來實現(xiàn)，而不是使用在記錄尾加標(biāo)志符的方法。度的

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

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

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

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

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

19、空間處填上某個特定的空值或記錄尾標(biāo)志符。例如圖個特定的空值或記錄尾標(biāo)志符。例如圖6.5的字節(jié)串的字節(jié)串表現(xiàn)形式可以用圖表現(xiàn)形式可以用圖6.7的預(yù)留空間方法實現(xiàn)。這方法的預(yù)留空間方法實現(xiàn)。這方法一般使用在大多數(shù)記錄的長度接近最大長度時才使一般使用在大多數(shù)記錄的長度接近最大長度時才使用，否則使用時空間浪費(fèi)很大。用，否則使用時空間浪費(fèi)很大。6.1.2 變長記錄（變長記錄（6）176.1.2 變長記錄（變長記錄（7）圖圖6.7 變長記錄變長記錄的預(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如果記錄的長度相差很大，那么可用指針形式實現(xiàn)變長記錄如果記錄的長度相差很大，那么可用指針形式實現(xiàn)變長記錄的定長表示形式。在每個記錄后加一個指針字段，圖的定長表示形式。在每個記錄后加一個指針字段，圖6.5的文的文件可以用圖件可以用圖6.8來表示。來表示。v使

21、用改進(jìn)的指針形式，在一個文件中使用兩種塊，固定塊和使用改進(jìn)的指針形式，在一個文件中使用兩種塊，固定塊和溢出塊。圖溢出塊。圖6.9表示文件的固定塊和溢出塊結(jié)構(gòu)。表示文件的固定塊和溢出塊結(jié)構(gòu)。18圖圖6.8 變長記錄的變長記錄的指針表示方式指針表示方式6.1.2 變長記錄（變長記錄（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）記錄可以放在文件的任何位置上。一般，以輸入順序為記錄可以放在文件的任何位置上。一般，以輸入順序為序。記錄的存儲順序與關(guān)鍵碼沒有直接的聯(lián)系。刪除操作只序。記錄的存儲順序與關(guān)鍵碼沒有直接的聯(lián)系。刪除操作只是加個刪除標(biāo)志，新插入記錄總是在文件尾。是加個刪除標(biāo)志，新插入記錄總是在文件尾。v（2）順序文件（）順序文件（sequential file）記錄是按查找鍵值升序或降序的順序存儲的。記錄是按查找鍵值升序或降序的順序存儲的。v（3）散列文件（）散列文件（hashing file）據(jù)記錄的某個屬性值通過散列函數(shù)求得的值作為記錄的據(jù)記錄的某個屬性值通過散列函數(shù)求得的值作為記錄的存儲地址（

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

25、件中，每個記錄增加一個指針件中，每個記錄增加一個指針字段，根據(jù)查找鍵值的大小用字段，根據(jù)查找鍵值的大小用指針把記錄鏈接起來。指針把記錄鏈接起來。v文件初始建立時，存儲記錄盡文件初始建立時，存儲記錄盡可能使物理順序和查找鍵值的可能使物理順序和查找鍵值的順序一致。順序一致。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刪除操作可以通過修改指針實刪除操作可以通過修改指針實現(xiàn)，被刪記錄鏈接成一個自由現(xiàn)，被刪記錄鏈接成一個自由空間，以便插入時使用?？臻g，以便插入時使用。v插入操作包括定位和插入兩步：插入操作包括定位和插入兩

27、步：v（1）定位：在指針鏈中，找）定位：在指針鏈中，找到插入的位置，即插入記錄應(yīng)到插入的位置，即插入記錄應(yīng)插在哪個記錄的前面。插在哪個記錄的前面。v（2）插入：在找到記錄的塊）插入：在找到記錄的塊內(nèi)，如果有空閑記錄，那么在內(nèi)，如果有空閑記錄，那么在該位置插入新記錄，并加入到該位置插入新記錄，并加入到指針鏈中；如果無空閑記錄，指針鏈中；如果無空閑記錄，那么就只能插入到溢出塊中。那么就只能插入到溢出塊中。v在圖在圖6.10中，插入一個新記錄中，插入一個新記錄（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 插入一個記錄插入一個記錄后的順序文件后的順序文件23v在小型在小型DBS中，數(shù)據(jù)量小，每個關(guān)系處理成一個文件。這種中，數(shù)據(jù)量小，每個關(guān)系處理成一個文件。這種文件稱為單記錄類型文件，文件中每個記錄都是定長的。文文件稱為單記錄類型文件，文件中每個記錄都是定長的。文件之間是分離的，沒有聯(lián)系。件之間是分離的，沒有聯(lián)系。v隨著數(shù)據(jù)量的增大，系統(tǒng)的性能和查詢速度日益下降。此時隨著數(shù)據(jù)量的增大

29、，系統(tǒng)的性能和查詢速度日益下降。此時應(yīng)采用新的文件結(jié)構(gòu)，稱為應(yīng)采用新的文件結(jié)構(gòu)，稱為“聚集文件聚集文件”。這種變化允許一。這種變化允許一個文件由多個關(guān)系的記錄組成，即多記錄類型文件。聚集文個文件由多個關(guān)系的記錄組成，即多記錄類型文件。聚集文件的管理由件的管理由DBS實現(xiàn)。實現(xiàn)。v例如教學(xué)數(shù)據(jù)庫中關(guān)系例如教學(xué)數(shù)據(jù)庫中關(guān)系S（SNO，SNAME，AGE，SEX）和）和SC（SNO，CNO，SCORE），如果將每個關(guān)系組織成一個），如果將每個關(guān)系組織成一個文件，那么查找學(xué)生的成績，就要做連接操作：文件，那么查找學(xué)生的成績，就要做連接操作：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）所示。即使一個學(xué)生的成績）所示。即使一個學(xué)生的成績信息很多，一塊訪不下，那么也是放在相鄰的塊內(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+樹索引文件樹索引文件v6.3.6

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

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

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

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

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

37、密索引定。讀者應(yīng)注意，在有些教材中稠密索引定義為對主文件中每個記錄建立一個索引記錄，與我們的提法義為對主文件中每個記錄建立一個索引記錄，與我們的提法有區(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）：在主文件中，對若干個）：在主文件中，對若干個查找鍵值才建立一個索引記錄，此時索引記錄的內(nèi)容仍和查找鍵值才建立一個索引記錄，此時索引記錄的內(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相比之下，在帶稠密索引的主文件中，查找速度較快；而帶相比之下，在帶稠密索引的主文件中，查找速度較快；而帶稀疏索引的文件中查找較慢，但稀疏索引的空間較小，因此稀疏索引的文件中查找較慢，但稀疏索引的空間較小，因此插入、刪除操作時指針的維護(hù)量相對要少些。插入、刪除操作時指針的維護(hù)量相對要少些。v系統(tǒng)設(shè)計者應(yīng)在存取時間和空間開銷方面權(quán)衡，選擇何種索系統(tǒng)設(shè)計者應(yīng)在存取時間和空間開銷方面權(quán)衡，選擇何種索引。有一個折衷的辦法，可把兩種索引結(jié)合起來。引。有一個折衷的辦法，可把兩種索引結(jié)合起來。v首先為順序文件的每一

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

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

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

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

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

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

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

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

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

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

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

52、和B樹。下面先介紹樹。下面先介紹B+樹。樹。6.3.5 B+樹索引文件（樹索引文件（1）406.3.5 B+樹索引文件（樹索引文件（2）v2B+樹的結(jié)構(gòu)樹的結(jié)構(gòu)在實際使用中，在實際使用中，B+樹有很多形式，下面介紹其中的一種。樹有很多形式，下面介紹其中的一種。v一棵一棵m階階B+樹是平衡樹，按下列方式組織：樹是平衡樹，按下列方式組織：（1） 每個結(jié)點(diǎn)中至多有每個結(jié)點(diǎn)中至多有m-1個查找鍵值個查找鍵值K1，K2，Km-1，m個指針個指針P1，P2，Pm，如圖，如圖6.17所示。所示。P1K1P2 Pm-1Km-1Pm圖圖6.17 B+樹的結(jié)點(diǎn)結(jié)構(gòu)樹的結(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)中的指針指向一個桶，桶中存放指向具有該查找鍵值的主記錄的指針。指向一個桶，桶中存放指向具有該查找鍵值的主記錄的指針。v每個葉結(jié)

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

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

56、9是一個完整的是一個完整的3階階B+樹索引。圖樹索引。圖6.20是一個是一個5階階B+樹索引的例子。樹索引的例子。43圖圖6.19 3階階B+樹索引樹索引6.3.5 B+樹索引文件（樹索引文件（5）圖圖6.20 5階階B+樹索引樹索引WENHELIULOUWEN ZHANG ZHOUZHANGLOUWENHELIULOUWENZHANGZHOU44v3B+樹的查詢樹的查詢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個指針，并且個指針，并且KKn-1，那么就沿著指針，那么就沿著指針Pn到達(dá)第二層的結(jié)點(diǎn)。在第二層的結(jié)到達(dá)第二層的結(jié)點(diǎn)。在第二層的結(jié)點(diǎn)，用類似的方法找到一個指針，進(jìn)入第三層的結(jié)點(diǎn)點(diǎn)，用類似的方法找到一個指針，進(jìn)入第三層的結(jié)點(diǎn)一一直到進(jìn)入直到進(jìn)入B+樹的葉結(jié)點(diǎn)，找到一個指針直接指向主文件的記樹的葉結(jié)點(diǎn)，找到一個指針直接指向主文件的記錄，或指向一個桶（存放指向主文件記錄的指針）。最后把錄，或指向一個桶（存放指向主文件記錄的指針）。最后把所需記錄找到。所需記錄找到。v如果文件中查找鍵值有如果文件中查找鍵值有W個值，那么對于個值，那么對于m階

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

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

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