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

1第6章DB的存儲(chǔ)結(jié)構(gòu)2第6章數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)6.1文件組織6.2文件結(jié)構(gòu)6.3索引技術(shù)6.4散列技術(shù)6.5多鍵訪問(wèn)6.6小結(jié)3 前言前面幾章，主要強(qiáng)調(diào)數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)。在關(guān)系模型中，我們把數(shù)據(jù)庫(kù)看成關(guān)系的匯集。數(shù)據(jù)庫(kù)系統(tǒng)的一個(gè)目標(biāo)是使用戶能簡(jiǎn)單、方便、容易地存取數(shù)據(jù)庫(kù)中的數(shù)據(jù)。用戶訪問(wèn)數(shù)據(jù)庫(kù)，不必關(guān)心數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)和具體的實(shí)現(xiàn)方式。但是，用戶如能了解數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)，那么對(duì)于數(shù)據(jù)庫(kù)就會(huì)有一個(gè)比較完整的了解，拓寬知識(shí)面。本章先介紹文件組織形式，然后介紹以及常用的索引組織和散列組織。46.1文件組織6.1.1定長(zhǎng)記錄6.1.2變長(zhǎng)記錄在外存中，數(shù)據(jù)庫(kù)以文件形式組織，而文件由記錄組成。文件結(jié)構(gòu)由操作系統(tǒng)的文件系統(tǒng)提供和管理。那么邏輯文件中的記錄在物理文件中將如何實(shí)現(xiàn)。這是本節(jié)所討論的問(wèn)題。一般，文件組織有兩種方式，一種是把記錄設(shè)計(jì)成定長(zhǎng)格式，另一種是變長(zhǎng)格式，下面分別討論。5為關(guān)系模式EMP（ENAME，ENO，SALARY）可以設(shè)計(jì)一個(gè)文件，記錄格式如下：

TYPEEMP_TYPE=RECORD ENAME：CHAR(10)；

ENO：CHAR(10)；

SALARY：REAL；

END假設(shè)一個(gè)實(shí)數(shù)占8個(gè)字節(jié)，那么每個(gè)記錄占28個(gè)字節(jié)。可以像圖6.1那樣把記錄依次組織起來(lái)。一個(gè)職工可以為幾個(gè)部門工作，因此可以有幾個(gè)工號(hào)。6.1.1定長(zhǎng)記錄（1）66.1.1定長(zhǎng)記錄（2）在系統(tǒng)運(yùn)行時(shí)，有兩個(gè)問(wèn)題需考慮：●如果要?jiǎng)h除一個(gè)記錄，那么必須在被刪位置上填補(bǔ)一個(gè)記錄，或者設(shè)法使文件忽略該位置?！癯敲繅K的大小恰好是28的倍數(shù)，否則可能有的記錄橫跨兩個(gè)塊。讀/寫這樣的記錄就要訪問(wèn)兩個(gè)塊。記錄0LIUA-102600記錄1WENB-306700記錄2HEF-257800記錄3ZHANGA-214600記錄4ZHOUC-343750記錄5LIUB-215800記錄6LOUB-428850記錄7ZHANGB-467600記錄8LIUC-333400圖6.1定長(zhǎng)記錄的文件76.1.1定長(zhǎng)記錄（3）1．刪除操作時(shí)的考慮刪除一個(gè)記錄，可采用下面三種方法之一實(shí)現(xiàn)：（1）把被刪記錄后的記錄一次移上來(lái)例如在圖6.1中，要?jiǎng)h除記錄2，那么要把記錄3～8依次移上來(lái)，如圖6.2所示。這時(shí)刪除一個(gè)記錄平均要移動(dòng)文件中的一半記錄。記錄0LIUA-102600記錄1WENB-306700記錄3ZHANGA-214600記錄4ZHOUC-343750記錄5LIUB-215800記錄6LOUB-428850記錄7ZHANGB-467600記錄8LIUC-333400圖6.2把被刪記錄后的記錄依次移上來(lái)

86.1.1定長(zhǎng)記錄（4）（2）把文件中最后一個(gè)記錄填補(bǔ)到被刪記錄位置，如圖6.3所示。這兩種方法都要移動(dòng)結(jié)點(diǎn)，操作不靈活。由于數(shù)據(jù)庫(kù)中刪除操作總是少于插入操作，因此我們可以采用下面方式實(shí)現(xiàn)。記錄0LIUA-102600記錄1WENB-306700記錄8LIUC-333400記錄3ZHANGA-214600記錄4ZHOUC-343750記錄5LIUB-215800記錄6LOUB-428850記錄7ZHANGB-467600圖6.3把最后一個(gè)記錄填補(bǔ)到被刪記錄位置9（3）把被刪結(jié)點(diǎn)用指針鏈接起來(lái)在每個(gè)記錄中增加一個(gè)指針，在文件中增設(shè)一個(gè)文件首部。文件如圖6.4所示。這種方式較好。但要注意，是否還有指針指向被刪記錄。在DB中，被指針指向的記錄稱為“被拴記錄”。如果不小心把被拴記錄刪掉，那么指向該記錄的指針成了“懸掛指針”。懸掛指針指向的空間稱為“垃圾”，即該空間別人無(wú)法使用而又被空閑著。6.1.1定長(zhǎng)記錄（5）文件首部記錄0LIUA-102600記錄1記錄2HEF-257800記錄3ZHANGA-214600記錄4記錄5LIUB-215800記錄6記錄7ZHANGB-467600記錄8LIUC-333400圖6.4刪除記錄1、4、6后的文件結(jié)構(gòu)102．插入操作時(shí)的考慮如果采用把被刪記錄鏈接起來(lái)的方法，那么插入操作可采用下列方法：在空閑記錄鏈表的第一個(gè)空閑記錄中，填上插入記錄的值，同時(shí)使首部指針指向下一個(gè)空閑記錄；如果空閑記錄鏈表為空，那么只能把新記錄插到文件尾。定長(zhǎng)記錄文件的插入操作比較簡(jiǎn)單，因?yàn)椴迦胗涗浀拈L(zhǎng)度與被刪記錄的長(zhǎng)度是相等的。在變長(zhǎng)記錄文件中操作就復(fù)雜了。6.1.1定長(zhǎng)記錄（6）11在DBS中，有時(shí)需要文件中的記錄是變長(zhǎng)格式。例如，一個(gè)文件存儲(chǔ)了多種不同的記錄類型記錄；文件中允許記錄類型的記錄是變長(zhǎng)的；允許記錄中某個(gè)字段可以出現(xiàn)重復(fù)組等等。例如圖6.1的文件也可以設(shè)計(jì)成變長(zhǎng)記錄格式：

TYPEEMP_LIST=RECORD ENAME：CHAR（10）；

ENO_INFO：ARRAY[1..∞]OF RECORD ENO：CHAR（10）；

SALARY：REAL；

END END此處定義（ENO，SALARY）作為成分元素組成一個(gè)數(shù)組，成分具體個(gè)數(shù)視實(shí)際情況而定。6.1.2變長(zhǎng)記錄（1）126.1.2變長(zhǎng)記錄（2）變長(zhǎng)記錄的表示有字節(jié)串形式和定長(zhǎng)形式兩種。1．變長(zhǎng)記錄的字節(jié)串表示形式 這種形式是把每個(gè)記錄看成連續(xù)的字節(jié)串，然后在每個(gè)記錄的尾部附加“記錄尾標(biāo)識(shí)符”（⊥）。圖6.1的定長(zhǎng)記錄文件可以用圖6.5的格式表示。0LIUA-102600B-215800C-333400⊥1WENB-306700⊥2HEF-257800⊥3ZHANGA-214600B-467600⊥4ZHOUC-343750⊥5LOUB-428850⊥圖6.5變長(zhǎng)記錄的字節(jié)串表示形式13字節(jié)串表現(xiàn)形式的另一種方式是在記錄的開始加一個(gè)記錄長(zhǎng)度的字段來(lái)實(shí)現(xiàn)，而不是使用在記錄尾加標(biāo)志符的方法。字節(jié)串表示形式有兩個(gè)缺點(diǎn)：（1）由于各記錄的長(zhǎng)度不一，因此被刪記錄的位置難以重新使用。既使制訂許多技術(shù)規(guī)則，仍然會(huì)導(dǎo)致磁盤中出現(xiàn)大量小的空間（即“碎片”）浪費(fèi)了。（2）如果文件中的記錄要伸長(zhǎng)，很難實(shí)現(xiàn)。必須要把記錄移到他處才能伸長(zhǎng)。如果要伸長(zhǎng)的記錄是“被拴記錄”，那么移動(dòng)的代價(jià)是很大的。由于上述兩個(gè)缺點(diǎn)，現(xiàn)在一般不使用字節(jié)串表現(xiàn)形式。在實(shí)際中，往往使用的是一種改進(jìn)的字節(jié)串表現(xiàn)形式，稱為“分槽式頁(yè)結(jié)構(gòu)”（slotted–pagestructure），如圖6.6所示。6.1.2變長(zhǎng)記錄（3）14在每塊的開始處設(shè)置一個(gè)“塊首部”，其中包括下列信息：①塊中記錄數(shù)目②指向塊中自由空間尾部的指針③登記每個(gè)記錄的開始位置和大小的信息6.1.2變長(zhǎng)記錄（4）塊首部記錄大小記錄數(shù)目自由空間……記錄位置自由空間尾部圖6.6分槽式頁(yè)結(jié)構(gòu)15在塊中實(shí)際記錄緊連著，并靠近塊尾部存放。塊中自由空間也緊連著，在塊的中間。插入總是從自由空間尾部開始，并在塊首部登錄其插入記錄的開始位置和大小。記錄刪除時(shí)只要在塊首部該記錄的大小登記處改為-1即可。更進(jìn)一步，可以把被刪記錄左邊的記錄移過(guò)來(lái)填補(bǔ)，使實(shí)際記錄仍然緊連著。當(dāng)然此時(shí)塊首部記錄的信息也要修改。記錄的伸縮也可使用這樣的方法。在塊中移動(dòng)記錄的代價(jià)也不太高，這是因?yàn)橐粔K的大小最多只有4KB。在分槽式頁(yè)結(jié)構(gòu)中，要求其它指針不能直接指向記錄本身，而是指向塊首部中的記錄信息登記項(xiàng)，這樣塊中記錄的移動(dòng)就獨(dú)立與外界因素了。6.1.2變長(zhǎng)記錄（5）162．變長(zhǎng)記錄的定長(zhǎng)表示形式 在文件系統(tǒng)中往往是使用一個(gè)或多個(gè)定長(zhǎng)記錄來(lái)表示變長(zhǎng)記錄的方法。具體實(shí)現(xiàn)時(shí)有兩種技術(shù)：預(yù)留空間和指針技術(shù)。（1）預(yù)留空間的方法 取所有變長(zhǎng)記錄中最長(zhǎng)的一個(gè)記錄的長(zhǎng)度作為存儲(chǔ)空間的記錄長(zhǎng)度，來(lái)存儲(chǔ)變長(zhǎng)記錄。如果變長(zhǎng)記錄短于存儲(chǔ)記錄長(zhǎng)度，那么在多余空間處填上某個(gè)特定的空值或記錄尾標(biāo)志符。例如圖6.5的字節(jié)串表現(xiàn)形式可以用圖6.7的預(yù)留空間方法實(shí)現(xiàn)。這方法一般使用在大多數(shù)記錄的長(zhǎng)度接近最大長(zhǎng)度時(shí)才使用，否則使用時(shí)空間浪費(fèi)很大。6.1.2變長(zhǎng)記錄（6）176.1.2變長(zhǎng)記錄（7）圖6.7變長(zhǎng)記錄的預(yù)留空間表示形式0LIUA-102600B-215800C-3334001WENB-306700⊥⊥⊥⊥2HEF-257800⊥⊥⊥⊥3ZHANGA-214600B-467600⊥⊥4ZHOUC-343750⊥⊥⊥⊥5LOUB-428850⊥⊥⊥⊥（2）指針形式如果記錄的長(zhǎng)度相差很大，那么可用指針形式實(shí)現(xiàn)變長(zhǎng)記錄的定長(zhǎng)表示形式。在每個(gè)記錄后加一個(gè)指針字段，圖6.5的文件可以用圖6.8來(lái)表示。使用改進(jìn)的指針形式，在一個(gè)文件中使用兩種塊，固定塊和溢出塊。圖6.9表示文件的固定塊和溢出塊結(jié)構(gòu)。18圖6.8變長(zhǎng)記錄的指針表示方式6.1.2變長(zhǎng)記錄（8）圖6.9固定塊和溢出塊的結(jié)構(gòu)固定塊0LIUA-1026001WENB-3067002HEF-2578003ZHANGA-2146004ZHOUC-3437505B-2158006LOUB-4288507B-4676008C-333400溢出塊LIUA-102600WENB-306700HEF-257800ZHANGA-214600ZHOUC-343750LOUB-428850B-215800C-333400B-467600196.2文件結(jié)構(gòu)

6.2.1四種文件結(jié)構(gòu)6.2.2順序文件6.2.3聚集文件20文件結(jié)構(gòu)主要有下列四種形式：（1）堆文件（heapfile） 記錄可以放在文件的任何位置上。一般，以輸入順序?yàn)樾?。記錄的存?chǔ)順序與關(guān)鍵碼沒有直接的聯(lián)系。刪除操作只是加個(gè)刪除標(biāo)志，新插入記錄總是在文件尾。（2）順序文件（sequentialfile） 記錄是按查找鍵值升序或降序的順序存儲(chǔ)的。（3）散列文件（hashingfile） 據(jù)記錄的某個(gè)屬性值通過(guò)散列函數(shù)求得的值作為記錄的存儲(chǔ)地址（即“塊號(hào)”）。這個(gè)技術(shù)通常與索引技術(shù)連用。（4）聚集文件（clusteringfile） 一個(gè)文件可以存儲(chǔ)多個(gè)關(guān)系的記錄。不同關(guān)系中有聯(lián)系的記錄存儲(chǔ)在同一塊內(nèi)，可以提高查找速度和I/O速度。本節(jié)介紹順序文件和聚集文件，散列文件在6.4節(jié)中介紹。6.2.1四種文件結(jié)構(gòu)21根據(jù)查找鍵的值的順序存儲(chǔ)記錄的文件稱為順序文件。在文件中，每個(gè)記錄增加一個(gè)指針字段，根據(jù)查找鍵值的大小用指針把記錄鏈接起來(lái)。文件初始建立時(shí)，存儲(chǔ)記錄盡可能使物理順序和查找鍵值的順序一致。圖6.10是順序文件的例子，記錄按ENAME值升序排列。順序文件可以很方便地按查找鍵的值的大小順序讀出所有的記錄。6.2.2順序文件（1）HEF-257800LIUA-102600LIUB-215800LIUC-333400LOUB-428850WENB-306700ZHANGA-214600ZHANGB-467600ZHOUC-343750圖6.10順序文件22刪除操作可以通過(guò)修改指針實(shí)現(xiàn)，被刪記錄鏈接成一個(gè)自由空間，以便插入時(shí)使用。插入操作包括定位和插入兩步：（1）定位：在指針鏈中，找到插入的位置，即插入記錄應(yīng)插在哪個(gè)記錄的前面。（2）插入：在找到記錄的塊內(nèi)，如果有空閑記錄，那么在該位置插入新記錄，并加入到指針鏈中；如果無(wú)空閑記錄，那么就只能插入到溢出塊中。在圖6.10中，插入一個(gè)新記錄（MA，B-547，500），就得到圖6.11。6.2.2順序文件（2）HEF-257800LIUA-102600LIUB-215800LIUC-333400LOUB-428850WENB-306700ZHANGA-214600ZHANGB-467600ZHOUC-343750MAB-547500圖6.11插入一個(gè)記錄后的順序文件23在小型DBS中，數(shù)據(jù)量小，每個(gè)關(guān)系處理成一個(gè)文件。這種文件稱為單記錄類型文件，文件中每個(gè)記錄都是定長(zhǎng)的。文件之間是分離的，沒有聯(lián)系。隨著數(shù)據(jù)量的增大，系統(tǒng)的性能和查詢速度日益下降。此時(shí)應(yīng)采用新的文件結(jié)構(gòu)，稱為“聚集文件”。這種變化允許一個(gè)文件由多個(gè)關(guān)系的記錄組成，即多記錄類型文件。聚集文件的管理由DBS實(shí)現(xiàn)。例如教學(xué)數(shù)據(jù)庫(kù)中關(guān)系S（SNO，SNAME，AGE，SEX）和SC（SNO，CNO，SCORE），如果將每個(gè)關(guān)系組織成一個(gè)文件，那么查找學(xué)生的成績(jī)，就要做連接操作：

SELECTS.SNO，SNAME，CNO，GRADE FROMS，SC WHERES.SNO=SC.SNO；6.2.3聚集文件（1）24在圖6.12中，關(guān)系S和SC如圖（a）、（b）所示，S和SC的元組混合放在一起，如圖（c）所示。即使一個(gè)學(xué)生的成績(jī)信息很多，一塊訪不下，那么也是放在相鄰的塊內(nèi)。為了進(jìn)一步提高查詢速度，我們可以在文件中建立以查詢學(xué)生信息為主的鏈表，在圖6.12的（c）中已表示。6.2.3聚集文件（2）S1WANG20MS1C180S1WANG20MS2LIU21FS1C270S1C180S3CHEN22MS3C190S1C270S3C285S2LIU21FS3C395S3CHEN22MS3C190S3C285S3C395（a）關(guān)系S（b）關(guān)系SC圖6.12聚集文件例子（c）聚集文件256.3索引技術(shù)6.3.1索引機(jī)制6.3.2有序索引的分類6.3.3主索引6.3.4輔助索引6.3.5B+樹索引文件6.3.6B樹索引文件26根據(jù)記錄中某種排序順序建立的索引，稱為有序索引。在索引技術(shù)中，用戶可根據(jù)下面五個(gè)方面選擇各種實(shí)現(xiàn)方法：①存取類型：用戶是根據(jù)屬性值找記錄，還是根據(jù)屬性值的范圍找記錄。②存取時(shí)間；查找記錄所花費(fèi)的時(shí)間。③插入時(shí)間；插入新記錄所花費(fèi)的時(shí)間，應(yīng)包括兩部份，找到正確的位置插入新記錄所花時(shí)間和修改索引結(jié)構(gòu)所花時(shí)間。④刪除時(shí)間；也應(yīng)包括兩部分，找到被刪記錄刪除所花時(shí)間和修改索引結(jié)構(gòu)所花時(shí)間。⑤索引空間開銷。在索引中，用于找記錄的屬性集稱為查找鍵。應(yīng)注意，查找鍵不一定是主鍵（候選鍵、超鍵），前者的值允許重復(fù)，而后者的值不允許重復(fù)。6.3.1索引機(jī)制27索引文件由兩個(gè)部分組成：索引和主文件。由于主文件記錄多、數(shù)據(jù)量大并且占據(jù)大量物理塊，因此在主文件中查找，速度是很慢的。如果對(duì)記錄建立索引，那么相對(duì)主文件而言，索引空間小，因而查找速度就快。這里考慮的主文件是指順序文件，文件按某個(gè)屬性值大小的順序排列。對(duì)主文件可以建立幾套不同的索引。如果索引的查找鍵值的順序與主文件的順序一致，那么這種索引稱為主索引，也稱為聚集索引。一般，主索引的查找鍵往往是文件的主鍵。如果查找鍵的值的順序與主文件的順序不一致，那么這種索引稱為輔助索引，或非聚集索引。6.3.2有序索引的分類28當(dāng)索引查找鍵值的順序與主文件順序一致時(shí)，這種索引文件稱為“索引順序文件”。這種文件既適用隨機(jī)處理，也適用順序處理。下面以圖6.10的順序文件為例介紹主索引以及稠密索引、稀疏索引和多級(jí)索引三種實(shí)現(xiàn)方法。1．稠密索引和稀疏索引對(duì)于主索引，可以采用下面兩種實(shí)現(xiàn)方法：（1）稠密索引（denseindex）：對(duì)于主文件中每一個(gè)查找鍵值建立一個(gè)索引記錄（索引項(xiàng)），索引記錄包括查找鍵值和指向具有該值的記錄鏈表中第一個(gè)記錄的指針。這種索引稱為“稠密索引”。讀者應(yīng)注意，在有些教材中稠密索引定義為對(duì)主文件中每個(gè)記錄建立一個(gè)索引記錄，與我們的提法有區(qū)別。圖6.13是為圖6.10的順序文件建立的稠密索引。6.3.3主索引（1）296.3.3主索引（2）圖6.13稠密索引HELIULOUWENZHANGZHOUHEF-257800LIUA-102600LIUB-215800LIUC-333400LOUB-428850WENB-306700ZHANGA-214600ZHANGB-467600ZHOUC-343750306.3.3主索引（3）（2）稀疏索引（sparseindex）：在主文件中，對(duì)若干個(gè)查找鍵值才建立一個(gè)索引記錄，此時(shí)索引記錄的內(nèi)容仍和稠密索引一樣。這種索引稱為“稀疏索引”。圖6.14為圖6.10的順序文件建立的稀疏索引。HELOUZHANGHEF-257800LIUA-102600LIUB-215800LIUC-333400LOUB-428850WENB-306700ZHANGA-214600ZHANGB-467600ZHOUC-343750圖6.14稀疏索引31相比之下，在帶稠密索引的主文件中，查找速度較快；而帶稀疏索引的文件中查找較慢，但稀疏索引的空間較小，因此插入、刪除操作時(shí)指針的維護(hù)量相對(duì)要少些。系統(tǒng)設(shè)計(jì)者應(yīng)在存取時(shí)間和空間開銷方面權(quán)衡，選擇何種索引。有一個(gè)折衷的辦法，可把兩種索引結(jié)合起來(lái)。首先為順序文件的每一塊建立一個(gè)索引記錄，得到一個(gè)以塊為基本單位的稠密索引，然后再在稠密索引基礎(chǔ)上建立一個(gè)稀疏索引。查找時(shí)，先在稀疏索引中找到記錄所在的范圍，然后在稠密索引中確定記錄在哪一塊，最后在主文件的塊中順序查找，找到所在的主記錄。這種方法實(shí)際已是二級(jí)索引了。6.3.3主索引（4）322．多級(jí)索引即使采用稀疏索引，可能建成的索引還是很大，以至于查詢效率不高。解決這個(gè)問(wèn)題的方法是對(duì)主索引再建立一級(jí)稀疏索引。即對(duì)每個(gè)索引塊建立一個(gè)索引記錄（如圖6.15所示）。圖6.15是一個(gè)二級(jí)索引例子。此時(shí)外層索引塊可常駐內(nèi)存，在找記錄時(shí)內(nèi)層索引塊只要讀1次就行。如果外層索引塊的數(shù)目太多，不能全部進(jìn)內(nèi)存，那么可對(duì)最外層索引再往外建一層索引。這就形成了多級(jí)索引技術(shù)。6.3.3主索引（5）336.3.3主索引（6）圖6.15二級(jí)稀疏索引………外層索引內(nèi)層索引索引塊0數(shù)據(jù)塊0索引塊1…數(shù)據(jù)塊1343．索引的更新：在索引文件中，主記錄的插入或刪除可能會(huì)引起索引的修改。在只有一級(jí)的索引中索引的修改算法如下所述。（1）刪除操作 ●為了在主文件中刪除一個(gè)記錄，首先要找到被刪記錄，才能執(zhí)行刪除操作。 ●如果符合查找鍵值的記錄在文件中只有一個(gè)，那么被刪記錄刪除后，肯定要修改索引。 ●如果要修改索引，對(duì)于稠密索引，要從索引中刪除被刪記錄相應(yīng)的索引記錄；對(duì)于稀疏索引，如果被刪記錄的查找鍵值在索引塊中出現(xiàn)，那么用主文件中被刪記錄的下一個(gè)主記錄的查找鍵值A(chǔ)替換，如果A已在索引塊中出現(xiàn)，那么被刪記錄的相應(yīng)索引記錄應(yīng)從索引塊中刪除。6.3.3主索引（7）35（2）插入操作 ●首先，用插入記錄的查找鍵值找到插入位置。

●如果是稠密索引并且查找鍵值在索引塊中未出現(xiàn)過(guò)，那么要把插入記錄的查找鍵值插入到索引塊中。

●如果是稀疏索引，每一個(gè)數(shù)據(jù)塊對(duì)應(yīng)一個(gè)索引記錄，那么在數(shù)據(jù)塊能放得下新記錄時(shí)，不必修改索引。如果要加入新的數(shù)據(jù)塊，那么插入記錄的查找鍵值將成為新數(shù)據(jù)塊的第一個(gè)查找鍵值，并將在索引塊中插入一個(gè)新的索引記錄。在多級(jí)索引時(shí),可以采取類似的辦法。在插入、刪除主記錄時(shí)，最低一級(jí)索引的修改方法如上所述。如果第二級(jí)索引（外層）要修改，那么把第一級(jí)索引（內(nèi)層）看成順序文件。在第一級(jí)索引中插入或刪除一個(gè)索引記錄時(shí)，第二級(jí)索引的修改也像上面敘述的方法一樣。以此類推。6.3.3主索引（8）36在主索引中，我們可以方便、快速地根據(jù)某個(gè)查找鍵值找記錄。如果我們要根據(jù)另一個(gè)查找鍵值尋找主文件的記錄，那么可以用輔助索引方法實(shí)現(xiàn)。在主索引中，具有相同查找鍵值的記錄在同一塊中或相鄰的塊中，因而查找速度較快。而在輔助索引中，具有相同查找鍵值的記錄將分散在文件的各處，因而查找速度較慢，并且查找時(shí)無(wú)法利用主文件中按主索引鍵值建立的指針鏈。輔助索引可采用下面的方法實(shí)現(xiàn)：仍然為每個(gè)查找鍵值建立一個(gè)索引記錄，內(nèi)容包括查找鍵值和一個(gè)指針。但這個(gè)指針不指向主文件中的記錄，而是指向一個(gè)桶（bucket），桶內(nèi)存放指向具有同一查找鍵值的主記錄的指針。例如在圖6.10的順序文件中，可以對(duì)屬性SALARY建立一個(gè)輔助索引，其結(jié)構(gòu)如圖6.16所示。6.3.4輔助索引（1）376.3.4輔助索引（2）圖6.16輔助索引例子400600700750800850HEF-257800LIUA-102600LIUB-215800LIUC-333400LOUB-428850WENB-306700ZHANGA-214600ZHANGB-467600ZHOUC-34375038在主索引中可以采取順序查找方法。在輔助索引中，由于同一個(gè)查找鍵值的記錄分散在文件的各處，因此以輔助索引查找鍵順序掃描文件是行不通的，每讀一個(gè)記錄幾乎都要執(zhí)行讀一塊到內(nèi)存的操作。輔助索引都是稠密索引，不可能是稀疏索引結(jié)構(gòu)。在主記錄插入或刪除時(shí)，都要修改輔助索引，修改的方法與主索引的方法類似。輔助索引機(jī)制曾在20世紀(jì)60年代中期廣泛流行，倒排文件系統(tǒng)就是建立了許多輔助索引的文件系統(tǒng)。輔助索引改善了系統(tǒng)的查詢效率和查詢方式，但是也給系統(tǒng)帶來(lái)很大的負(fù)擔(dān)。數(shù)據(jù)庫(kù)應(yīng)用設(shè)計(jì)者應(yīng)在查詢效率和修改的代價(jià)方面作出權(quán)衡，以選擇合適的索引結(jié)構(gòu)。6.3.4輔助索引（3）391．平衡樹的概念為了改善索引結(jié)構(gòu)的性能，可以采用多級(jí)索引，目前廣泛流行的一種技術(shù)，稱為平衡樹（Balancedtree）技術(shù)。數(shù)據(jù)庫(kù)技術(shù)中平衡樹的形式定義如下所述。定義6.1一棵m階平衡樹或者為空，或者滿足以下條件： ①每個(gè)結(jié)點(diǎn)至多有m棵子樹； ②根結(jié)點(diǎn)或?yàn)槿~結(jié)點(diǎn)，或至少有兩棵子樹； ③每個(gè)非葉結(jié)點(diǎn)至少有?m/2?棵子樹； ④從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的每一條路徑都有同樣的長(zhǎng)度，即 葉結(jié)點(diǎn)在同一層次上。平衡樹又分為兩類：B+樹和B樹。下面先介紹B+樹。6.3.5B+樹索引文件（1）406.3.5B+樹索引文件（2）2．B+樹的結(jié)構(gòu) 在實(shí)際使用中，B+樹有很多形式，下面介紹其中的一種。一棵m階B+樹是平衡樹，按下列方式組織：（1）每個(gè)結(jié)點(diǎn)中至多有m-1個(gè)查找鍵值K1，K2，…，Km-1， m個(gè)指針P1，P2，…，Pm，如圖6.17所示。P1K1P2……Pm-1Km-1Pm圖6.17B+樹的結(jié)點(diǎn)結(jié)構(gòu)41（2）葉結(jié)點(diǎn)的組織方式葉結(jié)點(diǎn)中的指針（1≤i≤m-1）指向主文件中的記錄。譬如指針Pi指向查找鍵值為Ki的主記錄。如果查找鍵恰好是主文件的主鍵，那么葉結(jié)點(diǎn)中的指針直接指向主文件中的記錄。如果查找鍵不是主文件的主鍵，并且查找鍵值的順序也不是主文件的順序，那么葉結(jié)點(diǎn)中的指針指向一個(gè)桶，桶中存放指向具有該查找鍵值的主記錄的指針。每個(gè)葉結(jié)點(diǎn)中至少應(yīng)有?（m-1）/2?個(gè)查找鍵，至多有m-1個(gè)查找鍵，并且查找鍵值不允許重復(fù)。如果B+樹索引是稠密索引，那么每個(gè)查找鍵值必須在某個(gè)葉結(jié)點(diǎn)中出現(xiàn)。葉結(jié)點(diǎn)中最后一個(gè)指針Pm，指向下一個(gè)葉結(jié)點(diǎn)（按查找鍵值順序）。這樣可以很方便地在主文件進(jìn)行順序訪問(wèn)。圖6.18表示3階B+樹的葉結(jié)點(diǎn)結(jié)構(gòu)。6.3.5B+樹索引文件（3）426.3.5B+樹索引文件（4）圖6.183階B+樹的 葉結(jié)點(diǎn)結(jié)構(gòu)葉結(jié)點(diǎn)HELIUHEF-257800LIUA-102600LIUB-215800LIUC-333400………下一個(gè)葉結(jié)點(diǎn)主文件（3）非葉結(jié)點(diǎn)的組織方式 B+樹中的非葉結(jié)點(diǎn)形成了葉結(jié)點(diǎn)上的一個(gè)多級(jí)稀疏索引。每個(gè)非葉結(jié)點(diǎn)（不包括根結(jié)點(diǎn)）中至少有?m/2?個(gè)指針，至多有m個(gè)指針。指針的數(shù)目稱為結(jié)點(diǎn)的“扇出端數(shù)”（fanout）。圖6.19是一個(gè)完整的3階B+樹索引。圖6.20是一個(gè)5階B+樹索引的例子。43圖6.193階B+樹索引6.3.5B+樹索引文件（5）圖6.205階B+樹索引WENHELIULOUWENZHANGZHOUZHANGLOUWENHELIULOUWENZHANGZHOU443．B+樹的查詢?nèi)绻脩粢獧z索查找鍵值為K的所有記錄，那么首先在根結(jié)點(diǎn)中找大于K的最小查找鍵值（設(shè)為Ki），然后沿著Ki左邊的指針Pi到達(dá)第二層的結(jié)點(diǎn)。如果根結(jié)點(diǎn)中有n個(gè)指針，并且K＞Kn-1，那么就沿著指針Pn到達(dá)第二層的結(jié)點(diǎn)。在第二層的結(jié)點(diǎn)，用類似的方法找到一個(gè)指針，進(jìn)入第三層的結(jié)點(diǎn)……一直到進(jìn)入B+樹的葉結(jié)點(diǎn)，找到一個(gè)指針直接指向主文件的記錄，或指向一個(gè)桶（存放指向主文件記錄的指針）。最后把所需記錄找到。如果文件中查找鍵值有W個(gè)值，那么對(duì)于m階B+樹而言，從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長(zhǎng)度不超過(guò)?log?m/2?（W）?。6.3.5B+樹索引文件（6）45例6.2討論B+樹索引查詢中查詢次數(shù)與文件的存儲(chǔ)塊數(shù)的關(guān)系。 如果在B+樹索引中，每塊存儲(chǔ)一個(gè)結(jié)點(diǎn)，占4096字節(jié)。如果查找鍵的長(zhǎng)度為32字節(jié)，指針仍為8字節(jié)，那么每塊大約可存儲(chǔ)100個(gè)查找鍵值和指針，即m約為100。 在m為100時(shí)，如果文件中查找鍵有100萬(wàn)個(gè)值，那么一次查找需讀索引塊的數(shù)目為?log50（1000000）?=4。如果B+樹索引的根結(jié)點(diǎn)常駐內(nèi)存，那么查找時(shí)只需再讀三個(gè)索引塊即可。B+樹的結(jié)構(gòu)與內(nèi)存中普遍使用的二叉排序樹的主要區(qū)別是結(jié)點(diǎn)的大小以及樹的高度。在二叉排序樹中，每個(gè)結(jié)點(diǎn)很小，只有一個(gè)鍵值和兩個(gè)指針。而B+樹中，每個(gè)結(jié)點(diǎn)很大，可以是磁盤上的一個(gè)塊，包含更多查找鍵值和指針。二叉排序樹顯得瘦而高，而B+樹顯得胖而矮。6.3.5B+樹索引文件（7）464．B+樹的更新 在B+樹索引文件中插入主記錄時(shí)，有可能葉結(jié)點(diǎn)要分裂，并引起上層結(jié)點(diǎn)的分裂和B+樹層數(shù)的增加。在刪除主記錄時(shí)，這有可能出現(xiàn)相反的現(xiàn)象。下面就是否出現(xiàn)分裂與合并情況分別討論。（1）不引起索引結(jié)點(diǎn)分裂的插入操作 首先使用查找方法，從根結(jié)點(diǎn)出發(fā)直到在葉結(jié)點(diǎn)中找到某個(gè)查找鍵值K1。如果插入記錄的查找鍵值K0已在葉結(jié)點(diǎn)出現(xiàn)，那么在主文件中插入記錄即可，不必修改索引。 如果K0在葉結(jié)點(diǎn)中不存在，那么在葉結(jié)點(diǎn)中K1之前插入K0值（此時(shí)假設(shè)葉結(jié)點(diǎn)中存在空閑空間），并把K1及K1后的值往后移動(dòng)，使葉結(jié)點(diǎn)中查找鍵值仍然保持排序。然后插入新記錄到主文件中去。6.3.5B+樹索引文件（8）47（2）不引起索引結(jié)點(diǎn)合并的刪除操作 首先使用查找方法在主文件中找到被刪記錄，刪除之。 如果主文件中還存在具有被刪記錄查找鍵值的記錄，那么不必修改索引；否則應(yīng)該從葉結(jié)點(diǎn)中刪除該查找鍵值和相應(yīng)的指針。此時(shí)假定葉結(jié)點(diǎn)中中查找鍵值的數(shù)目仍然不小于?（m-1）/2?。（3）引起索引結(jié)點(diǎn)分裂的插入操作 如果插入主記錄時(shí)，要在葉結(jié)點(diǎn)中插入其查找鍵值，并且葉結(jié)點(diǎn)中已放滿查找鍵值，那么此時(shí)葉結(jié)點(diǎn)應(yīng)分裂成兩個(gè)。例如在圖6.19的3階B+樹文件中，插入一個(gè)查找鍵值為“JIANG”的主記錄，那么左邊第一個(gè)葉結(jié)點(diǎn)就要分裂成兩個(gè)結(jié)點(diǎn)，如圖6.21所示。6.3.5B+樹索引文件（9）48圖6.21插入JIANG后葉結(jié)點(diǎn)的分裂6.3.5B+樹索引文件（10）LIULOUZHANGWENHEJIANGZHANGZHOULIULOUWENHEJIANGLIU圖6.22在圖6.19的B+樹中插入“JIANG”49（4）引起索引結(jié)點(diǎn)合并的刪除操作如果刪除主記錄時(shí)，要在葉結(jié)點(diǎn)中刪除被刪記錄的查找鍵值，并且該值刪除后葉結(jié)點(diǎn)中查找鍵值數(shù)目小于?（m-1）/2?，那么這個(gè)葉結(jié)點(diǎn)在作技術(shù)處理時(shí)有可能被刪掉。例如在圖6.22中要?jiǎng)h除“LIU”主記錄，導(dǎo)致葉結(jié)點(diǎn)中刪除“LIU”后成為空葉結(jié)點(diǎn)，因此該葉結(jié)點(diǎn)要?jiǎng)h除。這將引起在父結(jié)點(diǎn)中刪除相應(yīng)指針及指針左邊的查找鍵值“LIU”。此時(shí)索引的修改結(jié)束后如圖6.23所示。6.3.5B+樹索引文件（11）LOUZHANGWENHEJIANGZHANGZHOULOUWEN圖6.23在圖6.22的B+樹中刪除“LIU”50如果要在圖6.23中刪除“WEN”的主記錄，那么也會(huì)導(dǎo)致葉結(jié)點(diǎn)刪除WEN后成為空葉結(jié)點(diǎn)而被刪除。在其父結(jié)點(diǎn)中刪除相應(yīng)指針后，只剩下一個(gè)查找鍵值ZHANG和一個(gè)指針，這不符合B+樹的要求。由于該結(jié)點(diǎn)中還有信息，因此不能像剛才那樣進(jìn)行簡(jiǎn)單的刪除。此時(shí)由于其相鄰的左孿結(jié)點(diǎn)中還有空閑空間，因此兩個(gè)結(jié)點(diǎn)可合并成一個(gè)結(jié)點(diǎn)。這就引起根結(jié)點(diǎn)中也少了一個(gè)指針，不符合B+樹要求，因此可把根結(jié)點(diǎn)直接刪去即可（如圖6.24所示）。此時(shí)B+樹的高度減少了一層。6.3.5B+樹索引文件（12）LOUZHANGHEJIANGZHANGZHOULOU圖6.24在圖6.23的B+樹中刪除“WEN”51但有時(shí)結(jié)點(diǎn)的合并未必成功，只能重新安排指針。例如在圖6.22中刪除“WEN”的主記錄（此時(shí)“LIU”未刪除）。在葉結(jié)點(diǎn)中把“WEN”刪除后成為空葉結(jié)點(diǎn)，在父結(jié)點(diǎn)中刪除相應(yīng)指針后，指針數(shù)目不夠。此時(shí)父結(jié)點(diǎn)的左孿結(jié)點(diǎn)中已放滿了查找鍵值，因而不能合并，只能重新安排指針，從左孿結(jié)點(diǎn)中移一個(gè)指針過(guò)來(lái)，同時(shí)在這兩個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)（這里是根結(jié)點(diǎn)）中查找鍵值應(yīng)修改為“LOU”，如圖6.25所示。6.3.5B+樹索引文件（13）LIUZHANGLOUHEJIANGZHANGZHOULIULOU圖6.25在圖6.22的B+樹中刪除“WEN”52雖然B+樹索引的插入、刪除比較復(fù)雜，但其速度與B+樹高度成正比。前面已提到，100萬(wàn)個(gè)記錄的B+樹索引才4層，因此所花代價(jià)是不大的。由于這個(gè)原因，B+樹結(jié)構(gòu)在DBS中得到廣泛應(yīng)用。5．B+樹文件組織前面提到的B+樹索引文件組織，把B+樹索引與主文件截然分開。在B+樹結(jié)構(gòu)中，所有葉子處在同一層次上，并且利用葉子中的指針指向主文件中的記錄，或指向一個(gè)桶，再由桶內(nèi)指針指向記錄。在這樣的結(jié)構(gòu)中，B+樹不僅是一個(gè)索引，而且還是一個(gè)文件中記錄的組織者。6.3.5B+樹索引文件（14）53對(duì)B+樹索引文件組織作進(jìn)一步的演變，使得B+樹葉結(jié)點(diǎn)不存儲(chǔ)指向主記錄的指針，而是直接存儲(chǔ)記錄本身，那么這種結(jié)構(gòu)稱為“B+樹文件組織”。圖6.26表示了這種結(jié)構(gòu)。這樣，查詢時(shí)到達(dá)葉結(jié)點(diǎn)后，直接可把主記錄找到，不必再沿著指針去找主記錄.顯然文件的性能得到進(jìn)一步的提高.雖然主記錄長(zhǎng)度要比指針大很多,也就是每個(gè)葉結(jié)點(diǎn)可存儲(chǔ)的記錄數(shù)目要小于非葉結(jié)點(diǎn)中的指針數(shù)目,但是我們?nèi)匀灰竺總€(gè)葉結(jié)點(diǎn)中至少有一半空間是裝著記錄的。B+樹文件組織的插入、刪除操作與B+樹索引記錄的插入和刪除操作是一樣的，也有可能會(huì)引起結(jié)點(diǎn)的分裂或合并，層數(shù)的增加或減少。6.3.5B+樹索引文件（15）54圖6.26B+樹文件組織6.3.5B+樹索引文件（16）CF1KM(A,4)(B,8)(C,2)(D,9)(E,4)(F,7)(G,3)(H,3)(I,4)(J,8)(K,4)(L,6)(M,4)(N,8)(P,6)55B樹索引類似于B+樹索引。兩者主要區(qū)別在于B樹中所有查找鍵值只出現(xiàn)一次。例如，在圖6.22的B+樹中，查找鍵值“LIU”、“LOU”等都出現(xiàn)了兩次。在B+樹中，每個(gè)查找鍵值都必須在葉結(jié)點(diǎn)中出現(xiàn)，為了組織多級(jí)索引，某些查找鍵值還必須在上層結(jié)點(diǎn)中出現(xiàn)。在B樹中，查找鍵值可以出現(xiàn)在任何結(jié)點(diǎn)上，但只能出現(xiàn)一次。圖6.22的B+樹結(jié)構(gòu)用B樹形式表示如圖6.27所示。顯然，B樹中的查找鍵值數(shù)目比B+樹少。6.3.6B樹索引文件（1）LIUZHANGHEJIANGLOUWENZHOUbucketbucketbucketbucketbucketbucketbucket圖6.27與圖6.22中B+樹等價(jià)的B樹結(jié)構(gòu)56在B樹中查詢的查找次數(shù)取決于查找鍵值的位置，有時(shí)未到達(dá)葉結(jié)點(diǎn)，就已找到了鍵值。查找鍵值靠近下面層次或葉結(jié)點(diǎn)層次，則查找次數(shù)較多。B樹的查詢時(shí)間復(fù)雜性仍然是對(duì)數(shù)級(jí)時(shí)間。在B樹中，如果查找鍵值出現(xiàn)在非葉結(jié)點(diǎn)，那么在它出現(xiàn)的地方應(yīng)附加上一個(gè)指向主記錄的指針；如果查找鍵值出現(xiàn)在葉結(jié)點(diǎn)，那么不必另加指針，可利用結(jié)點(diǎn)中的指針指向主記錄。像B+樹一樣，這個(gè)指針也可指向一個(gè)桶，桶內(nèi)存放指向主記錄的指針。這個(gè)結(jié)構(gòu)如圖6.28所示。指針Pi的使用方法與B+樹一樣，非葉結(jié)點(diǎn)中的指針Bi指向一個(gè)桶或主記錄。一棵m階B樹中，每個(gè)非葉結(jié)點(diǎn)中最多可包含m個(gè)指針，m-1個(gè)查找鍵值和m-1個(gè)指向桶的指針。而每個(gè)葉結(jié)點(diǎn)最多可包含n個(gè)指針和n-1個(gè)查找鍵值。由于葉結(jié)點(diǎn)中不包含Bi指針，因此葉結(jié)點(diǎn)中可以比非葉結(jié)點(diǎn)多存儲(chǔ)一些查找鍵，也就是n＞m。6.3.6B樹索引文件（2）57B樹中刪除操作較復(fù)雜。B+樹的刪除操作總是在葉結(jié)點(diǎn)進(jìn)行，而B樹有時(shí)可在非葉結(jié)點(diǎn)進(jìn)行。B樹中，如果被刪的查找鍵值在非葉結(jié)點(diǎn)中，那么必須從子樹中選一個(gè)查找鍵值填補(bǔ)。譬如某個(gè)非葉結(jié)點(diǎn)中，要?jiǎng)h除查找鍵值Ki，那么應(yīng)從指針Pi+1指向的子樹中選一個(gè)最小的查找鍵值移上來(lái)填補(bǔ)Ki的位置。如果葉結(jié)點(diǎn)中發(fā)現(xiàn)查找鍵值太少時(shí)，那么也要像B+樹那樣進(jìn)行結(jié)點(diǎn)的合并工作。B樹的插入基本上與B+樹類似。雖然B樹的空間量比B+樹小，但是由于B樹的刪除操作較復(fù)雜，因此大多數(shù)DBS都是使用B+樹結(jié)構(gòu)，而不使用B樹結(jié)構(gòu)。6.3.6B樹索引文件（3）58圖6.28B樹中非葉結(jié)點(diǎn)和葉結(jié)點(diǎn)的結(jié)構(gòu)6.3.6B樹索引文件（4）P1B1K1P2B2K2……Pm-1Bm-1Km-1Pm非葉結(jié)點(diǎn)P1K1P2K2……Pn-1Kn-1Pn葉結(jié)點(diǎn)596.4散列技術(shù)6.4.1散列機(jī)制6.4.2散列索引6.4.3靜態(tài)散列中的問(wèn)題6.4.4可擴(kuò)充散列結(jié)構(gòu)前面提到的順序文件組織的缺點(diǎn)是必須通過(guò)索引結(jié)構(gòu)訪問(wèn)數(shù)據(jù)。而且索引組織的空間和I／O操作的時(shí)間代價(jià)都是很大的。而散列方法是一種不必通過(guò)索引就能訪問(wèn)數(shù)據(jù)的方法。在散列技術(shù)基礎(chǔ)上結(jié)合索引方法可進(jìn)一步提高訪問(wèn)效率。本節(jié)介紹DB技術(shù)中使用的散列技術(shù)。601．散列概念根據(jù)記錄的查找鍵值，使用一個(gè)函數(shù)計(jì)算得到的函數(shù)值作為磁盤塊的地址，對(duì)記錄進(jìn)行存儲(chǔ)和訪問(wèn)，這種方法稱為散列方法。在DB技術(shù)中，一般使用“桶”（bucket）作為基本的存儲(chǔ)單位。一個(gè)桶可以存放多個(gè)記錄。桶可以是磁盤中的塊，也可以是比塊大的空間。定義6.2設(shè)K是所有查找鍵值的集合，B是所有桶地址的集合。散列函數(shù)h是從K到B的一個(gè)函數(shù)，它把每個(gè)查找鍵值映像到地址集合中的地址。要插入查找鍵值為Ki的記錄，首先也是計(jì)算h（Ki），求出該記錄的桶地址，然后在桶內(nèi)查找。刪除操作是很方便的，先用查找方法把記錄找到，然后直接從桶內(nèi)刪去即可。6.4.1散列機(jī)制（1）612．散列函數(shù)使用散列方法，首先要有一個(gè)好的散列函數(shù)。由于在設(shè)計(jì)散列函數(shù)時(shí)不可能精確知道要存儲(chǔ)的記錄的查找鍵值，因此要求散列函數(shù)在把查找鍵值轉(zhuǎn)換成存儲(chǔ)地址（桶號(hào)）時(shí)，因滿足下面兩個(gè)條件：①地址的分布是均勻的：把所有可能的查找鍵值轉(zhuǎn)換成桶號(hào)以后，要求每個(gè)桶內(nèi)的查找鍵值數(shù)目大抵相同。②地址的分布是隨機(jī)的：所有散列函數(shù)值不受查找鍵值各種順序的影響，例如字母順序、長(zhǎng)度順序等。散列函數(shù)在數(shù)據(jù)結(jié)構(gòu)教材中已有詳細(xì)介紹，這里不再詳述。下面介紹常用的“質(zhì)數(shù)除余法”，把記錄的查找鍵值除以一個(gè)質(zhì)數(shù)，求得的余數(shù)作為桶號(hào)。為方便，下面例子中除數(shù)不是質(zhì)數(shù)，而是10。6.4.1散列機(jī)制（2）62例6.3對(duì)于圖6.1的數(shù)據(jù)，我們可以用散列方法存儲(chǔ)。假設(shè)查找鍵值是ENAME。散列函數(shù)用下列方法設(shè)計(jì)：把姓名字符串中每一個(gè)字符轉(zhuǎn)換成一個(gè)整數(shù)（按字母表中的順序），然后求出這些整數(shù)的和；假設(shè)存儲(chǔ)空間分成10個(gè)桶，把求得的“和”除以10，得到余數(shù)作為桶號(hào)；然后把記錄存入相應(yīng)的桶。例如“LIU”轉(zhuǎn)換成的整數(shù)和為42，除以桶數(shù)10，得到余數(shù)2，作為桶號(hào)，把LIU記錄存入桶號(hào)為2的桶內(nèi)。圖6.1的數(shù)據(jù)用散列方法組織的示意圖見圖6.29。散列函數(shù)應(yīng)仔細(xì)設(shè)計(jì)。設(shè)計(jì)得不好，造成各個(gè)桶內(nèi)的查找時(shí)間有長(zhǎng)有短；設(shè)計(jì)得好，各個(gè)桶內(nèi)的查找時(shí)間相差無(wú)幾，并且查找的平均時(shí)間是最小的。6.4.1散列機(jī)制（3）636.4.1散列機(jī)制（4）圖6.29查找鍵為ENAME的散列組織桶0ZHOUC-343750桶5桶1桶6ZHANGA-214600ZHANGB-467600桶2LIUA-102600桶7LIUB-215800LIUC-333400WENB-306700桶3HEF-257800桶8LOUB-428850桶4桶9643．桶溢出的處理在散列組織中，每個(gè)桶的空間是固定的，如果某個(gè)桶內(nèi)已裝滿記錄，還有新的記錄要插入到該桶，那么稱這種現(xiàn)象為“桶溢出”（也稱為“散列碰撞”）。產(chǎn)生桶溢出的原因主要有以下兩個(gè)： ●初始設(shè)計(jì)時(shí)桶數(shù)偏少。 ●由于散列函數(shù)的“均勻分布性”不好，造成某些桶存滿了記錄，而某些桶有較多空閑空間。在設(shè)計(jì)散列函數(shù)時(shí)，桶數(shù)應(yīng)放寬些，一般存儲(chǔ)空間應(yīng)有20%的余量，讓它空閑著，以利減少桶溢出的機(jī)會(huì)。但是不管散列函數(shù)如何好，再留有一定的存儲(chǔ)空間余量，桶溢出現(xiàn)象難免還會(huì)發(fā)生。因而我們?nèi)砸幸幌盗刑幚硪绯龅姆椒?，具體如下所述。6.4.1散列機(jī)制（5）65（1）溢出桶拉鏈法（溢出鏈法）：如果某個(gè)桶b（稱為基本桶）已裝滿記錄，還有新的記錄等待插入桶b，那么可以由系統(tǒng)提供一個(gè)溢出桶，用指針鏈接在桶b的后面。如果溢出桶也裝滿了，那么用類似的方法在其后面再鏈接一個(gè)溢出桶。這種方法稱為溢出鏈方法。圖6.30是這個(gè)方法的示意圖。6.4.1散列機(jī)制（6）桶0桶1桶2桶3桶1的溢出桶鏈圖6.30散列結(jié)構(gòu) 的溢出鏈66（2）開放式散列法（openhashing）這個(gè)方法是把桶的集合固定下來(lái)，也就是只考慮基本桶，不考慮溢出桶。如果有一個(gè)桶b裝滿了記錄，那么就在桶集中挑選一個(gè)有空閑空間的桶，裝入新記錄。就桶的選擇方法的不同，可分為下面兩種： ●線性探查法：在桶b的下面（以循環(huán)的次序）順序選擇一個(gè)有空閑空間的桶，把新記錄裝進(jìn)去。 ●再散列探查法：采用二次散列方法，跳躍式地選擇一個(gè)有空閑空間的桶，裝入新記錄。6.4.1散列機(jī)制（7）67上面開放式散列法一般使用在編譯或匯編中構(gòu)造符號(hào)表的情況。由于開放式散列法的刪除操作比較復(fù)雜，因此數(shù)據(jù)庫(kù)系統(tǒng)中使用封閉散列法。散列方法的缺點(diǎn)是在系統(tǒng)實(shí)現(xiàn)時(shí)必須選擇恰當(dāng)?shù)纳⒘泻瘮?shù)，并且不像索引結(jié)構(gòu)那樣隨著數(shù)據(jù)量的變化容易變動(dòng)。標(biāo)志散列組織裝滿程度的因子α稱為“裝填因子”或“負(fù)載因子”。α等于存儲(chǔ)記錄的空間量與給定的存儲(chǔ)空間量的商。一般α取0.6~0.8。如果α＞0.8，容易產(chǎn)生桶溢出； 如果α＜0.6，表示空間浪費(fèi)太多。6.4.1散列機(jī)制（8）68散列方法不僅可以用在文件組織上，也可以用在索引結(jié)構(gòu)的創(chuàng)建上?！吧⒘兴饕笔前巡檎益I值與指針一起組合成散列文件結(jié)構(gòu)的一種索引。散列索引的構(gòu)造方法如下：首先為主文件中每個(gè)查找鍵值建立一個(gè)索引記錄；然后把這些索引記錄組織成散列結(jié)構(gòu)（稱為“散列索引”），而不是稠密或稀疏索引結(jié)構(gòu)。例6.4對(duì)圖6.10的數(shù)據(jù)建立一個(gè)散列索引。查找鍵為ENO（工號(hào)），對(duì)每個(gè)查找鍵值建立一個(gè)索引記錄。散列函數(shù)可以這樣構(gòu)造：對(duì)工號(hào)中的數(shù)字部分，求出其和，然后除以7（即桶數(shù)為7），得到余數(shù)作為索引的桶地址。這樣，散列索引有7個(gè)桶。假設(shè)每個(gè)桶可放2個(gè)索引記錄，如果超過(guò)2個(gè)，就要鏈接溢出桶。對(duì)圖6.10的數(shù)據(jù)建立的散列索引如圖6.31所示。6.4.2散列索引（1）69在這個(gè)例子中，ENO是一個(gè)候選鍵，每個(gè)ENO值只與一個(gè)主記錄聯(lián)系。一般，查找鍵值可以與多個(gè)主記錄相聯(lián)系，那么散列索引中的指針或者指向一個(gè)主記錄，在主文件中再沿著指針鏈找到其它相應(yīng)記錄；或者指向一個(gè)桶，桶內(nèi)存放指向主記錄的指針。這些技術(shù)都是輔助索引中使用過(guò)的?！吧⒘兴饕边@個(gè)術(shù)語(yǔ)是指散列文件結(jié)構(gòu)，也可以指輔助散列索引。嚴(yán)格地講，散列索引是一種輔助索引結(jié)構(gòu)，不屬于主索引結(jié)構(gòu)。但是由于散列文件組織提供由索引直接找主記錄的方法，因此我們可以認(rèn)為散列文件組織提供了一個(gè)虛擬的主散列索引。6.4.2散列索引（2）70圖6.31在查找鍵ENO上的散列索引6.4.2散列索引（3）F-257B-428桶0A-214B-215桶1C-333B-306桶2A-102B-467桶3桶5桶6桶4C-343HEF-257800LIUA-102600LIUB-215800LIUC-333400LOUB-428850WENB-306700ZHANGA-214600ZHANGB-467600ZHOUC-34375071前面提到的散列技術(shù)屬于靜態(tài)散列，也就是在散列函數(shù)確定以后，所有的桶地址及桶空間都確定了。為了適應(yīng)DB的快速增長(zhǎng)，在使用靜態(tài)散列技術(shù)時(shí)，有三種選擇方案供用戶使用。 ●（1）在當(dāng)前文件規(guī)模的基礎(chǔ)上選擇一個(gè)散列函數(shù)。這種選擇在文件急劇增長(zhǎng)時(shí)，散列結(jié)構(gòu)的維護(hù)、改組和查詢的代價(jià)越來(lái)越大。 ●（2）在文件預(yù)計(jì)達(dá)到的規(guī)?；A(chǔ)上選擇散列函數(shù)。這種方案雖然適應(yīng)了未來(lái)的需要，但在初始一段時(shí)期內(nèi)，空間的利用率非常低。 ●（3）隨著數(shù)據(jù)量的增長(zhǎng)，周期性地選擇新的散列函數(shù)，重新組織散列文件。但重新組織的代價(jià)巨大。為了克服靜態(tài)索引的缺陷，在實(shí)際中往往使用動(dòng)態(tài)散列技術(shù)，即桶空間可隨時(shí)申請(qǐng)或釋放，而維護(hù)的代價(jià)又不大。下面介紹動(dòng)態(tài)散列中的一種技術(shù)——可擴(kuò)充散列結(jié)構(gòu)。6.4.3散列索引中的問(wèn)題72在靜態(tài)散列文件中有一種擴(kuò)充方法稱為“成倍擴(kuò)充法”。這種方法在需要時(shí)，把桶數(shù)擴(kuò)大一倍，從原來(lái)m個(gè)桶擴(kuò)大為2m個(gè)桶，而桶內(nèi)的記錄減少為原來(lái)的一半。但在數(shù)據(jù)量很大時(shí)，再擴(kuò)大一倍，空間代價(jià)太大，利用率也低?？蓴U(kuò)充散列結(jié)構(gòu)實(shí)際上是對(duì)成倍擴(kuò)充法的改進(jìn)，能從容地應(yīng)付數(shù)據(jù)庫(kù)經(jīng)常性的增長(zhǎng)或收縮，即桶的分裂或合并?？臻g利用率高，重新組織時(shí)，每次只是一個(gè)桶的增加或減少。1．可擴(kuò)充散列結(jié)構(gòu)的組織方法 首先選擇一個(gè)均勻性和隨機(jī)性都比較好的散列函數(shù)h。并且這個(gè)散列函數(shù)產(chǎn)生的函數(shù)值（簡(jiǎn)稱“散列值”）較大，是一個(gè)由b個(gè)二進(jìn)制位組成的整數(shù)。如果b=32，那么就有232（約4×109）個(gè)散列值，可以對(duì)應(yīng)232個(gè)桶。但是每個(gè)散列值并不立即對(duì)應(yīng)一個(gè)桶空間，而是根據(jù)實(shí)際需要申請(qǐng)或釋放。6.4.4可擴(kuò)充散列結(jié)構(gòu)（1）73在初始時(shí)，不是根據(jù)全部b位值得出桶地址，而是根據(jù)這個(gè)b位的前i位(高位)(0≤i≤b)得出桶地址值。在數(shù)據(jù)增長(zhǎng)過(guò)程中，取的位數(shù)i也隨之增加。這i位組成的值是一個(gè)桶號(hào)。所有的桶地址放在一張“桶地址表”中，桶地址的位置就是桶號(hào)。圖6.32是可擴(kuò)充散列結(jié)構(gòu)的示意圖。在桶地址表上方出現(xiàn)的i表示當(dāng)前情況是取散列值的前i位作為桶地址的位置。在桶地址表中，有時(shí)可能某幾個(gè)相鄰的項(xiàng)中的指針指向同一個(gè)桶。每個(gè)桶的上方出現(xiàn)的整數(shù)i0、i1、i2……表示這些桶是沿著散列值的前i0、i1、i2……位作為桶地址表中的地址尋找來(lái)的。桶地址表和桶的上方出現(xiàn)的i、i0、i1、i2……這些值稱為“散列前綴”。它們間的關(guān)系有ij≤i，這里ij是第j個(gè)桶的散列前綴。指向第j個(gè)桶的指針數(shù)目是2（i-ij）。6.4.4可擴(kuò)充散列結(jié)構(gòu)（2）74圖6.32可擴(kuò)充散列結(jié)構(gòu)6.4.4可擴(kuò)充散列結(jié)構(gòu)（3）桶2i…00…01…10…11i0散列前綴桶0，桶1i1i2桶2桶3桶地址表752．可擴(kuò)充散列結(jié)構(gòu)的操作 主要有查找、插入、刪除三類操作。（1）查找操作 設(shè)散列函數(shù)為h（K）。若查找鍵值為K1，桶地址表的散列前綴為i，那么首先求出h（K1）的前i位值m，然后沿著桶地址表位置m處的指針到達(dá)某一個(gè)桶中去找記錄。（2）插入操作 要插入一個(gè)查找鍵值為K1的記錄，首先要用查找操作找到應(yīng)插入的桶，譬如第j個(gè)桶。如果桶內(nèi)有空閑空間，直接插入即可。如果桶已裝滿記錄，那么必須分裂桶，重新分布記錄，并插入新記錄。分裂桶的過(guò)程分成兩種情況考慮：6.4.4可擴(kuò)充散列結(jié)構(gòu)（4）76第一種情況是：i=ij。也就是指向第j個(gè)桶的指針只有一個(gè)。這時(shí)應(yīng)在桶地址表中增加項(xiàng)數(shù)，以保證第j個(gè)桶分裂后，在桶地址表中有位置存放指向新桶的指針。用增加散列前綴的方法，也就是i的值增1，譬如原來(lái)i為4，對(duì)應(yīng)“桶地址表”中的16項(xiàng)，若i增為5，則對(duì)應(yīng)“桶地址表”中的32項(xiàng)。也就是每一項(xiàng)分裂成相鄰的兩項(xiàng)，此時(shí)桶地址采用了成倍擴(kuò)充法、但存儲(chǔ)數(shù)據(jù)的桶空間還沒有擴(kuò)大。桶地址表的空間要比存儲(chǔ)數(shù)據(jù)的桶空間小得多。 此時(shí)指向第j個(gè)桶的指針就有兩個(gè)。再申請(qǐng)一個(gè)桶空間（第z個(gè)桶），置第二個(gè)指針值為指向桶z，在置第j和第z個(gè)桶的散列前綴均為新的i值。接著，把原來(lái)第j個(gè)桶中的記錄根據(jù)散列值的前i位（已增1了）重新分配是仍留在第j個(gè)桶還是移到第z個(gè)桶。再把新記錄插入到第j或第z個(gè)桶。6.4.4可擴(kuò)充散列結(jié)構(gòu)（5）77 如果分裂以后，原來(lái)第j個(gè)桶的記錄仍全部留下，而新記錄還要插入到該桶，那么只能用上法把桶地址表再次擴(kuò)大。但這種可能性極小。一般，單記錄的插入不太可能造成桶地址表擴(kuò)大兩次。第二種情況是：i＞ij。此時(shí)指向第j個(gè)桶的指針至少兩個(gè)或兩個(gè)以上，那么桶地址表不必?cái)U(kuò)大。只要分裂第j個(gè)桶即可。申請(qǐng)一個(gè)桶空間（桶z）。對(duì)ij的值增1，置第j個(gè)桶的指針和第z個(gè)桶的散列前綴都為新的ij值。然后在桶地址表中原來(lái)指向第j個(gè)桶的指針中分出后一半指針，填上桶z的地址，而前一半指針仍指向桶j。再把第j個(gè)桶中的記錄按散列前綴確定的位數(shù)所表示的值重新分布的桶j或桶z中。再把新記錄插入到桶j或桶z中。在這兩種情況下重新分布記錄，只是對(duì)第j個(gè)桶的操作，而與其它桶無(wú)關(guān)。6.4.4可擴(kuò)充散列結(jié)構(gòu)（6）78（3）刪除操作 要?jiǎng)h除查找鍵值為K1的記錄，首先也是先用查找方法，把記錄找到，然后把記錄從所在的桶內(nèi)刪除。如果刪除后，桶為空，那么這個(gè)桶也要被刪除，也就是桶的合并操作。有時(shí)很可能會(huì)引起桶地址表的收縮（成倍地收縮）。6.4.4可擴(kuò)充散列結(jié)構(gòu)（7）796.4.4可擴(kuò)充散列結(jié)構(gòu)（8）例6.5對(duì)圖6.33的文件EMPLOYEE的數(shù)據(jù)，重建一個(gè)動(dòng)態(tài)散列文件結(jié)構(gòu)。設(shè)查找鍵為ENAME，有一個(gè)散列函數(shù)把查找鍵值轉(zhuǎn)換成的32位散列值如圖6.34所示。初始時(shí)，文件為空，如圖6.35所示。下面把圖6.33的記錄一個(gè)個(gè)插入到可擴(kuò)充散列文件中去。為示意，假設(shè)每個(gè)桶里只能放兩個(gè)記錄。ENAMEENOSALARYENAMEh（ENAME）HEF-257800HE00101101……LIUA-102600LIU10100011……LIUB-215800LOU11000111……LIUC-333400WEN00110101……LOUB-428850ZHANG11110001……WENB-306700ZHOU11011000……ZHANGA-214600ZHANGB-467600ZHOUC-343750圖6.33EMPLOYEE文件的數(shù)據(jù)圖6.34ENAME的散列值（32位，圖中只列出高位部分）80圖6.35初始的可擴(kuò)充散列結(jié)構(gòu)6.4.4可擴(kuò)充散列結(jié)構(gòu)（9）散列前綴00桶地址表0桶0圖6.36插入3個(gè)記錄后的散列結(jié)構(gòu)1HEF-257800桶0

0111LIUA-102600LIUB-215800桶181圖6.37插入4個(gè)記錄后的散列結(jié)構(gòu)6.4.4可擴(kuò)充散列結(jié)構(gòu)（10）1HEF-257800桶0

0111LIUC-333400溢出桶1LIUA-102600LIUB-215800桶11HEF-257800WENB-306700桶0，桶12LIUC-333400

2LIUA-102600LIUB-215800桶22LOUB-428850ZHANGA-214800桶32ZHANGB-467600

012

23圖6.38插入8個(gè)記錄后的散列結(jié)構(gòu)82圖6.39EMPLOYEE文件的可擴(kuò)充散列結(jié)構(gòu)6.4.4可擴(kuò)充散列結(jié)構(gòu)（11）1HEF-257800WENB-306700桶0,桶1,桶2,桶32LIUC-333400

2LIUA-102600LIUB-215800桶4，桶53LOUB-428850ZHOUC-343750桶6

013

23

45

673ZHANGA-214800ZHANGB-467600桶783與其它索引或散列技術(shù)比較，可擴(kuò)充散列技術(shù)有兩個(gè)顯著的優(yōu)點(diǎn)：①隨著文件的數(shù)據(jù)量增長(zhǎng)，仍然保持原有的操作和查詢性能。②空間開銷達(dá)到最小，額外的開銷是桶地址表，由于每個(gè)散列值只需一個(gè)指針，因此桶地址表只占少量空間。另外，存儲(chǔ)記錄的桶和溢出桶空間都能動(dòng)態(tài)地申請(qǐng)或釋放?？蓴U(kuò)充散列技術(shù)的缺點(diǎn)是比靜態(tài)散列多了一個(gè)桶地址表。由于桶的編號(hào)在桶分裂或合并后不斷變化，因此桶地址要存儲(chǔ)在桶地址表中，以利查找。但這個(gè)間接訪問(wèn)對(duì)文件的性能影響較小，系統(tǒng)和用戶都能接受。6.4.4可擴(kuò)充散列結(jié)構(gòu)（12）846.5多鍵訪問(wèn)6.5.1單鍵查詢的問(wèn)題6.5.2網(wǎng)格文件6.5.3分區(qū)散列技術(shù)85前面幾節(jié)提到的索引或散列技術(shù)只使用一個(gè)查找鍵來(lái)組織文件和處理查詢。有時(shí)，可利用多個(gè)索引處理查詢。例如EMPLOYEE文件有兩個(gè)索引，一個(gè)索引的查找鍵是ENAME，另一個(gè)索引的查找鍵是SALARY。用戶有一個(gè)查詢：“檢索職工LIU工資為600的工作部門編號(hào)”，可用下列SQL語(yǔ)句實(shí)現(xiàn)：

SELECTENO FROMEMPLOYEE WHEREENAME=“LIU”ANDSALARY=600；6.5.1單鍵查詢的問(wèn)題（1）86處理這個(gè)查詢有三種方法：（1）使用ENAME索引，把LIU的記錄全部找到，再檢查每個(gè)找到的記錄的SALARY是否為600。（2）使用SALARY索引，把SALARY為600的記錄全部找到，再檢查每個(gè)找到的記錄的姓名是否為L(zhǎng)IU。（3）使用ENAME索引，求出指向LIU記錄的指針集；使用SALARY索引，求出指向600的記錄的指針集。然后求出這兩個(gè)指針集的交集。最后沿著得到的指針把主記錄找到。這三種方法在多索引情況中都能使用，但都有這樣一個(gè)缺陷。如果LIU的記錄很多，工資為600的記錄很多，而LIU工資為600的記錄很少，那么上述三種方法都要掃描大量的指針，而最后只求出少量的記錄。6.5.1單鍵查詢的問(wèn)題（2）87有一個(gè)改進(jìn)的方法，把ENAME和SALARY一起作為一個(gè)查找鍵值，建立一個(gè)索引。這種索引與前面幾節(jié)提到的索引技術(shù)本質(zhì)上沒有什么區(qū)別，只是查找鍵中屬性個(gè)數(shù)不同而已。但是由多屬性構(gòu)成的有序索引，有一些弱點(diǎn)。例如查詢語(yǔ)句

SELECTENO FROMEMPLOYEE WHEREENAME＜ˊLIUˊANDSALARY=600對(duì)于姓名小于“LIU”的所有職工記錄，都要檢查其SALARY是否為600。由于這些記錄很可能存儲(chǔ)在不同的磁盤上，因此需要較多的I／O操作。原因是查詢語(yǔ)句中的條件是比較操作，不是等值操作。顯然，前面提到的索引技術(shù)不適宜于多鍵查找。下面介紹多鍵訪問(wèn)時(shí)采用的兩種技術(shù)：網(wǎng)格文件和分區(qū)散列。6.5.1單鍵查詢的問(wèn)題（3）88圖6.40是一個(gè)網(wǎng)格文件（gridfiles）的示意圖，查找鍵是EMPLOYEE文件中的ENAME和SALARY屬性。圖中二維矩陣稱為“網(wǎng)格矩陣”，一維數(shù)組稱為“線性標(biāo)尺”（linearscal