1、1第第 六六 章章 數(shù)據(jù)庫的存儲結(jié)構(gòu)數(shù)據(jù)庫的存儲結(jié)構(gòu)2 3 根據(jù)訪問數(shù)據(jù)的速度、成本和可靠根據(jù)訪問數(shù)據(jù)的速度、成本和可靠性，計算機系統(tǒng)的存儲介質(zhì)可以分為性，計算機系統(tǒng)的存儲介質(zhì)可以分為以下六類：以下六類：1 1、高速緩沖存儲器、高速緩沖存儲器2 2、主存儲器、主存儲器3 3、快擦寫存儲器、快擦寫存儲器4 4、磁盤存儲器、磁盤存儲器5 5、光存儲器、光存儲器6 6、磁帶、磁帶高速緩存高速緩存主存主存快閃存儲器快閃存儲器磁盤存儲器磁盤存儲器光存儲器光存儲器磁帶存儲器磁帶存儲器存儲器設(shè)備層次存儲器設(shè)備層次4 磁盤是一種大容量的可直接存取的外部存磁盤是一種大容量的可直接存取的外部存儲設(shè)備。所謂儲設(shè)備。

2、所謂直接存取直接存取是指可以隨機到達(dá)磁是指可以隨機到達(dá)磁盤上的任何一個部位存取其中的數(shù)據(jù)。盤上的任何一個部位存取其中的數(shù)據(jù)。移動頭磁盤示意圖561 1、硬磁盤的總?cè)萘渴牵?、硬磁盤的總?cè)萘渴牵?記錄盤面數(shù)目記錄盤面數(shù)目每記錄盤面的磁每記錄盤面的磁道數(shù)道數(shù)每磁道的盤塊數(shù)每磁道的盤塊數(shù)每盤塊的字每盤塊的字節(jié)數(shù)節(jié)數(shù) 這樣，一個數(shù)據(jù)存在磁盤上需要這樣，一個數(shù)據(jù)存在磁盤上需要的三個定位信息：的三個定位信息： 柱面號柱面號 磁頭號磁頭號 盤塊號盤塊號72 2、編址、編址 柱面從外向內(nèi)從柱面從外向內(nèi)從0 0開始依次編號，開始依次編號，磁道按柱面編號，盤塊號根據(jù)磁道號磁道按柱面編號，盤塊號根據(jù)磁道號統(tǒng)一編址。統(tǒng)

3、一編址。3 3、格式化、格式化 在各個盤塊的塊頭部位加注該塊在各個盤塊的塊頭部位加注該塊地址，包括該塊所在的地址，包括該塊所在的柱面號、磁頭柱面號、磁頭號和盤塊號以及某些狀態(tài)標(biāo)志號和盤塊號以及某些狀態(tài)標(biāo)志。84 4、磁盤的性能指標(biāo)、磁盤的性能指標(biāo) 磁盤的性能指標(biāo)可用四個參數(shù)衡量：磁盤的性能指標(biāo)可用四個參數(shù)衡量：磁盤磁盤的容量，存取時間，數(shù)據(jù)傳輸速度和可靠性。的容量，存取時間，數(shù)據(jù)傳輸速度和可靠性。（1 1）磁盤容量隨技術(shù)的發(fā)展而變化；）磁盤容量隨技術(shù)的發(fā)展而變化；（2 2）存取時間指從發(fā)出讀、寫請求到數(shù)據(jù)傳輸）存取時間指從發(fā)出讀、寫請求到數(shù)據(jù)傳輸開始這一段時間。由磁頭定位時間和旋轉(zhuǎn)延開始這一段

4、時間。由磁頭定位時間和旋轉(zhuǎn)延遲時間組成。一般在遲時間組成。一般在1040ms1040ms之間。之間。（3 3）數(shù)據(jù)傳輸速度是指在磁盤上讀寫數(shù)據(jù)的速）數(shù)據(jù)傳輸速度是指在磁盤上讀寫數(shù)據(jù)的速度，每秒可達(dá)度，每秒可達(dá)15MB15MB；（4 4）可靠性是指磁盤的故障率，一般在）可靠性是指磁盤的故障率，一般在3838萬小萬小時（時（3.43.4到到9.19.1年）內(nèi)不出故障。年）內(nèi)不出故障。95 5、內(nèi)外存間的數(shù)據(jù)交換、內(nèi)外存間的數(shù)據(jù)交換 數(shù)據(jù)庫運行時，內(nèi)外存間要頻繁的進行數(shù)據(jù)交換，數(shù)據(jù)庫運行時，內(nèi)外存間要頻繁的進行數(shù)據(jù)交換，每交換一次數(shù)據(jù)就稱為一次每交換一次數(shù)據(jù)就稱為一次I/OI/O操作。在數(shù)據(jù)庫中最操

5、作。在數(shù)據(jù)庫中最終是調(diào)用操作系統(tǒng)這一功能的。終是調(diào)用操作系統(tǒng)這一功能的。（1 1）交換單位：交換單位：一次一個數(shù)據(jù)塊，可以是一個或幾個磁一次一個數(shù)據(jù)塊，可以是一個或幾個磁盤塊；盤塊；（2 2）組塊方式：組塊方式：不跨塊方式不跨塊方式跨塊方式跨塊方式（3 3）由數(shù)據(jù)庫的設(shè)計者決定由數(shù)據(jù)庫的設(shè)計者決定106 6、磁盤冗余陣列（、磁盤冗余陣列（RAIDRAID）（1 1）產(chǎn)生原因：）產(chǎn)生原因：早期早期小磁盤成本低小磁盤成本低現(xiàn)在現(xiàn)在提高磁盤系統(tǒng)的性能和數(shù)據(jù)存儲提高磁盤系統(tǒng)的性能和數(shù)據(jù)存儲的可靠性的可靠性（2 2）通過）通過“冗余冗余”改善可靠性改善可靠性 最簡單的冗余方法是復(fù)式存儲，也稱為鏡像最簡單

6、的冗余方法是復(fù)式存儲，也稱為鏡像技術(shù)。技術(shù)。（3 3）通過）通過“并行并行”提高數(shù)據(jù)傳輸速度提高數(shù)據(jù)傳輸速度 常見的有常見的有“位級拆存技術(shù)位級拆存技術(shù)”和和“塊級拆存技塊級拆存技術(shù)術(shù)”。111 1、光盤、光盤（1 1）存儲容量大，從）存儲容量大，從500M500M到到17G17G左右左右（2 2）成本低）成本低（3 3）運行性能低于磁盤）運行性能低于磁盤（4 4）部分種類可讀寫）部分種類可讀寫2 2、磁帶、磁帶（1 1）容量大）容量大（2 2）存取速度慢）存取速度慢（3 3）作為輔助存儲器）作為輔助存儲器（4 4）可靠性好，一般作為數(shù)據(jù)轉(zhuǎn)換的脫機介質(zhì)使用）可靠性好，一般作為數(shù)據(jù)轉(zhuǎn)換的脫機介質(zhì)

7、使用12 13 例如：對于關(guān)系模式例如：對于關(guān)系模式EMPEMP（ENAMEENAME，ENOENO，SALARYSALARY）可以設(shè)計一個文件，記錄格式如下：可以設(shè)計一個文件，記錄格式如下： TYPE EMP_TYPE=RECORDTYPE EMP_TYPE=RECORD ENAME:CHAR(10); ENAME:CHAR(10); ENO:CHAR(10); ENO:CHAR(10); SALARY:REAL; SALARY:REAL; END; END; 假設(shè)一個實數(shù)占假設(shè)一個實數(shù)占8 8個字節(jié)，那么每個記錄占個字節(jié)，那么每個記錄占2828個字節(jié)。在系統(tǒng)運行時，有兩個問題：個字節(jié)。在系

8、統(tǒng)運行時，有兩個問題：（1 1）如果要刪除一個記錄，必須在被刪位置填補上）如果要刪除一個記錄，必須在被刪位置填補上一個記錄，或者設(shè)法使文件忽略該位置；一個記錄，或者設(shè)法使文件忽略該位置；（2 2）記錄有可能橫跨兩個塊。）記錄有可能橫跨兩個塊。141 1、刪除操作時的考慮、刪除操作時的考慮（1 1）把被刪除記錄后面的記錄依次移上去；）把被刪除記錄后面的記錄依次移上去；（2 2）把文件中最后一個記錄填補到被刪除位置；）把文件中最后一個記錄填補到被刪除位置；（3 3）把被刪除結(jié)點用指針鏈接起來）把被刪除結(jié)點用指針鏈接起來 在每個記錄中增加一個指針，在文件中增在每個記錄中增加一個指針，在文件中增設(shè)一個

9、文件首部。文件首部中包括文件中的設(shè)一個文件首部。文件首部中包括文件中的有關(guān)信息，其中有一個指針指向第一個被刪有關(guān)信息，其中有一個指針指向第一個被刪除記錄位置，所有被刪結(jié)點用指針鏈接，構(gòu)除記錄位置，所有被刪結(jié)點用指針鏈接，構(gòu)成一個棧結(jié)構(gòu)的空閑記錄鏈表。成一個棧結(jié)構(gòu)的空閑記錄鏈表。152 2、插入操作時的考慮、插入操作時的考慮 如果采用把被刪記錄鏈接起來的方法，如果采用把被刪記錄鏈接起來的方法，那么插入操作可采用下列方法：那么插入操作可采用下列方法：（1 1）在空閑記錄鏈表的第一個空閑記錄）在空閑記錄鏈表的第一個空閑記錄中，填上插入記錄的值，同時使首部中，填上插入記錄的值，同時使首部指針指向下一個

10、空閑記錄；指針指向下一個空閑記錄；（2 2）如果空閑記錄鏈表為空，那么只能）如果空閑記錄鏈表為空，那么只能把新記錄插到文件尾。把新記錄插到文件尾。16 一個文件中存儲了多種不同的記錄類型一個文件中存儲了多種不同的記錄類型記錄；文件中允許記錄類型的記錄是變長的；記錄；文件中允許記錄類型的記錄是變長的；允許記錄中某個字段可以出現(xiàn)重復(fù)組等。這允許記錄中某個字段可以出現(xiàn)重復(fù)組等。這些都是變長記錄格式。些都是變長記錄格式。 上例文件中的記錄也可以設(shè)計成變長的。上例文件中的記錄也可以設(shè)計成變長的。 TYPE EMP_LIST=RECORDTYPE EMP_LIST=RECORD ENAME:CHAR(10

11、); ENAME:CHAR(10); ENO_INFO:ARRAY1 OF ENO_INFO:ARRAY1 OF RECORD RECORD ENO:CHAR(10); ENO:CHAR(10); SALARY:REAL; SALARY:REAL; END END END END17變長記錄的表示有變長記錄的表示有字節(jié)串形式字節(jié)串形式和和定長形式定長形式兩種。兩種。1 1、變長記錄的字節(jié)串表示形式、變長記錄的字節(jié)串表示形式（1 1）把每個記錄看成是連續(xù)的字節(jié)串，然后在）把每個記錄看成是連續(xù)的字節(jié)串，然后在每個記錄的尾部附加每個記錄的尾部附加“記錄尾部標(biāo)志符記錄尾部標(biāo)志符”。（2 2）在記錄的開

12、始加一個記錄長度的字段來實）在記錄的開始加一個記錄長度的字段來實現(xiàn)?，F(xiàn)。B-125600A-102LIU700A-103WUB-123650A-104LI18缺點：缺點：（1 1）由于各記錄的長度不一，因此被刪記錄的）由于各記錄的長度不一，因此被刪記錄的位置難于重新使用。即使制定很多技術(shù)規(guī)則，位置難于重新使用。即使制定很多技術(shù)規(guī)則，仍然會導(dǎo)致磁盤中出現(xiàn)大量小的空間浪費。仍然會導(dǎo)致磁盤中出現(xiàn)大量小的空間浪費。（2 2）如果文件中的記錄要伸長，很難實現(xiàn)。所）如果文件中的記錄要伸長，很難實現(xiàn)。所以，現(xiàn)在實際中一般使用一種改進的字節(jié)串以，現(xiàn)在實際中一般使用一種改進的字節(jié)串表示形式，稱為表示形式，稱為“

13、分槽式頁結(jié)構(gòu)分槽式頁結(jié)構(gòu)”。19分槽式頁結(jié)構(gòu)：分槽式頁結(jié)構(gòu)： 在每塊的開始處設(shè)置一個在每塊的開始處設(shè)置一個“塊首部塊首部”，包，包含下列信息：含下列信息：（1 1）塊中記錄數(shù)目）塊中記錄數(shù)目（2 2）指向塊中自由空間尾部的指針）指向塊中自由空間尾部的指針（3 3）登記每個記錄的開始位置和大小信息）登記每個記錄的開始位置和大小信息 20分槽式頁結(jié)構(gòu)分槽式頁結(jié)構(gòu)記錄大小記錄大小記錄位置記錄位置記錄數(shù)目記錄數(shù)目自由空間塊首部塊首部指向自由空間尾部指向自由空間尾部212 2、變長記錄的定長表示形式、變長記錄的定長表示形式預(yù)留空間法預(yù)留空間法取所有變長記錄中最長的一個記錄的長度取所有變長記錄中最長的一個

14、記錄的長度作為存儲空間的記錄長度，來存儲變長記錄。作為存儲空間的記錄長度，來存儲變長記錄。1LIUA-102600B-1048002WENB-103750/3LIC-104800/4CAID-105600/5WangE-201800C-3066506Zhang F-304700/222 2、變長記錄的定長表示形式、變長記錄的定長表示形式指針形式指針形式在每個記錄的后面加一個指針字段，用在每個記錄的后面加一個指針字段，用來連接同一類的記錄來連接同一類的記錄1LIUA-10260052WENB-103750/3LIC-10480064CAID-105600/5/E-201800#6/F-30470

15、0#23改進的指針形式：分為固定塊和溢出塊改進的指針形式：分為固定塊和溢出塊1LIUA-10260052WENB-103750/3LIC-10480064CAID-105600/5E-201800#6F-304700#24251 1、堆文件、堆文件記錄可以放在文件的任何位置上，記錄可以放在文件的任何位置上，一般以輸入順序為主一般以輸入順序為主刪除操作只是加個刪除標(biāo)志，新插刪除操作只是加個刪除標(biāo)志，新插入記錄總是在文件尾入記錄總是在文件尾2 2、順序文件、順序文件記錄是按查找鍵值升序或降序的順記錄是按查找鍵值升序或降序的順序存儲序存儲263 3、散列文件、散列文件據(jù)記錄的某個屬性值通過散列函數(shù)求

16、據(jù)記錄的某個屬性值通過散列函數(shù)求得的值作為記錄的存儲地址（既得的值作為記錄的存儲地址（既“塊塊號號”）。這種技術(shù)通常與索引技術(shù)連）。這種技術(shù)通常與索引技術(shù)連用。用。4 4、聚集文件、聚集文件一個文件可以存儲多個關(guān)系的記錄一個文件可以存儲多個關(guān)系的記錄不同關(guān)系中有聯(lián)系的記錄存儲在同一不同關(guān)系中有聯(lián)系的記錄存儲在同一塊內(nèi)，可以提高查找速度和塊內(nèi)，可以提高查找速度和I/OI/O速度。速度。27 根據(jù)查找鍵的值的順序存儲記錄的根據(jù)查找鍵的值的順序存儲記錄的文件稱為順序文件。文件稱為順序文件。 在文件中，根據(jù)查找鍵的大小用指在文件中，根據(jù)查找鍵的大小用指針把記錄鏈接起來。針把記錄鏈接起來。刪除：刪除：可

17、以通過修改指針來實現(xiàn)可以通過修改指針來實現(xiàn)28插入：插入：定位：在指針鏈中，找到插入的位置（按定位：在指針鏈中，找到插入的位置（按照鍵的順序）照鍵的順序）插入：在找到記錄的塊內(nèi)，先看自由空間插入：在找到記錄的塊內(nèi)，先看自由空間有無空閑，如有，則插入，并加入到指針有無空閑，如有，則插入，并加入到指針鏈中；如沒有，則只能插入到溢出塊中鏈中；如沒有，則只能插入到溢出塊中盡量維持物理順序和查找鍵值的順序一盡量維持物理順序和查找鍵值的順序一致，以提高查找速度致，以提高查找速度29 允許一個文件由多個關(guān)系組成，既多記允許一個文件由多個關(guān)系組成，既多記錄類型文件。錄類型文件。 例如：教學(xué)數(shù)據(jù)庫中，學(xué)生和成績

18、記錄例如：教學(xué)數(shù)據(jù)庫中，學(xué)生和成績記錄屬于兩個關(guān)系，如果他們的數(shù)據(jù)量很大，那屬于兩個關(guān)系，如果他們的數(shù)據(jù)量很大，那么做聯(lián)結(jié)查詢速度很慢。如果把這些數(shù)據(jù)全么做聯(lián)結(jié)查詢速度很慢。如果把這些數(shù)據(jù)全部放在一個文件中，并且盡可能把每個學(xué)生部放在一個文件中，并且盡可能把每個學(xué)生的信息和其成績信息放在相鄰的位置上，那的信息和其成績信息放在相鄰的位置上，那么在讀學(xué)生信息時，能夠把學(xué)生信息和連在么在讀學(xué)生信息時，能夠把學(xué)生信息和連在一起的成績信息一次讀到內(nèi)存中。一起的成績信息一次讀到內(nèi)存中。30聚類文件聚類文件3132（1 1）有序索引：）有序索引：根據(jù)記錄中某種排序順序建立根據(jù)記錄中某種排序順序建立的索引；的

19、索引；（2 2）散列索引：）散列索引：根據(jù)記錄中的某個屬性值，通根據(jù)記錄中的某個屬性值，通過散列函數(shù)得到的函數(shù)值，作為存儲空間的過散列函數(shù)得到的函數(shù)值，作為存儲空間的地址。地址。 選取何種實現(xiàn)方法，可以參考以下幾個方面：選取何種實現(xiàn)方法，可以參考以下幾個方面：存取類型存取類型存取時間存取時間插入時間插入時間刪除時間刪除時間索引空間開銷索引空間開銷33 索引文件由兩個成分組成：索引文件由兩個成分組成：索引和主文件索引和主文件。 索引分兩類：索引分兩類：（1 1）如果索引的查找鍵值的順序與主文件的順）如果索引的查找鍵值的順序與主文件的順序一致，那么這種索引稱為主索引，也稱為序一致，那么這種索引稱為

20、主索引，也稱為“聚類索引聚類索引”；（2 2）如果查找鍵的值的順序與主文件的順序不）如果查找鍵的值的順序與主文件的順序不一致，那么這種索引稱為一致，那么這種索引稱為輔助索引輔助索引，或，或“非非聚類索引聚類索引”。34（1 1）稠密索引）稠密索引 對于主文件中每一個查找鍵值建立一個索對于主文件中每一個查找鍵值建立一個索引記錄，索引記錄包括查找鍵值和指向具有引記錄，索引記錄包括查找鍵值和指向具有該值的記錄鏈表中第一個記錄的指針；該值的記錄鏈表中第一個記錄的指針；（2 2）稀疏索引）稀疏索引 在主文件中，若干個查找鍵的值才建立一在主文件中，若干個查找鍵的值才建立一個索引記錄。個索引記錄。35稀疏索

21、引稀疏索引1HeF-12880022LIUA-10260033WENB-10375044LIC-10480055CAID-10560066DongE-20180077QiaoF-304700#He1Wen 3Cai536（3 3）多級索引）多級索引如果索引塊數(shù)多，那么可以為索引塊再建立一級稀疏索如果索引塊數(shù)多，那么可以為索引塊再建立一級稀疏索引，即對每個索引塊建立一個索引記錄。引，即對每個索引塊建立一個索引記錄。為了查找記錄，可以在外層索引使用二分法查找，找到為了查找記錄，可以在外層索引使用二分法查找，找到一個索引記錄，該索引記錄的查找鍵值小于或等于給出一個索引記錄，該索引記錄的查找鍵值小于或

22、等于給出查找鍵值的最大一個鍵值；然后沿著索引記錄中的指針查找鍵值的最大一個鍵值；然后沿著索引記錄中的指針到達(dá)內(nèi)層索引塊；在內(nèi)層索引塊可用順序查找或二分查到達(dá)內(nèi)層索引塊；在內(nèi)層索引塊可用順序查找或二分查找也可找到相應(yīng)的索引記錄；然后沿著這個索引記錄中找也可找到相應(yīng)的索引記錄；然后沿著這個索引記錄中的指針到達(dá)主文件的某個數(shù)據(jù)塊；在數(shù)據(jù)塊中沿著指針的指針到達(dá)主文件的某個數(shù)據(jù)塊；在數(shù)據(jù)塊中沿著指針鏈查找記錄。鏈查找記錄。37多級索引多級索引數(shù)據(jù)塊數(shù)據(jù)塊0 0數(shù)據(jù)塊數(shù)據(jù)塊1 1數(shù)據(jù)塊數(shù)據(jù)塊n-1n-1數(shù)據(jù)塊數(shù)據(jù)塊n n索引塊索引塊1 1索引塊索引塊0 0外層索引外層索引38（4 4）索引更新）索引更新刪

23、除操作刪除操作找到被刪記錄，如果被刪除的記錄在文找到被刪記錄，如果被刪除的記錄在文件中只有一個，那么刪除后肯定要修改索件中只有一個，那么刪除后肯定要修改索引引對于稠密索引，要刪除相應(yīng)的索引記錄；對于稠密索引，要刪除相應(yīng)的索引記錄；對于稀疏索引，如果被刪記錄的查找鍵對于稀疏索引，如果被刪記錄的查找鍵值在索引塊中出現(xiàn)，那么用下一個鍵值替值在索引塊中出現(xiàn)，那么用下一個鍵值替換，如果下一個鍵值在索引中存在，那么換，如果下一個鍵值在索引中存在，那么刪除相應(yīng)的索引記錄刪除相應(yīng)的索引記錄39（4 4）索引更新）索引更新插入操作插入操作用插入記錄的查找鍵值找到插入位置用插入記錄的查找鍵值找到插入位置對于稠密索

24、引，如果沒有該鍵值，則插對于稠密索引，如果沒有該鍵值，則插入到索引塊中入到索引塊中對于稀疏索引，如果當(dāng)前數(shù)據(jù)塊能放下對于稀疏索引，如果當(dāng)前數(shù)據(jù)塊能放下新記錄，則不必修改索引；如果要插入新新記錄，則不必修改索引；如果要插入新的數(shù)據(jù)塊，那么插入記錄的查找鍵值將成的數(shù)據(jù)塊，那么插入記錄的查找鍵值將成為新數(shù)據(jù)塊的第一個查找鍵值，并在索引為新數(shù)據(jù)塊的第一個查找鍵值，并在索引塊中插入一個新的索引記錄。塊中插入一個新的索引記錄。40可以根據(jù)另一個查找鍵值尋找主文件的記錄可以根據(jù)另一個查找鍵值尋找主文件的記錄實現(xiàn)方法：實現(xiàn)方法： 仍然為每個查找鍵值建立一個索引記錄，內(nèi)仍然為每個查找鍵值建立一個索引記錄，內(nèi)容包

25、括查找鍵值和一個指針，指針指向一個容包括查找鍵值和一個指針，指針指向一個桶，桶內(nèi)存放指向具有同一查找鍵值的主記桶，桶內(nèi)存放指向具有同一查找鍵值的主記錄的指針。錄的指針。41輔助索引輔助索引2800F-128H-105CAI7800E-201Dong#700F-304Qiao5800C-104LI4750B-103WEN3600A-102LIU800750700600桶桶421 1、平衡樹的概念、平衡樹的概念定義定義6.1 6.1 一棵一棵m m階平衡樹或者為空，或者滿足以階平衡樹或者為空，或者滿足以 下條件：下條件： 每個結(jié)點至多有每個結(jié)點至多有m m棵子樹；棵子樹；

26、 根結(jié)點或為葉結(jié)點，或至少有兩棵子樹；根結(jié)點或為葉結(jié)點，或至少有兩棵子樹； 每個非葉結(jié)點至少有每個非葉結(jié)點至少有m/2m/2棵子樹；棵子樹； 從根結(jié)點到葉結(jié)點的每一條路徑都有同從根結(jié)點到葉結(jié)點的每一條路徑都有同樣的長度，即葉結(jié)點在同一層次上。樣的長度，即葉結(jié)點在同一層次上。 平衡樹又分兩類：平衡樹又分兩類： B B 樹和樹和B B樹樹432 2、B B 樹的結(jié)構(gòu)樹的結(jié)構(gòu) 在實際使用中，在實際使用中，B B 樹有很多形式，下面介紹其中樹有很多形式，下面介紹其中的一種。的一種。一棵一棵m m階階B B 樹是平衡樹，按下列方式組織：樹是平衡樹，按下列方式組織： 1) 1) 每個結(jié)點中至多有每個結(jié)點中

27、至多有m-1m-1個查找鍵值個查找鍵值K K1 1,K,K2 2,K,KM-1M-1, , m m個指針個指針P P1 1,P,P2 2,P,PM M , ,如圖所示。如圖所示。 2 2）葉結(jié)點的組織方式）葉結(jié)點的組織方式 葉結(jié)點中的指針（葉結(jié)點中的指針（1=i=m-11=iKKKn-1n-1，那么就沿著，那么就沿著指針指針P Pn n到達(dá)第二層的結(jié)點。重復(fù)此方法直到進入到達(dá)第二層的結(jié)點。重復(fù)此方法直到進入葉結(jié)點，找到一個指針直接指向主文件的記錄，葉結(jié)點，找到一個指針直接指向主文件的記錄，或指向一個桶，最后把所需記錄找到?；蛑赶蛞粋€桶，最后把所需記錄找到。454 4、 B B 樹的更新樹的更新

28、 在在B B 樹索引文件中的插入、刪除操作要比查找復(fù)樹索引文件中的插入、刪除操作要比查找復(fù)雜的多。在插入主記錄，有可能葉結(jié)點要分裂，雜的多。在插入主記錄，有可能葉結(jié)點要分裂，并引起上層結(jié)點的分裂和并引起上層結(jié)點的分裂和B B 樹層數(shù)的增加。在刪樹層數(shù)的增加。在刪除主記錄時，則有可能出現(xiàn)相反的現(xiàn)象。除主記錄時，則有可能出現(xiàn)相反的現(xiàn)象。 1 1）不引起索引結(jié)點分裂的插入操作）不引起索引結(jié)點分裂的插入操作 2 2）不引起索引結(jié)點合并的刪除操作）不引起索引結(jié)點合并的刪除操作 3 3）引起索引結(jié)點分裂的插入操作）引起索引結(jié)點分裂的插入操作 4 4）引起索引結(jié)點合并的刪除操作）引起索引結(jié)點合并的刪除操作4

29、64 4、 B B 樹文件組織樹文件組織 對對B B 樹索引文件組織作進一步的演變，使得樹索引文件組織作進一步的演變，使得B B 樹樹葉結(jié)點不存儲指向主記錄的指針，而是直接存儲葉結(jié)點不存儲指向主記錄的指針，而是直接存儲記錄本身，那么這種結(jié)構(gòu)稱為記錄本身，那么這種結(jié)構(gòu)稱為“B B 樹文件組織樹文件組織”。 B B 樹文件組織的插入、刪除操作與樹文件組織的插入、刪除操作與B B 樹索引記錄樹索引記錄的插入和刪除操作是一樣的，也有可能會引起結(jié)的插入和刪除操作是一樣的，也有可能會引起結(jié)點的分裂或合并，層數(shù)的增加或減少。點的分裂或合并，層數(shù)的增加或減少。47B B樹索引類似于樹索引類似于B B 樹索引。

30、樹索引。 在在B B 樹中，每個查找鍵值都必須在葉結(jié)點中出樹中，每個查找鍵值都必須在葉結(jié)點中出 現(xiàn)，為了組織多級索引，某些查找鍵值還必須在上現(xiàn)，為了組織多級索引，某些查找鍵值還必須在上層結(jié)點中出現(xiàn)。層結(jié)點中出現(xiàn)。在在B B樹中，查找鍵值可以出現(xiàn)任何結(jié)點上，但只樹中，查找鍵值可以出現(xiàn)任何結(jié)點上，但只能出現(xiàn)一次。能出現(xiàn)一次。48491 1、散列概念、散列概念 根據(jù)記錄的查找鍵值，使用一個函數(shù)計算得到的根據(jù)記錄的查找鍵值，使用一個函數(shù)計算得到的函數(shù)值作為磁盤塊的地址，對記錄進行存儲和訪問，函數(shù)值作為磁盤塊的地址，對記錄進行存儲和訪問，這種方法稱為散列方法。這種方法稱為散列方法。定義定義6.2 6.2

31、 設(shè)設(shè)K K是所有查找鍵值的集合，是所有查找鍵值的集合，B B是所有桶地是所有桶地址的集合。散列函數(shù)址的集合。散列函數(shù)h h是從是從K K到到B B的一個函數(shù)，它把每的一個函數(shù)，它把每個查找鍵值映象到地址集合中的地址。個查找鍵值映象到地址集合中的地址。刪除操作是很方便的，先用查找方法把記錄找到，刪除操作是很方便的，先用查找方法把記錄找到，然后直接然后直接 從桶內(nèi)刪去即可。從桶內(nèi)刪去即可。502 2、散列函數(shù)、散列函數(shù) 散列函數(shù)在把查找鍵值轉(zhuǎn)換成存儲地址（桶號）散列函數(shù)在把查找鍵值轉(zhuǎn)換成存儲地址（桶號）時，應(yīng)滿足兩個條件：時，應(yīng)滿足兩個條件： 1 1）地址的分布是均勻的：把所有可能的查找鍵）地址的分布是均勻的：把所有可能的查找鍵值轉(zhuǎn)換成桶號以后，要求每個桶內(nèi)的查找鍵值數(shù)目值轉(zhuǎn)換成桶號以后，要求每個桶內(nèi)的查找鍵值數(shù)目大抵相同。大抵相同。 2