清華大學(xué)數(shù)據(jù)庫(kù)access課件第08章：索引和散列

第8章索引和散列講課內(nèi)容：索引的目的就是為了能夠快速地在文件中定位要訪問(wèn)的記錄，當(dāng)然，理想的做法是系統(tǒng)能夠直接定位這些記錄！為了實(shí)現(xiàn)這種訪問(wèn)數(shù)據(jù)的方式，需要一些附加結(jié)構(gòu)——索引，并將索引同數(shù)據(jù)文件聯(lián)系起來(lái)。在本章，只要不是特別指明，數(shù)據(jù)文件一般是指存儲(chǔ)數(shù)據(jù)記錄的文件，我們簡(jiǎn)稱(chēng)文件，而索引文件是指存儲(chǔ)索引記錄（或稱(chēng)之為索引項(xiàng)）的文件。■基本概念■散列文件組織■SQL中索引的定義■順序索引■散列索引■多碼訪問(wèn)■B＋樹(shù)索引文件■兩種索引的比較■本章總結(jié)12/13/20221第8章索引和散列講課內(nèi)容：12/12/20221§8.1基本概念基本索引順序索引：基于對(duì)值的一種排序；結(jié)構(gòu)：順序文件和B樹(shù)文件散列索引：基于將值平均、隨機(jī)地分布到若干存儲(chǔ)桶中：由1至32個(gè)連續(xù)的物理塊構(gòu)成的一種存儲(chǔ)結(jié)構(gòu)；與物理塊不同的是，存儲(chǔ)桶只能包含整記錄，即記錄可以跨塊存儲(chǔ)但不能跨桶存儲(chǔ)。一個(gè)值所屬的存儲(chǔ)桶由一個(gè)函數(shù)來(lái)決定，該函數(shù)稱(chēng)為散列函數(shù)，也叫哈稀函數(shù)；索引結(jié)構(gòu)是散列文件！12/13/20222§8.1基本概念基本索引12/12/20222§8.1基本概念索引技術(shù)的評(píng)價(jià)標(biāo)準(zhǔn)沒(méi)有哪一種索引技術(shù)是最好的，每種索引都有自己適合的數(shù)據(jù)庫(kù)應(yīng)用。對(duì)索引技術(shù)的評(píng)價(jià)必須考慮以下因素：訪問(wèn)類(lèi)型：能有效支持的數(shù)據(jù)訪問(wèn)類(lèi)型，包括根據(jù)指定的屬性值進(jìn)行查詢(xún)，或根據(jù)給定屬性值的范圍進(jìn)行查詢(xún)。訪問(wèn)時(shí)間：訪問(wèn)一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)所需要的時(shí)間。插入時(shí)間：在文件中插入一個(gè)新數(shù)據(jù)項(xiàng)所需要的時(shí)間，包括找到插入該項(xiàng)的正確位置和修改索引所需要的時(shí)間。12/13/20223§8.1基本概念索引技術(shù)的評(píng)價(jià)標(biāo)準(zhǔn)12/12/20223§8.1基本概念索引技術(shù)的評(píng)價(jià)標(biāo)準(zhǔn)沒(méi)有哪一種索引技術(shù)是最好的，每種索引都有自己適合的數(shù)據(jù)庫(kù)應(yīng)用。對(duì)索引技術(shù)的評(píng)價(jià)必須考慮以下因素：刪除時(shí)間：在文件中刪除一個(gè)數(shù)據(jù)項(xiàng)所需要的時(shí)間，包括找到待刪除項(xiàng)的正確位置和修改索引所需要的時(shí)間。更新時(shí)間：U=D+I（在位與異位）空間開(kāi)銷(xiāo)：索引結(jié)構(gòu)所需要的額外存儲(chǔ)空間；索引是用空間的代價(jià)來(lái)?yè)Q取系統(tǒng)性能的提高。索引實(shí)現(xiàn)的難度決定了該索引技術(shù)是否實(shí)用、能否推廣。12/13/20224§8.1基本概念索引技術(shù)的評(píng)價(jià)標(biāo)準(zhǔn)12/12/20224§8.2順序索引順序索引的作用能迅速地按順序或隨機(jī)地訪問(wèn)文件中的記錄順序索引的結(jié)構(gòu)在邏輯上按順序存儲(chǔ)搜索碼的值，并將搜索碼值與包含該搜索碼值的記錄關(guān)聯(lián)起來(lái)。順序索引的特征一個(gè)文件可以有多個(gè)索引，對(duì)應(yīng)于不同的搜索碼。根據(jù)索引結(jié)構(gòu)中搜索碼值的邏輯順序和數(shù)據(jù)文件中記錄的物理存儲(chǔ)順序之間的關(guān)系，順序索引分為主索引和輔助索引。12/13/20225§8.2順序索引順序索引的作用12/12/20225§8.2順序索引基本概念主索引與輔助索引如果數(shù)據(jù)文件中記錄按照某個(gè)搜索碼指定的順序物理存儲(chǔ)，則該搜索碼對(duì)應(yīng)的索引稱(chēng)為主索引或簇集索引；相反，搜索碼順序與數(shù)據(jù)文件中記錄的物理順序不同的那些索引稱(chēng)為輔助索引或非簇集索引；顯然，一個(gè)數(shù)據(jù)文件只能有一個(gè)主索引，但可以有多個(gè)輔助索引，為什么？堆文件與索引順序文件沒(méi)有主索引的數(shù)據(jù)文件就是堆文件；而擁有主索引的數(shù)據(jù)文件就是索引順序文件。12/13/20226§8.2順序索引基本概念12/12/20226§8.2順序索引索引順序文件數(shù)據(jù)文件中的記錄按照某個(gè)搜索碼值的順序物理存儲(chǔ)：12/13/20227§8.2順序索引索引順序文件12/12/20227§8.2順序索引順序索引的分類(lèi)按照索引結(jié)構(gòu)中搜索碼值與數(shù)據(jù)文件中搜索碼值的對(duì)應(yīng)關(guān)系，順序索引又分為：稠密索引稀疏索引稠密索引：對(duì)應(yīng)文件中搜索碼的每一個(gè)值都有一個(gè)索引記錄(或索引項(xiàng))，它包括：搜索碼值；指向具有該搜索碼值的第一個(gè)數(shù)據(jù)記錄的指針。12/13/20228§8.2順序索引順序索引的分類(lèi)12/12/20228§8.2順序索引順序索引的分類(lèi)稀疏索引：只為搜索碼的部分值建立索引項(xiàng)；與稠密索引一樣，每個(gè)索引項(xiàng)也包括搜索碼值和指向具有該搜索碼值的第一個(gè)數(shù)據(jù)記錄的指針。問(wèn)題：如何利用稀疏索引進(jìn)行查詢(xún)呢？12/13/20229§8.2順序索引順序索引的分類(lèi)問(wèn)題：如何利用稀疏索引進(jìn)行查詢(xún)SQLSERVER主索引的問(wèn)題？搜索碼鏈表的作用記錄的惟一標(biāo)識(shí)是F#:P#:S#索引中索引項(xiàng)的指針是？頁(yè)頭：96字節(jié)數(shù)據(jù)行，即記錄176行偏移數(shù)組：鏈表095Mianus(96)…Downtown(136).Brighton(176).Downtown(216).13621696

3210頁(yè)號(hào)：010§8.2順序索引各行順序號(hào)(槽號(hào))RID是01:010:01的記錄的搜索碼是Downtown12/13/202210SQLSERVER頁(yè)頭：數(shù)據(jù)行，即記錄176行偏移數(shù)組：鏈§8.2順序索引稠密索引和稀疏索引的比較利用稠密索引通?？梢员认∈杷饕斓囟ㄎ灰粋€(gè)記錄的位置；與稠密索引相比，稀疏索引占用空間小，插入和刪除時(shí)的維護(hù)開(kāi)銷(xiāo)也小。實(shí)踐中如何正確地建立稀疏索引？數(shù)據(jù)庫(kù)查詢(xún)的開(kāi)銷(xiāo)主要是由什么來(lái)決定的？在主存內(nèi)掃描整個(gè)塊的時(shí)間是可以忽略的；考慮為每個(gè)塊建一個(gè)索引項(xiàng)的稀疏索引，這樣的索引可以定位包含所要查找記錄的塊。12/13/202211§8.2順序索引稠密索引和稀疏索引的比較12/12/2022§8.2順序索引多級(jí)索引問(wèn)題的提出：即使采用稀疏索引，索引本身有時(shí)也會(huì)變得非常龐大而難于有效處理，例如：一個(gè)文件有100000條記錄；一個(gè)塊存儲(chǔ)10個(gè)記錄，每個(gè)塊有一個(gè)索引記錄；一個(gè)塊存儲(chǔ)100個(gè)索引記錄。索引過(guò)大在讀索引時(shí)就必須有一部分放在磁盤(pán)上，搜索一個(gè)索引項(xiàng)就必須多次讀磁盤(pán)塊：當(dāng)然在索引上可以用二分法來(lái)定位索引項(xiàng)，最壞需要讀log2(b)次塊，假設(shè)索引占據(jù)了b個(gè)塊。如果索引小到一次I/O就能夠放到主存里，搜索一個(gè)索引項(xiàng)的時(shí)間就很短，可以忽略不計(jì)。12/13/202212§8.2順序索引多級(jí)索引12/12/202212§8.2順序索引多級(jí)索引問(wèn)題的解決：像對(duì)待其他任何順序文件那樣對(duì)待索引結(jié)構(gòu)，即在主索引上再構(gòu)造一個(gè)稀疏索引，形成一個(gè)具有內(nèi)層索引和外層索引的多級(jí)索引結(jié)構(gòu)：主索引結(jié)構(gòu)本身就是一個(gè)順序文件12/13/202213§8.2順序索引多級(jí)索引主索引結(jié)構(gòu)本身就是一個(gè)順序文件12/§8.2順序索引索引的更新刪除數(shù)據(jù)記錄，稠密索引的變化情況：①刪除數(shù)據(jù)文件中的“鄧婉玲”記錄；②刪除數(shù)據(jù)文件中“王小麗”的s000005記錄；③刪除數(shù)據(jù)文件中“王小麗”的s000009記錄。12/13/202214§8.2順序索引索引的更新12/12/202214§8.2順序索引索引的更新刪除數(shù)據(jù)記錄，稀疏索引的變化情況：①刪除文件中搜索碼為“陳舒藝”的記錄；②刪除文件中搜索碼為“陳國(guó)國(guó)”的所有記錄；③刪除文件中搜索碼為“馮藹妍”記錄；④刪除文件中“王小麗”的s000005記錄；⑤刪除文件中“王小麗”的s000007記錄。12/13/202215§8.2順序索引索引的更新12/12/202215§8.2順序索引索引的更新插入數(shù)據(jù)記錄，索引的變化情況：若索引是稠密的，并且待插入記錄的搜索碼值不在索引中，就要把該搜索碼值插入到索引中；若索引是為每個(gè)塊保存一個(gè)索引項(xiàng)的稀疏索引：只要沒(méi)有新塊產(chǎn)生，索引就無(wú)需做任何改動(dòng)；在產(chǎn)生新塊的情況下，新塊中的第一個(gè)搜索碼值將被插入到索引中。多級(jí)索引：刪除和插入數(shù)據(jù)記錄時(shí)，它的更新同上面類(lèi)似：內(nèi)層索引的更新同上；內(nèi)層索引的變化，引起外層索引按上述算法更新。12/13/202216§8.2順序索引索引的更新12/12/202216§8.2順序索引輔助索引在文件中，記錄按主索引而不是輔助索引的搜索碼值順序物理存儲(chǔ)；具有同一個(gè)輔助搜索碼值的記錄可能分布在文件的各個(gè)地方，例如：12/13/202217§8.2順序索引輔助索引12/12/202217§8.2順序索引輔助索引其結(jié)構(gòu)與主索引的結(jié)構(gòu)是不同的：輔助索引必須包含指向每一記錄的指針；輔助索引的指針并不直接指向文件，而是每個(gè)指針指向一個(gè)包含文件指針的存儲(chǔ)桶；存儲(chǔ)桶中的每個(gè)指針才指向文件中的記錄。12/13/202218§8.2順序索引輔助索引12/12/202218§8.2順序索引輔助索引輔助索引的優(yōu)缺點(diǎn)：可以提高使用利用輔助搜索碼查詢(xún)記錄的速度；但輔助索引也大大增加了數(shù)據(jù)庫(kù)更新的開(kāi)銷(xiāo)。12/13/202219§8.2順序索引輔助索引12/12/202219§8.3B+樹(shù)索引文件索引順序文件的缺陷性能：索引順序文件組織最大的缺點(diǎn)在于隨著文件的增大，索引查找性能和順序掃描性能都會(huì)下降。文件重組：而且隨著頻繁的刪除和插入記錄，就會(huì)不斷有溢出塊出現(xiàn)，記錄的物理順序同主搜索碼順序的一致性就遭到破壞，這樣就不得不重組文件。解決方案呢？研究在插入和刪除操作很頻繁的情況下仍保持有效的索引結(jié)構(gòu)：B+樹(shù)索引就是其中的一種。12/13/202220§8.3B+樹(shù)索引文件索引順序文件的缺陷12/12/2022§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)總體結(jié)構(gòu)：是一個(gè)多級(jí)索引，但其結(jié)構(gòu)不同于多級(jí)順序索引采用平衡樹(shù)結(jié)構(gòu)：即每個(gè)葉結(jié)點(diǎn)到根的路徑長(zhǎng)度都相同。每個(gè)非葉結(jié)點(diǎn)有n/2到n個(gè)子女，n對(duì)特定樹(shù)是固定的；它的所有結(jié)點(diǎn)結(jié)構(gòu)都相同，最多包含n-1個(gè)搜索碼值K1、K2、…、Kn-1及n個(gè)指針P1、P2、…、Pn；每個(gè)結(jié)點(diǎn)中的搜索碼值按次序存放，即若i<j，那么一定有Ki<Kj。12/13/202221§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)12/12/202221§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)葉結(jié)點(diǎn)：指針Pi(i=1,2,…,n-1)指向具有搜索碼值Ki的一個(gè)數(shù)據(jù)記錄或一個(gè)指針桶，桶中的每個(gè)指針指向具有搜索碼值Ki的一個(gè)數(shù)據(jù)記錄。指針桶只在記錄不按搜索碼順序物理存儲(chǔ)時(shí)才使用指針Pn具有特殊的作用。每個(gè)葉結(jié)點(diǎn)最多可有n-1個(gè)搜索碼值，最少也要有(n-1)/2個(gè)搜索碼值；各個(gè)葉結(jié)點(diǎn)的搜索碼值的范圍互不相交；要使B+樹(shù)索引成為稠密索引，文件中各搜索碼值就都必須在某個(gè)葉結(jié)點(diǎn)中出現(xiàn)且只能出現(xiàn)一次；12/13/202222§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)12/12/202222B+樹(shù)索引結(jié)構(gòu)葉結(jié)點(diǎn)：各葉結(jié)點(diǎn)按照所含的搜索碼值有一個(gè)線性順序，利用指針Pn將葉結(jié)點(diǎn)按搜索碼順序鏈接在一起；這種排序能高效地對(duì)文件進(jìn)行順序處理，而B(niǎo)+樹(shù)索引的其他結(jié)構(gòu)能高效地對(duì)文件進(jìn)行隨機(jī)處理?！?.3B+樹(shù)索引文件12/13/202223B+樹(shù)索引結(jié)構(gòu)§8.3B+樹(shù)索引文件12/12/202223B+樹(shù)索引結(jié)構(gòu)非葉結(jié)點(diǎn)：B+樹(shù)索引的非葉結(jié)點(diǎn)形成葉結(jié)點(diǎn)上的一個(gè)多級(jí)稀疏索引；非葉結(jié)點(diǎn)的結(jié)構(gòu)和葉結(jié)點(diǎn)的結(jié)構(gòu)相同，即含有能夠存儲(chǔ)n-1個(gè)搜索碼值和n個(gè)指針的存儲(chǔ)單元。只不過(guò)非葉結(jié)點(diǎn)中的所有指針都指向樹(shù)中的結(jié)點(diǎn)；如果一個(gè)非葉結(jié)點(diǎn)有m個(gè)指針，則n/2≤m≤n。若m<n，則非葉結(jié)點(diǎn)中指針Pm之后的所有空閑空間作為預(yù)留空間，與葉結(jié)點(diǎn)的區(qū)別在于結(jié)點(diǎn)的最后一個(gè)指針Pm和Pn的位置與指向；§8.3B+樹(shù)索引文件12/13/202224B+樹(shù)索引結(jié)構(gòu)§8.3B+樹(shù)索引文件12/12/202224§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)非葉結(jié)點(diǎn)：在含有m個(gè)指針的非葉結(jié)點(diǎn)中，Pi(i=2,…,m-1)指向一棵子樹(shù)，該子樹(shù)的所有結(jié)點(diǎn)的搜索碼值大于等于Ki-1而小于Ki；指針Pm指向子樹(shù)中所含搜索碼值大于等于Km-1的那一部分；而指針P1指向子樹(shù)中所含搜索碼值小于K1的那一部分。12/13/202225§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)12/12/202225§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)根結(jié)點(diǎn)：根結(jié)點(diǎn)的結(jié)構(gòu)也與葉結(jié)點(diǎn)的結(jié)構(gòu)相同；根結(jié)點(diǎn)包含的指針數(shù)可能小于n/2，除非整棵樹(shù)只有一個(gè)結(jié)點(diǎn)，否則它至少包含兩個(gè)指針。12/13/202226§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)12/12/202226§8.3B+樹(shù)索引文件B+樹(shù)索引缺點(diǎn)B+樹(shù)的“平衡”(Balance)特征保證了B+樹(shù)索引具有良好的查找、插入和修改性能，但B+樹(shù)索引也有以下缺陷：B+樹(shù)索引結(jié)構(gòu)會(huì)增加文件插入和刪除處理的空間開(kāi)銷(xiāo)，以空間代價(jià)換取性能上的優(yōu)勢(shì)；B+樹(shù)索引結(jié)構(gòu)在極端情況下，結(jié)點(diǎn)可以是半空的(n/2到n)，這雖然造成了空間浪費(fèi)，但缺保證了性能。B+樹(shù)索引技術(shù)已經(jīng)被廣泛地應(yīng)用到商業(yè)數(shù)據(jù)庫(kù)管理系統(tǒng)中。12/13/202227§8.3B+樹(shù)索引文件B+樹(shù)索引缺點(diǎn)12/12/202227§8.3B+樹(shù)索引文件B+樹(shù)上的查詢(xún)?nèi)绾卫肂+樹(shù)索引進(jìn)行查詢(xún)呢？假設(shè)要找出搜索碼值為K的所有記錄：首先檢查根結(jié)點(diǎn)，找到大于K的最小搜索碼值，假設(shè)是Ki，那么沿著指針Pi走到另一個(gè)結(jié)點(diǎn)；如果K<K1，則沿著指針P1走至另一個(gè)結(jié)點(diǎn)；如果K≥Km-1(m是該結(jié)點(diǎn)的指針數(shù))，則沿著指針Pm走至另一個(gè)結(jié)點(diǎn)；對(duì)新到達(dá)的結(jié)點(diǎn)，重復(fù)以上步驟，最終到達(dá)一個(gè)葉結(jié)點(diǎn)。12/13/202228§8.3B+樹(shù)索引文件B+樹(shù)上的查詢(xún)12/12/202228§8.3B+樹(shù)索引文件B+樹(shù)上的查詢(xún)舉例：利用student關(guān)系上的B+樹(shù)索引，給出在該關(guān)系中查找student_name為“鄧婉玲”的所有記錄的過(guò)程：12/13/202229§8.3B+樹(shù)索引文件B+樹(shù)上的查詢(xún)12/12/202229§8.3B+樹(shù)索引文件B+樹(shù)的更新很煩瑣，《數(shù)據(jù)結(jié)構(gòu)》課程講的內(nèi)容。B+樹(shù)文件組織B+樹(shù)索引通過(guò)在葉結(jié)點(diǎn)來(lái)組織包含真實(shí)記錄的物理塊來(lái)解決索引順序文件組織隨著文件的增大而性能下降的缺點(diǎn)：在B+樹(shù)文件組織中，B+樹(shù)結(jié)構(gòu)不僅用做索引，同時(shí)也是文件中記錄的組織者。樹(shù)葉結(jié)點(diǎn)中存儲(chǔ)的是記錄而不是指向記錄的指針。12/13/202230§8.3B+樹(shù)索引文件B+樹(shù)的更新12/12/202230基本概念在前面介紹的索引類(lèi)型中，必須訪問(wèn)該索引結(jié)構(gòu)，才能在文件中定位記錄。而基于散列(Hash)的文件組織能夠避免訪問(wèn)索引結(jié)構(gòu)；在散列文件組織中，用存儲(chǔ)桶來(lái)表示能存儲(chǔ)一條或多條記錄的一個(gè)存儲(chǔ)單位。通過(guò)計(jì)算搜索碼上的一個(gè)函數(shù)，就可以確定包含該搜索碼值的記錄應(yīng)該存儲(chǔ)在哪個(gè)桶中；令K表示所有搜索碼值的集合，令B表示所有桶地址的集合，散列函數(shù)h就是一個(gè)從K到B的函數(shù)：h(K)B或B=h(K)?！?.4散列文件組織12/13/202231基本概念§8.4散列文件組織12/12/202231散列文件的操作插入：為了插入一個(gè)搜索碼為Ki的記錄，通過(guò)計(jì)算h(Ki)獲得存放該記錄的桶地址。于是就把這條記錄存入桶中或是相應(yīng)的溢出桶中；刪除：如果待刪除記錄的搜索碼值是Ki，則計(jì)算h(Ki)，然后在相應(yīng)的桶中搜尋此記錄并刪除它；基于搜索碼值Ki的查找：首先計(jì)算h(Ki)，然后在計(jì)算出地址的桶中搜索所有的記錄。因?yàn)椴煌乃阉鞔a值對(duì)應(yīng)相同的桶地址正是散列文件組織的最大特點(diǎn)?！?.4散列文件組織12/13/202232散列文件的操作§8.4散列文件組織12/12/202232散列函數(shù)如果散列函數(shù)設(shè)計(jì)的不好，就有可能把所有的搜索碼值都映射到同一個(gè)存儲(chǔ)桶中，這時(shí)散列就失去了意義。因此，對(duì)散列函數(shù)的基本要求是：分布是均勻的：即每個(gè)存儲(chǔ)桶從所有可能的搜索碼值集合中分配到的值的個(gè)數(shù)差不多相同，例如將大寫(xiě)英文字母分配到5個(gè)存儲(chǔ)桶中；分布是隨機(jī)的：不管搜索碼值的實(shí)際情況是怎樣的，每個(gè)存儲(chǔ)桶應(yīng)分配到的搜索碼值的個(gè)數(shù)也差不多相同。例如，假設(shè)實(shí)際的搜索碼值是A、B、C、D、E五個(gè)字母?！?.4散列文件組織12/13/202233散列函數(shù)§8.4散列文件組織12/12/202233散列函數(shù)舉例：假設(shè)將26個(gè)大寫(xiě)英文字母分布到5個(gè)存儲(chǔ)桶中(地址從0到4)，那么散列函數(shù)h該如何設(shè)計(jì)呢？假設(shè)用code(A)表示A所對(duì)應(yīng)的編號(hào)0，……；散列函數(shù)h=code(SearchKey)mod5?！?.4散列文件組織12/13/202234散列函數(shù)§8.4散列文件組織12/12/202234問(wèn)題的提出散列不僅可以用于數(shù)據(jù)文件中記錄的組織，還可以用于索引中索引項(xiàng)的組織。散列索引：將索引項(xiàng)中的搜索碼及相應(yīng)的指針按散列文件的形式進(jìn)行組織。散列索引的構(gòu)造首先將散列函數(shù)作用于索引項(xiàng)中的搜索碼以確定對(duì)應(yīng)的存儲(chǔ)桶；然后將此搜索碼及相應(yīng)的指針存入此存儲(chǔ)桶中，而指針指向數(shù)據(jù)文件中的記錄?！?.5散列索引12/13/202235問(wèn)題的提出§8.5散列索引12/12/202235舉例：為關(guān)系student上的student_number搜索碼建立一個(gè)輔助的散列索引?！?.5散列索引散列函數(shù)h是學(xué)號(hào)各位數(shù)字之和后模3該散列索引共有3個(gè)桶，每個(gè)桶的大小為312/13/202236舉例：為關(guān)系student上的student_number搜小結(jié)術(shù)語(yǔ)“散列文件”是指用來(lái)組織和存儲(chǔ)文件中數(shù)據(jù)記錄的散列文件結(jié)構(gòu)。而散列索引是指將文件上的輔助索引的索引項(xiàng)按照散列文件的結(jié)構(gòu)進(jìn)行組織，不要將二者混淆；如果數(shù)據(jù)文件自身是按散列組織的，就認(rèn)為該散列文件已經(jīng)有了一個(gè)“主索引”，一般不必在其上另外創(chuàng)建獨(dú)立的索引結(jié)構(gòu)；散列索引只用來(lái)組織數(shù)據(jù)文件上的輔助索引數(shù)據(jù)文件上的主索引結(jié)構(gòu)不應(yīng)該是散列文件索引本身的文件結(jié)構(gòu)有哪些？§8.5散列索引12/13/202237小結(jié)§8.5散列索引12/12/202237用索引還是散列？索引和散列都為訪問(wèn)數(shù)據(jù)提供了存取路徑：索引需要通過(guò)值的比較，才能確定數(shù)據(jù)的位置；散列不通過(guò)值的比較，而通過(guò)值的含義來(lái)確定數(shù)據(jù)的位置的。用索引還是散列實(shí)際當(dāng)中要考慮以下問(wèn)題：索引或散列的周期性重組代價(jià)如何？在文件中插入和刪除記錄的頻率如何？為了優(yōu)化平均訪問(wèn)時(shí)間而導(dǎo)致最壞情況下的訪問(wèn)時(shí)間的做法是否可??？能夠有效支持的查詢(xún)類(lèi)型是哪些？§8.6順序索引和散列的比較12/13/202238用索引還是散列？§8.6順序索引和散列的比較12/12/20散列支持的查詢(xún)類(lèi)型等值查詢(xún)，或者叫點(diǎn)查詢(xún)范圍檢索散列與索引比較舉例之一selectA1,A2,…,AnfromrwhereAi=c順序索引查找所需要的時(shí)間與關(guān)系r中Ai值的個(gè)數(shù)的對(duì)數(shù)成正比；而在散列文件中，平均查找時(shí)間是一個(gè)與數(shù)據(jù)庫(kù)大小無(wú)關(guān)的常數(shù)；使用索引時(shí)，最壞情況下的查找時(shí)間和關(guān)系r中Ai值的個(gè)數(shù)的對(duì)數(shù)成正比；而散列文件在最壞情況下可能需要搜索所有記錄?！?.6順序索引和散列的比較12/13/202239散列支持的查詢(xún)類(lèi)型§8.6順序索引和散列的比較12/12/2索引支持的查詢(xún)類(lèi)型范圍檢索等值查詢(xún)，或者叫點(diǎn)查詢(xún)散列與索引比較舉例之二selectA1,A2,…,AnfromrwhereAi>=c1ANDAi<=c2使用索引時(shí)，首先確定數(shù)據(jù)c1所在的位置，然后順著索引順序文件中的搜索碼鏈表或B+樹(shù)索引中的葉結(jié)點(diǎn)的Pn指針鏈繼續(xù)查找，直到確定數(shù)據(jù)c2的位置為止；如果使用散列，由于散列函數(shù)的隨機(jī)性，將不得不讀取散列文件的所有存儲(chǔ)桶?！?.6順序索引和散列的比較12/13/202240索引支持的查詢(xún)類(lèi)型§8.6順序索引和散列的比較12/12/2索引的創(chuàng)建與刪除原則上，DBMS可以自動(dòng)決定創(chuàng)建什么樣的索引，但實(shí)際上很少這樣做。DBA和程序員都可以使用SQLDDL來(lái)創(chuàng)建和刪除索引：創(chuàng)建索引createindex<index_name>on<relation_name>(<attribute_list>)createindexs_indexonstudent(student_name)刪除索引dropindex<index-name>DBMS為優(yōu)化查詢(xún)而自動(dòng)創(chuàng)建的索引是不能用drop語(yǔ)句刪除的。§8.7SQL中索引的定義12/13/202241索引的創(chuàng)建與刪除§8.7SQL中索引的定義12/12/202問(wèn)題的提出到目前為止，都隱含地假設(shè)在關(guān)系上查詢(xún)時(shí)只使用一個(gè)索引或散列；如果存在多個(gè)索引，該如何處理呢？例如：假設(shè)文件student上有兩個(gè)索引，分別建立在student_name和department_name上。考慮如下查詢(xún)：selectstudent_numberfromstudentwherestudent_name=“陳國(guó)圍”ANDdepartment_name=“計(jì)算機(jī)系”問(wèn)題：對(duì)于這個(gè)查詢(xún)，如何利用上面已有的兩個(gè)索引呢？§8.8多碼訪問(wèn)12/13/202242問(wèn)題的提出§8.8多碼訪問(wèn)12/12/202242多個(gè)索引的利用處理前面的查詢(xún)有三種策略：利用student_name上的索引，找出“陳國(guó)圍”的所有記錄，然后檢查每條記錄是否滿(mǎn)足條件：department_name=“計(jì)算機(jī)系”；利用department_name上的索引，找出所有“計(jì)算機(jī)系”的記錄，然后檢查每條記錄是否滿(mǎn)足條件：student_name=“陳國(guó)圍”；利用上述兩個(gè)索引分別找出指向滿(mǎn)足各自條件的所有記錄的索引指針，然后計(jì)算這兩個(gè)指針集的交集即可得到結(jié)果。§8.8多碼訪問(wèn)12/13/202243多個(gè)索引的利用§8.8多碼訪問(wèn)12/12/202243多個(gè)索引的利用上面三種策略中，只有第三個(gè)方案同時(shí)利用了兩個(gè)索引。但它有可能是最糟糕的選擇：名字是“陳國(guó)圍”的記錄太多；“計(jì)算機(jī)系”的學(xué)生記錄太多；“計(jì)算機(jī)系”中名字為“陳國(guó)圍”的記錄很少。這樣的話(huà)，為了得到一個(gè)很小的結(jié)果，將不得不掃描大量的指針；最好的解決方案是在復(fù)合搜索碼：(student_name,department_name)上建立并使用索引，這樣的索引叫復(fù)合索引§8.8多碼訪問(wèn)12/13/202244多個(gè)索引的利用§8.8多碼訪問(wèn)12/12/202244B+樹(shù)與B樹(shù)結(jié)構(gòu)簇集索引采用B+樹(shù)結(jié)構(gòu)：簇集索引的葉級(jí)頁(yè)是真正的數(shù)據(jù)頁(yè)。非簇集索引采用B樹(shù)結(jié)構(gòu)?！?.9SQLServer的索引結(jié)構(gòu)12/13/202245B+樹(shù)與B樹(shù)結(jié)構(gòu)§8.9SQLServer的索引結(jié)構(gòu)12/B+樹(shù)與B樹(shù)結(jié)構(gòu)查詢(xún)舉例：§8.9SQLServer的索引結(jié)構(gòu)12/13/202246B+樹(shù)與B樹(shù)結(jié)構(gòu)§8.9SQLServer的索引結(jié)構(gòu)12/小結(jié)：索引與散列存取路徑的實(shí)現(xiàn)策略索引、散列、簇集索引本身的文件結(jié)構(gòu)類(lèi)型主索引的特征與結(jié)構(gòu)散列文件與散列索引的區(qū)別B+樹(shù)索引的結(jié)構(gòu)特征實(shí)踐中如何正確地建立索引？一個(gè)巨大的關(guān)系表DBMS的參數(shù)與性能調(diào)整工具復(fù)合索引12/13/202247小結(jié)：索引與散列存取路徑的實(shí)現(xiàn)策略12/12/202247第8章索引和散列講課內(nèi)容：索引的目的就是為了能夠快速地在文件中定位要訪問(wèn)的記錄，當(dāng)然，理想的做法是系統(tǒng)能夠直接定位這些記錄！為了實(shí)現(xiàn)這種訪問(wèn)數(shù)據(jù)的方式，需要一些附加結(jié)構(gòu)——索引，并將索引同數(shù)據(jù)文件聯(lián)系起來(lái)。在本章，只要不是特別指明，數(shù)據(jù)文件一般是指存儲(chǔ)數(shù)據(jù)記錄的文件，我們簡(jiǎn)稱(chēng)文件，而索引文件是指存儲(chǔ)索引記錄（或稱(chēng)之為索引項(xiàng)）的文件?！龌靖拍睢錾⒘形募M織■SQL中索引的定義■順序索引■散列索引■多碼訪問(wèn)■B＋樹(shù)索引文件■兩種索引的比較■本章總結(jié)12/13/202248第8章索引和散列講課內(nèi)容：12/12/20221§8.1基本概念基本索引順序索引：基于對(duì)值的一種排序；結(jié)構(gòu)：順序文件和B樹(shù)文件散列索引：基于將值平均、隨機(jī)地分布到若干存儲(chǔ)桶中：由1至32個(gè)連續(xù)的物理塊構(gòu)成的一種存儲(chǔ)結(jié)構(gòu)；與物理塊不同的是，存儲(chǔ)桶只能包含整記錄，即記錄可以跨塊存儲(chǔ)但不能跨桶存儲(chǔ)。一個(gè)值所屬的存儲(chǔ)桶由一個(gè)函數(shù)來(lái)決定，該函數(shù)稱(chēng)為散列函數(shù)，也叫哈稀函數(shù)；索引結(jié)構(gòu)是散列文件！12/13/202249§8.1基本概念基本索引12/12/20222§8.1基本概念索引技術(shù)的評(píng)價(jià)標(biāo)準(zhǔn)沒(méi)有哪一種索引技術(shù)是最好的，每種索引都有自己適合的數(shù)據(jù)庫(kù)應(yīng)用。對(duì)索引技術(shù)的評(píng)價(jià)必須考慮以下因素：訪問(wèn)類(lèi)型：能有效支持的數(shù)據(jù)訪問(wèn)類(lèi)型，包括根據(jù)指定的屬性值進(jìn)行查詢(xún)，或根據(jù)給定屬性值的范圍進(jìn)行查詢(xún)。訪問(wèn)時(shí)間：訪問(wèn)一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)所需要的時(shí)間。插入時(shí)間：在文件中插入一個(gè)新數(shù)據(jù)項(xiàng)所需要的時(shí)間，包括找到插入該項(xiàng)的正確位置和修改索引所需要的時(shí)間。12/13/202250§8.1基本概念索引技術(shù)的評(píng)價(jià)標(biāo)準(zhǔn)12/12/20223§8.1基本概念索引技術(shù)的評(píng)價(jià)標(biāo)準(zhǔn)沒(méi)有哪一種索引技術(shù)是最好的，每種索引都有自己適合的數(shù)據(jù)庫(kù)應(yīng)用。對(duì)索引技術(shù)的評(píng)價(jià)必須考慮以下因素：刪除時(shí)間：在文件中刪除一個(gè)數(shù)據(jù)項(xiàng)所需要的時(shí)間，包括找到待刪除項(xiàng)的正確位置和修改索引所需要的時(shí)間。更新時(shí)間：U=D+I（在位與異位）空間開(kāi)銷(xiāo)：索引結(jié)構(gòu)所需要的額外存儲(chǔ)空間；索引是用空間的代價(jià)來(lái)?yè)Q取系統(tǒng)性能的提高。索引實(shí)現(xiàn)的難度決定了該索引技術(shù)是否實(shí)用、能否推廣。12/13/202251§8.1基本概念索引技術(shù)的評(píng)價(jià)標(biāo)準(zhǔn)12/12/20224§8.2順序索引順序索引的作用能迅速地按順序或隨機(jī)地訪問(wèn)文件中的記錄順序索引的結(jié)構(gòu)在邏輯上按順序存儲(chǔ)搜索碼的值，并將搜索碼值與包含該搜索碼值的記錄關(guān)聯(lián)起來(lái)。順序索引的特征一個(gè)文件可以有多個(gè)索引，對(duì)應(yīng)于不同的搜索碼。根據(jù)索引結(jié)構(gòu)中搜索碼值的邏輯順序和數(shù)據(jù)文件中記錄的物理存儲(chǔ)順序之間的關(guān)系，順序索引分為主索引和輔助索引。12/13/202252§8.2順序索引順序索引的作用12/12/20225§8.2順序索引基本概念主索引與輔助索引如果數(shù)據(jù)文件中記錄按照某個(gè)搜索碼指定的順序物理存儲(chǔ)，則該搜索碼對(duì)應(yīng)的索引稱(chēng)為主索引或簇集索引；相反，搜索碼順序與數(shù)據(jù)文件中記錄的物理順序不同的那些索引稱(chēng)為輔助索引或非簇集索引；顯然，一個(gè)數(shù)據(jù)文件只能有一個(gè)主索引，但可以有多個(gè)輔助索引，為什么？堆文件與索引順序文件沒(méi)有主索引的數(shù)據(jù)文件就是堆文件；而擁有主索引的數(shù)據(jù)文件就是索引順序文件。12/13/202253§8.2順序索引基本概念12/12/20226§8.2順序索引索引順序文件數(shù)據(jù)文件中的記錄按照某個(gè)搜索碼值的順序物理存儲(chǔ)：12/13/202254§8.2順序索引索引順序文件12/12/20227§8.2順序索引順序索引的分類(lèi)按照索引結(jié)構(gòu)中搜索碼值與數(shù)據(jù)文件中搜索碼值的對(duì)應(yīng)關(guān)系，順序索引又分為：稠密索引稀疏索引稠密索引：對(duì)應(yīng)文件中搜索碼的每一個(gè)值都有一個(gè)索引記錄(或索引項(xiàng))，它包括：搜索碼值；指向具有該搜索碼值的第一個(gè)數(shù)據(jù)記錄的指針。12/13/202255§8.2順序索引順序索引的分類(lèi)12/12/20228§8.2順序索引順序索引的分類(lèi)稀疏索引：只為搜索碼的部分值建立索引項(xiàng)；與稠密索引一樣，每個(gè)索引項(xiàng)也包括搜索碼值和指向具有該搜索碼值的第一個(gè)數(shù)據(jù)記錄的指針。問(wèn)題：如何利用稀疏索引進(jìn)行查詢(xún)呢？12/13/202256§8.2順序索引順序索引的分類(lèi)問(wèn)題：如何利用稀疏索引進(jìn)行查詢(xún)SQLSERVER主索引的問(wèn)題？搜索碼鏈表的作用記錄的惟一標(biāo)識(shí)是F#:P#:S#索引中索引項(xiàng)的指針是？頁(yè)頭：96字節(jié)數(shù)據(jù)行，即記錄176行偏移數(shù)組：鏈表095Mianus(96)…Downtown(136).Brighton(176).Downtown(216).13621696

3210頁(yè)號(hào)：010§8.2順序索引各行順序號(hào)(槽號(hào))RID是01:010:01的記錄的搜索碼是Downtown12/13/202257SQLSERVER頁(yè)頭：數(shù)據(jù)行，即記錄176行偏移數(shù)組：鏈§8.2順序索引稠密索引和稀疏索引的比較利用稠密索引通?？梢员认∈杷饕斓囟ㄎ灰粋€(gè)記錄的位置；與稠密索引相比，稀疏索引占用空間小，插入和刪除時(shí)的維護(hù)開(kāi)銷(xiāo)也小。實(shí)踐中如何正確地建立稀疏索引？數(shù)據(jù)庫(kù)查詢(xún)的開(kāi)銷(xiāo)主要是由什么來(lái)決定的？在主存內(nèi)掃描整個(gè)塊的時(shí)間是可以忽略的；考慮為每個(gè)塊建一個(gè)索引項(xiàng)的稀疏索引，這樣的索引可以定位包含所要查找記錄的塊。12/13/202258§8.2順序索引稠密索引和稀疏索引的比較12/12/2022§8.2順序索引多級(jí)索引問(wèn)題的提出：即使采用稀疏索引，索引本身有時(shí)也會(huì)變得非常龐大而難于有效處理，例如：一個(gè)文件有100000條記錄；一個(gè)塊存儲(chǔ)10個(gè)記錄，每個(gè)塊有一個(gè)索引記錄；一個(gè)塊存儲(chǔ)100個(gè)索引記錄。索引過(guò)大在讀索引時(shí)就必須有一部分放在磁盤(pán)上，搜索一個(gè)索引項(xiàng)就必須多次讀磁盤(pán)塊：當(dāng)然在索引上可以用二分法來(lái)定位索引項(xiàng)，最壞需要讀log2(b)次塊，假設(shè)索引占據(jù)了b個(gè)塊。如果索引小到一次I/O就能夠放到主存里，搜索一個(gè)索引項(xiàng)的時(shí)間就很短，可以忽略不計(jì)。12/13/202259§8.2順序索引多級(jí)索引12/12/202212§8.2順序索引多級(jí)索引問(wèn)題的解決：像對(duì)待其他任何順序文件那樣對(duì)待索引結(jié)構(gòu)，即在主索引上再構(gòu)造一個(gè)稀疏索引，形成一個(gè)具有內(nèi)層索引和外層索引的多級(jí)索引結(jié)構(gòu)：主索引結(jié)構(gòu)本身就是一個(gè)順序文件12/13/202260§8.2順序索引多級(jí)索引主索引結(jié)構(gòu)本身就是一個(gè)順序文件12/§8.2順序索引索引的更新刪除數(shù)據(jù)記錄，稠密索引的變化情況：①刪除數(shù)據(jù)文件中的“鄧婉玲”記錄；②刪除數(shù)據(jù)文件中“王小麗”的s000005記錄；③刪除數(shù)據(jù)文件中“王小麗”的s000009記錄。12/13/202261§8.2順序索引索引的更新12/12/202214§8.2順序索引索引的更新刪除數(shù)據(jù)記錄，稀疏索引的變化情況：①刪除文件中搜索碼為“陳舒藝”的記錄；②刪除文件中搜索碼為“陳國(guó)國(guó)”的所有記錄；③刪除文件中搜索碼為“馮藹妍”記錄；④刪除文件中“王小麗”的s000005記錄；⑤刪除文件中“王小麗”的s000007記錄。12/13/202262§8.2順序索引索引的更新12/12/202215§8.2順序索引索引的更新插入數(shù)據(jù)記錄，索引的變化情況：若索引是稠密的，并且待插入記錄的搜索碼值不在索引中，就要把該搜索碼值插入到索引中；若索引是為每個(gè)塊保存一個(gè)索引項(xiàng)的稀疏索引：只要沒(méi)有新塊產(chǎn)生，索引就無(wú)需做任何改動(dòng)；在產(chǎn)生新塊的情況下，新塊中的第一個(gè)搜索碼值將被插入到索引中。多級(jí)索引：刪除和插入數(shù)據(jù)記錄時(shí)，它的更新同上面類(lèi)似：內(nèi)層索引的更新同上；內(nèi)層索引的變化，引起外層索引按上述算法更新。12/13/202263§8.2順序索引索引的更新12/12/202216§8.2順序索引輔助索引在文件中，記錄按主索引而不是輔助索引的搜索碼值順序物理存儲(chǔ)；具有同一個(gè)輔助搜索碼值的記錄可能分布在文件的各個(gè)地方，例如：12/13/202264§8.2順序索引輔助索引12/12/202217§8.2順序索引輔助索引其結(jié)構(gòu)與主索引的結(jié)構(gòu)是不同的：輔助索引必須包含指向每一記錄的指針；輔助索引的指針并不直接指向文件，而是每個(gè)指針指向一個(gè)包含文件指針的存儲(chǔ)桶；存儲(chǔ)桶中的每個(gè)指針才指向文件中的記錄。12/13/202265§8.2順序索引輔助索引12/12/202218§8.2順序索引輔助索引輔助索引的優(yōu)缺點(diǎn)：可以提高使用利用輔助搜索碼查詢(xún)記錄的速度；但輔助索引也大大增加了數(shù)據(jù)庫(kù)更新的開(kāi)銷(xiāo)。12/13/202266§8.2順序索引輔助索引12/12/202219§8.3B+樹(shù)索引文件索引順序文件的缺陷性能：索引順序文件組織最大的缺點(diǎn)在于隨著文件的增大，索引查找性能和順序掃描性能都會(huì)下降。文件重組：而且隨著頻繁的刪除和插入記錄，就會(huì)不斷有溢出塊出現(xiàn)，記錄的物理順序同主搜索碼順序的一致性就遭到破壞，這樣就不得不重組文件。解決方案呢？研究在插入和刪除操作很頻繁的情況下仍保持有效的索引結(jié)構(gòu)：B+樹(shù)索引就是其中的一種。12/13/202267§8.3B+樹(shù)索引文件索引順序文件的缺陷12/12/2022§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)總體結(jié)構(gòu)：是一個(gè)多級(jí)索引，但其結(jié)構(gòu)不同于多級(jí)順序索引采用平衡樹(shù)結(jié)構(gòu)：即每個(gè)葉結(jié)點(diǎn)到根的路徑長(zhǎng)度都相同。每個(gè)非葉結(jié)點(diǎn)有n/2到n個(gè)子女，n對(duì)特定樹(shù)是固定的；它的所有結(jié)點(diǎn)結(jié)構(gòu)都相同，最多包含n-1個(gè)搜索碼值K1、K2、…、Kn-1及n個(gè)指針P1、P2、…、Pn；每個(gè)結(jié)點(diǎn)中的搜索碼值按次序存放，即若i<j，那么一定有Ki<Kj。12/13/202268§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)12/12/202221§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)葉結(jié)點(diǎn)：指針Pi(i=1,2,…,n-1)指向具有搜索碼值Ki的一個(gè)數(shù)據(jù)記錄或一個(gè)指針桶，桶中的每個(gè)指針指向具有搜索碼值Ki的一個(gè)數(shù)據(jù)記錄。指針桶只在記錄不按搜索碼順序物理存儲(chǔ)時(shí)才使用指針Pn具有特殊的作用。每個(gè)葉結(jié)點(diǎn)最多可有n-1個(gè)搜索碼值，最少也要有(n-1)/2個(gè)搜索碼值；各個(gè)葉結(jié)點(diǎn)的搜索碼值的范圍互不相交；要使B+樹(shù)索引成為稠密索引，文件中各搜索碼值就都必須在某個(gè)葉結(jié)點(diǎn)中出現(xiàn)且只能出現(xiàn)一次；12/13/202269§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)12/12/202222B+樹(shù)索引結(jié)構(gòu)葉結(jié)點(diǎn)：各葉結(jié)點(diǎn)按照所含的搜索碼值有一個(gè)線性順序，利用指針Pn將葉結(jié)點(diǎn)按搜索碼順序鏈接在一起；這種排序能高效地對(duì)文件進(jìn)行順序處理，而B(niǎo)+樹(shù)索引的其他結(jié)構(gòu)能高效地對(duì)文件進(jìn)行隨機(jī)處理?！?.3B+樹(shù)索引文件12/13/202270B+樹(shù)索引結(jié)構(gòu)§8.3B+樹(shù)索引文件12/12/202223B+樹(shù)索引結(jié)構(gòu)非葉結(jié)點(diǎn)：B+樹(shù)索引的非葉結(jié)點(diǎn)形成葉結(jié)點(diǎn)上的一個(gè)多級(jí)稀疏索引；非葉結(jié)點(diǎn)的結(jié)構(gòu)和葉結(jié)點(diǎn)的結(jié)構(gòu)相同，即含有能夠存儲(chǔ)n-1個(gè)搜索碼值和n個(gè)指針的存儲(chǔ)單元。只不過(guò)非葉結(jié)點(diǎn)中的所有指針都指向樹(shù)中的結(jié)點(diǎn)；如果一個(gè)非葉結(jié)點(diǎn)有m個(gè)指針，則n/2≤m≤n。若m<n，則非葉結(jié)點(diǎn)中指針Pm之后的所有空閑空間作為預(yù)留空間，與葉結(jié)點(diǎn)的區(qū)別在于結(jié)點(diǎn)的最后一個(gè)指針Pm和Pn的位置與指向；§8.3B+樹(shù)索引文件12/13/202271B+樹(shù)索引結(jié)構(gòu)§8.3B+樹(shù)索引文件12/12/202224§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)非葉結(jié)點(diǎn)：在含有m個(gè)指針的非葉結(jié)點(diǎn)中，Pi(i=2,…,m-1)指向一棵子樹(shù)，該子樹(shù)的所有結(jié)點(diǎn)的搜索碼值大于等于Ki-1而小于Ki；指針Pm指向子樹(shù)中所含搜索碼值大于等于Km-1的那一部分；而指針P1指向子樹(shù)中所含搜索碼值小于K1的那一部分。12/13/202272§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)12/12/202225§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)根結(jié)點(diǎn)：根結(jié)點(diǎn)的結(jié)構(gòu)也與葉結(jié)點(diǎn)的結(jié)構(gòu)相同；根結(jié)點(diǎn)包含的指針數(shù)可能小于n/2，除非整棵樹(shù)只有一個(gè)結(jié)點(diǎn)，否則它至少包含兩個(gè)指針。12/13/202273§8.3B+樹(shù)索引文件B+樹(shù)索引結(jié)構(gòu)12/12/202226§8.3B+樹(shù)索引文件B+樹(shù)索引缺點(diǎn)B+樹(shù)的“平衡”(Balance)特征保證了B+樹(shù)索引具有良好的查找、插入和修改性能，但B+樹(shù)索引也有以下缺陷：B+樹(shù)索引結(jié)構(gòu)會(huì)增加文件插入和刪除處理的空間開(kāi)銷(xiāo)，以空間代價(jià)換取性能上的優(yōu)勢(shì)；B+樹(shù)索引結(jié)構(gòu)在極端情況下，結(jié)點(diǎn)可以是半空的(n/2到n)，這雖然造成了空間浪費(fèi)，但缺保證了性能。B+樹(shù)索引技術(shù)已經(jīng)被廣泛地應(yīng)用到商業(yè)數(shù)據(jù)庫(kù)管理系統(tǒng)中。12/13/202274§8.3B+樹(shù)索引文件B+樹(shù)索引缺點(diǎn)12/12/202227§8.3B+樹(shù)索引文件B+樹(shù)上的查詢(xún)?nèi)绾卫肂+樹(shù)索引進(jìn)行查詢(xún)呢？假設(shè)要找出搜索碼值為K的所有記錄：首先檢查根結(jié)點(diǎn)，找到大于K的最小搜索碼值，假設(shè)是Ki，那么沿著指針Pi走到另一個(gè)結(jié)點(diǎn)；如果K<K1，則沿著指針P1走至另一個(gè)結(jié)點(diǎn)；如果K≥Km-1(m是該結(jié)點(diǎn)的指針數(shù))，則沿著指針Pm走至另一個(gè)結(jié)點(diǎn)；對(duì)新到達(dá)的結(jié)點(diǎn)，重復(fù)以上步驟，最終到達(dá)一個(gè)葉結(jié)點(diǎn)。12/13/202275§8.3B+樹(shù)索引文件B+樹(shù)上的查詢(xún)12/12/202228§8.3B+樹(shù)索引文件B+樹(shù)上的查詢(xún)舉例：利用student關(guān)系上的B+樹(shù)索引，給出在該關(guān)系中查找student_name為“鄧婉玲”的所有記錄的過(guò)程：12/13/202276§8.3B+樹(shù)索引文件B+樹(shù)上的查詢(xún)12/12/202229§8.3B+樹(shù)索引文件B+樹(shù)的更新很煩瑣，《數(shù)據(jù)結(jié)構(gòu)》課程講的內(nèi)容。B+樹(shù)文件組織B+樹(shù)索引通過(guò)在葉結(jié)點(diǎn)來(lái)組織包含真實(shí)記錄的物理塊來(lái)解決索引順序文件組織隨著文件的增大而性能下降的缺點(diǎn)：在B+樹(shù)文件組織中，B+樹(shù)結(jié)構(gòu)不僅用做索引，同時(shí)也是文件中記錄的組織者。樹(shù)葉結(jié)點(diǎn)中存儲(chǔ)的是記錄而不是指向記錄的指針。12/13/202277§8.3B+樹(shù)索引文件B+樹(shù)的更新12/12/202230基本概念在前面介紹的索引類(lèi)型中，必須訪問(wèn)該索引結(jié)構(gòu)，才能在文件中定位記錄。而基于散列(Hash)的文件組織能夠避免訪問(wèn)索引結(jié)構(gòu)；在散列文件組織中，用存儲(chǔ)桶來(lái)表示能存儲(chǔ)一條或多條記錄的一個(gè)存儲(chǔ)單位。通過(guò)計(jì)算搜索碼上的一個(gè)函數(shù)，就可以確定包含該搜索碼值的記錄應(yīng)該存儲(chǔ)在哪個(gè)桶中；令K表示所有搜索碼值的集合，令B表示所有桶地址的集合，散列函數(shù)h就是一個(gè)從K到B的函數(shù)：h(K)B或B=h(K)?！?.4散列文件組織12/13/202278基本概念§8.4散列文件組織12/12/202231散列文件的操作插入：為了插入一個(gè)搜索碼為Ki的記錄，通過(guò)計(jì)算h(Ki)獲得存放該記錄的桶地址。于是就把這條記錄存入桶中或是相應(yīng)的溢出桶中；刪除：如果待刪除記錄的搜索碼值是Ki，則計(jì)算h(Ki)，然后在相應(yīng)的桶中搜尋此記錄并刪除它；基于搜索碼值Ki的查找：首先計(jì)算h(Ki)，然后在計(jì)算出地址的桶中搜索所有的記錄。因?yàn)椴煌乃阉鞔a值對(duì)應(yīng)相同的桶地址正是散列文件組織的最大特點(diǎn)。§8.4散列文件組織12/13/202279散列文件的操作§8.4散列文件組織12/12/202232散列函數(shù)如果散列函數(shù)設(shè)計(jì)的不好，就有可能把所有的搜索碼值都映射到同一個(gè)存儲(chǔ)桶中，這時(shí)散列就失去了意義。因此，對(duì)散列函數(shù)的基本要求是：分布是均勻的：即每個(gè)存儲(chǔ)桶從所有可能的搜索碼值集合中分配到的值的個(gè)數(shù)差不多相同，例如將大寫(xiě)英文字母分配到5個(gè)存儲(chǔ)桶中；分布是隨機(jī)的：不管搜索碼值的實(shí)際情況是怎樣的，每個(gè)存儲(chǔ)桶應(yīng)分配到的搜索碼值的個(gè)數(shù)也差不多相同。例如，假設(shè)實(shí)際的搜索碼值是A、B、C、D、E五個(gè)字母。§8.4散列文件組織12/13/202280散列函數(shù)§8.4散列文件組織12/12/202233散列函數(shù)舉例：假設(shè)將26個(gè)大寫(xiě)英文字母分布到5個(gè)存儲(chǔ)桶中(地址從0到4)，那么散列函數(shù)h該如何設(shè)計(jì)呢？假設(shè)用code(A)表示A所對(duì)應(yīng)的編號(hào)0，……；散列函數(shù)h=code(SearchKey)mod5。§8.4散列文件組織12/13/202281散列函數(shù)§8.4散列文件組織12/12/202234問(wèn)題的提出散列不僅可以用于數(shù)據(jù)文件中記錄的組織，還可以用于索引中索引項(xiàng)的組織。散列索引：將索引項(xiàng)中的搜索碼及相應(yīng)的指針按散列文件的形式進(jìn)行組織。散列索引的構(gòu)造首先將散列函數(shù)作用于索引項(xiàng)中的搜索碼以確定對(duì)應(yīng)的存儲(chǔ)桶；然后將此搜索碼及相應(yīng)的指針存入此存儲(chǔ)桶中，而指針指向數(shù)據(jù)文件中的記錄。§8.5散列索引12/13/202282問(wèn)題的提出§8.5散列索引12/12/202235舉例：為關(guān)系student上的student_number搜索碼建立一個(gè)輔助的散列索引?！?.5散列索引散列函數(shù)h是學(xué)號(hào)各位數(shù)字之和后模3該散列索引共有3個(gè)桶，每個(gè)桶的大小為312/13/202283舉例：為關(guān)系student上的student_number搜小結(jié)術(shù)語(yǔ)“散列文件”是指用來(lái)組織和存儲(chǔ)文件中數(shù)據(jù)記錄的散列文件結(jié)構(gòu)。而散列索引是指將文件上的輔助索引的索引項(xiàng)按照散列文件的結(jié)構(gòu)進(jìn)行組織，不要將二者混淆；如果數(shù)據(jù)文件自身是按散列組織的，就認(rèn)為該散列文件已經(jīng)有了一個(gè)“主索引”，一般不必在其上另外創(chuàng)建獨(dú)立的索引結(jié)構(gòu)；散列索引只用來(lái)組織數(shù)據(jù)文件上的輔助索引數(shù)據(jù)文件上的主索引結(jié)構(gòu)不應(yīng)該是散列文件索引本身的文件結(jié)構(gòu)有哪些？§8.5散列索引12/13/202284小結(jié)§8.5散列索引12/12/202237用索引還是散列？索引和散列都為訪問(wèn)數(shù)據(jù)提供了存取路徑：索引需要通過(guò)值的比較，才能確定數(shù)據(jù)的位置；散列不通過(guò)值的比較，而通過(guò)值的含義來(lái)確定數(shù)據(jù)的位置的。用索引還是散列實(shí)際當(dāng)中要考慮以下問(wèn)題：索引或散列的周期性重組代價(jià)如何？在文件中插入和刪除記錄的頻率如何？為了優(yōu)化平均訪問(wèn)時(shí)間而導(dǎo)致最壞情況下的訪問(wèn)時(shí)間的做法是否可取？能夠有效支持的查詢(xún)類(lèi)型是哪些？§8.6順序索引和散列的比較12/13/202285用索引還是散列？§8.6順序索引和散列的比較12/12/20散列支持的查詢(xún)類(lèi)型等值查詢(xún)，或者叫點(diǎn)查詢(xún)范圍檢索散列與索引比較舉例之一selectA1,A2,…,An