數(shù)據(jù)庫原理與應(yīng)用

數(shù)據(jù)庫原理與應(yīng)用6.***第1頁，共55頁，2023年，2月20日，星期六第六章數(shù)據(jù)存儲(chǔ)與查詢優(yōu)化物理存儲(chǔ)索引結(jié)構(gòu)查詢處理過程代數(shù)優(yōu)化物理優(yōu)化第2頁，共55頁，2023年，2月20日，星期六物理存儲(chǔ)介質(zhì)現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)中存在著多種存儲(chǔ)介質(zhì)，按照容量、訪問速度等技術(shù)指標(biāo)又可分為三級(jí)，組成一個(gè)典型的金字塔結(jié)構(gòu)第3頁，共55頁，2023年，2月20日，星期六揮發(fā)性和持久性介質(zhì)內(nèi)存等一級(jí)存儲(chǔ)介質(zhì)只在系統(tǒng)運(yùn)行時(shí)保存數(shù)據(jù)，一旦斷電，數(shù)據(jù)全部丟失，稱為揮發(fā)性介質(zhì)磁盤、磁帶等二、三級(jí)存儲(chǔ)介質(zhì)則在斷電之后仍能保持?jǐn)?shù)據(jù)的有效性，稱為持久性介質(zhì)數(shù)據(jù)庫中的數(shù)據(jù)必須長時(shí)間的保存，即使系統(tǒng)關(guān)閉也不應(yīng)該影響數(shù)據(jù)庫中數(shù)據(jù)的有效性。因此，數(shù)據(jù)庫中的數(shù)據(jù)必須存儲(chǔ)在二、三級(jí)持久性介質(zhì)中第4頁，共55頁，2023年，2月20日，星期六磁盤磁盤又稱為硬盤，磁盤屬于第二級(jí)存儲(chǔ)，為持久性介質(zhì)，是數(shù)據(jù)庫的典型存儲(chǔ)介質(zhì)一個(gè)磁盤中包含一個(gè)或多個(gè)盤片，這些盤片由金屬或玻璃等剛性介質(zhì)制成，表面涂有磁性介質(zhì)用來記錄數(shù)據(jù)一個(gè)盤片有上下兩個(gè)盤面，可以都用來記錄數(shù)據(jù)，也可以只用一個(gè)面來記錄數(shù)據(jù)對(duì)每一個(gè)用來記錄數(shù)據(jù)的盤面都有一個(gè)磁盤臂，其末端的讀寫頭通過感應(yīng)或改變盤片的局部磁性來讀取或?qū)懭氪疟P中的數(shù)據(jù)第5頁，共55頁，2023年，2月20日，星期六磁盤（續(xù)）一個(gè)盤面被劃分為多個(gè)間距很小的同心圓，這些同心圓被稱為磁道(track)，不同盤面上有相同直徑的磁道構(gòu)成一個(gè)柱面(cylinder)磁道又可以進(jìn)一步分為多個(gè)扇區(qū)(sector)，現(xiàn)有的磁盤中一個(gè)扇區(qū)的典型容量是512字節(jié)在工作狀態(tài)時(shí)，磁盤軸帶動(dòng)盤片以恒定的速度旋轉(zhuǎn)磁盤與操作系統(tǒng)之間的交互是通過磁盤控制器完成的第6頁，共55頁，2023年，2月20日，星期六磁盤結(jié)構(gòu)第7頁，共55頁，2023年，2月20日，星期六磁盤I/O的性能讀寫磁盤數(shù)據(jù)時(shí)，磁盤內(nèi)部需要進(jìn)行以下的一系列動(dòng)作移動(dòng)磁盤臂，直到讀寫頭位于數(shù)據(jù)所在磁道的正上方通過盤片旋轉(zhuǎn)，使得讀寫頭位于所讀寫數(shù)據(jù)的正上方讀寫頭讀取或?qū)懭霐?shù)據(jù)磁盤進(jìn)行一次數(shù)據(jù)讀寫操作的時(shí)間由三部分組成第一部分是移動(dòng)磁盤臂所用的時(shí)間，稱為尋道時(shí)間，典型值為幾毫秒第二部分是旋轉(zhuǎn)盤片所用的時(shí)間，稱為旋轉(zhuǎn)時(shí)間，典型值為5-10毫秒第三部分是讀寫數(shù)據(jù)所用的時(shí)間，稱為傳輸時(shí)間，典型值為幾到幾十MB每秒第8頁，共55頁，2023年，2月20日，星期六磁盤讀寫的優(yōu)化磁盤臂調(diào)度的目的是通過規(guī)劃多個(gè)數(shù)據(jù)讀寫請(qǐng)求的服務(wù)順序來減少讀寫頭的總移動(dòng)距離，從而縮短讀寫磁盤的平均尋道時(shí)間。一種常用的磁盤臂調(diào)度算法是電梯算法無論讀寫的數(shù)據(jù)量多大，由尋道時(shí)間和旋轉(zhuǎn)時(shí)間帶來的額外消耗都是一定的，因此讀寫少量數(shù)據(jù)時(shí)的效率就比讀寫大量數(shù)據(jù)時(shí)的效率低得多基于計(jì)算機(jī)系統(tǒng)中的局部性原理，在磁盤與操作系統(tǒng)之間的數(shù)據(jù)交互過程中廣泛使用數(shù)據(jù)預(yù)取技術(shù)，即在讀取指定數(shù)據(jù)的同時(shí)也預(yù)先讀取與其相鄰的一定范圍內(nèi)的數(shù)據(jù)典型的數(shù)據(jù)預(yù)取技術(shù)是數(shù)據(jù)的按塊傳輸，塊是一個(gè)邏輯單位，即一個(gè)磁盤從邏輯上被劃分多個(gè)連續(xù)的塊。目前典型的塊大小在1KB-8KB之間第9頁，共55頁，2023年，2月20日，星期六緩沖管理在系統(tǒng)內(nèi)存中開辟一塊專用空間，稱為緩沖區(qū)，用來緩存經(jīng)常需要訪問數(shù)據(jù)DBMS中用來對(duì)緩沖區(qū)進(jìn)行管理的模塊就稱為緩沖區(qū)管理器當(dāng)DBMS的其它模塊需要讀取數(shù)據(jù)時(shí)，它們向緩沖區(qū)管理器發(fā)出請(qǐng)求緩沖區(qū)管理器首先查看需要讀取的數(shù)據(jù)是否在緩沖區(qū)中，如果在，則緩沖區(qū)管理器直接返回緩沖區(qū)中的數(shù)據(jù)，從而免除了進(jìn)行磁盤I/O的代價(jià)如果在緩沖區(qū)中找不到指定數(shù)據(jù)時(shí)，則緩沖區(qū)管理器先從磁盤將數(shù)據(jù)讀入緩沖區(qū)，然后返回給請(qǐng)求者第10頁，共55頁，2023年，2月20日，星期六緩沖區(qū)管理器緩沖區(qū)中的內(nèi)容被劃分為多個(gè)塊，塊大小與磁盤塊一致。為了對(duì)緩沖區(qū)進(jìn)行有效管理，需要為每個(gè)緩沖塊記錄以下內(nèi)容：空閑位臟位，在讀入之后被修改過的緩沖塊稱為臟塊pin值：pin值有兩個(gè)功能，一是防止緩沖區(qū)管理器替換出正在處理的塊，二是可以指定某些塊常駐內(nèi)存。緩沖區(qū)在選擇被替換的塊時(shí)，如果發(fā)現(xiàn)某緩沖塊的pin值不為0，則不會(huì)將它替換出去。提供強(qiáng)制寫出臟的緩沖塊的功能，這是為了保證數(shù)據(jù)的持久化存儲(chǔ)。一種典型情況是系統(tǒng)關(guān)閉時(shí)需要強(qiáng)制寫出所有臟的緩沖塊，另外為了數(shù)據(jù)庫恢復(fù)的需要也要強(qiáng)制寫出臟的緩沖塊第11頁，共55頁，2023年，2月20日，星期六緩沖區(qū)替換策略緩沖區(qū)通常不足以容納數(shù)據(jù)庫中的所有數(shù)據(jù)，在需要讀入新的數(shù)據(jù)時(shí)，可能出現(xiàn)緩沖區(qū)已滿的情況，這時(shí)緩沖區(qū)管理器就要選擇一個(gè)緩沖塊替換出去如何選擇被替換的緩沖塊將影響到數(shù)據(jù)庫運(yùn)行過程中進(jìn)行磁盤I/O的頻率，一個(gè)好的緩沖區(qū)替換策略應(yīng)該能夠減少磁盤I/O，提高數(shù)據(jù)庫的性能LRU（LeastRecentlyUsed）替換策略的基本思想是：系統(tǒng)未來對(duì)數(shù)據(jù)的訪問情況可由系統(tǒng)過去的訪問情況預(yù)期，即如果一個(gè)數(shù)據(jù)塊在過去很少被訪問，則將來也不太可能被訪問，因此在緩沖區(qū)滿時(shí)可考慮將其替換出去，反之，如果一個(gè)數(shù)據(jù)塊在過去經(jīng)常被訪問，則將來也很有可能會(huì)被再次訪問，因此不應(yīng)將其替換出去第12頁，共55頁，2023年，2月20日，星期六LRU替換策略設(shè)有一個(gè)4塊的緩沖區(qū)，初始為空，以后依次訪問了塊1,4,8,1,5,2,3,2,4，則根據(jù)LRU替換策略緩沖區(qū)的內(nèi)容如下圖所示，其間共發(fā)生了三次緩沖區(qū)替換第13頁，共55頁，2023年，2月20日，星期六記錄的存儲(chǔ)數(shù)據(jù)庫的數(shù)據(jù)通常按記錄的形式加以組織，記錄又由一到多個(gè)字段組成有些類型，如整型、浮點(diǎn)型、定長字符串和日期類型等，無論具體的值是什么，占用的存儲(chǔ)空間都是一樣的，稱為定長類型另一些類型，如變長字符串和文本等，占用的存儲(chǔ)空間由實(shí)際的值決定，稱為變長類型如果一條記錄中只包含定長類型的字段，則該記錄稱為定長記錄，否則稱為變長記錄第14頁，共55頁，2023年，2月20日，星期六定長記錄定長記錄中所有的字段都是定長的，只需將所有字段按既定的順序連續(xù)存放，所有字段的地址相對(duì)于記錄首地址的偏移都可以計(jì)算得到第15頁，共55頁，2023年，2月20日，星期六變長記錄變長記錄中每個(gè)字段相對(duì)于記錄首地址的偏移是不固定的，因此除了記錄所有字段的值之外，在記錄中還需要包含一些附加信息，以使得在訪問時(shí)可以計(jì)算出記錄中各個(gè)字段的偏移量。變長記錄的內(nèi)部格式通常有兩種，一種是用特殊的分隔符將記錄中的各字段隔開，這種方法有兩個(gè)缺點(diǎn)不能保證分隔符永遠(yuǎn)不會(huì)在字段的值中出現(xiàn)即使只訪問記錄中的某個(gè)字段，也必須從記錄首部開始搜索，否則無法確定該字段的位置第16頁，共55頁，2023年，2月20日，星期六變長記錄（續(xù)）另一種方法是在記錄首部存儲(chǔ)各個(gè)字段的偏移量，這種方法解決了特殊字符分隔法的缺點(diǎn)，因此在實(shí)際的系統(tǒng)中更為常用第17頁，共55頁，2023年，2月20日，星期六塊格式塊是內(nèi)外存交互的單位，記錄必須存儲(chǔ)在塊中。一般來說，記錄的長度小于塊大小，因此在一個(gè)塊中可以存放多條記錄，每個(gè)塊中可以存放多條記錄，其中f稱為該數(shù)據(jù)文件的塊因子。如果記錄跨塊存儲(chǔ)，在訪問該記錄時(shí)就會(huì)導(dǎo)致多次磁盤I/O操作。第18頁，共55頁，2023年，2月20日，星期六數(shù)據(jù)文件的重整在DBMS運(yùn)行過程中，每刪除一條記錄，就在數(shù)據(jù)文件中產(chǎn)生一塊小的空閑空間，這些小的空閑空間難以被有效利用，隨著DBMS的不斷運(yùn)行，就會(huì)使數(shù)據(jù)文件中產(chǎn)生越來越多的“碎片”，從而導(dǎo)致DBMS性能的降低。為解決這一問題，需要定期對(duì)數(shù)據(jù)文件進(jìn)行重整數(shù)據(jù)文件的重整可以在文件范圍進(jìn)行，能夠完全消除數(shù)據(jù)文件中的“碎片”。但文件范圍的重整會(huì)導(dǎo)致記錄在文件范圍內(nèi)移動(dòng)，使得整個(gè)數(shù)據(jù)文件在重整過程中無法使用，也必然會(huì)影響到建立在該數(shù)據(jù)文件上的索引結(jié)構(gòu)更為常用的重整方法是塊內(nèi)重整，塊內(nèi)重整按序處理數(shù)據(jù)文件中的每個(gè)塊，將該塊內(nèi)的記錄集中存儲(chǔ)到塊尾第19頁，共55頁，2023年，2月20日，星期六超長記錄和記錄的跨塊存儲(chǔ)為了利用空間，可以考慮允許記錄跨塊存儲(chǔ)，即當(dāng)塊中存不下一條完整的記錄時(shí)，可以把記錄的前一部分存在該塊中，而把余下的部分存在后續(xù)的塊中除了為了防止空間浪費(fèi)而進(jìn)行跨塊存儲(chǔ)外，當(dāng)記錄的長度超過塊的大小時(shí)，也必須進(jìn)行跨塊存儲(chǔ)第20頁，共55頁，2023年，2月20日，星期六文件組織方式堆文件：記錄間沒有次序關(guān)系，新加入的記錄可以存儲(chǔ)在文件中任何有空間的地方。順序文件：記錄按某些字段的值進(jìn)行排序。哈希文件：對(duì)記錄的某些字段進(jìn)行哈希運(yùn)算，運(yùn)算的結(jié)果決定記錄存儲(chǔ)在文件中的哪一塊。聚集文件：將同種類或相關(guān)的來自于不同關(guān)系的記錄存放在同一塊中，以減少同時(shí)獲取這些記錄的I/O操作第21頁，共55頁，2023年，2月20日，星期六順序文件第22頁，共55頁，2023年，2月20日，星期六順序文件的特點(diǎn)優(yōu)點(diǎn)按搜索鍵的值順序讀取記錄的效率很高如果選擇條件基于搜索鍵的值，就可以在磁盤上進(jìn)行二分查找但順序文件在處理記錄的插入上卻有較大的困難，當(dāng)插入一條記錄時(shí)，首先要根據(jù)待插入記錄的搜索鍵值找到記錄的插入點(diǎn)，然后要將插入點(diǎn)之后的所有記錄向后移動(dòng)，以便為待插入記錄留出空間。這樣平均插入一條記錄就要移動(dòng)文件中一半的記錄。為改善順序文件中記錄插入操作的性能，可以在每個(gè)塊中都為新記錄預(yù)留出一定的存儲(chǔ)空間第23頁，共55頁，2023年，2月20日，星期六聚集文件但對(duì)于大型或超大型的數(shù)據(jù)庫，性能是最重要的因素。為提高數(shù)據(jù)庫的性能，大型數(shù)據(jù)庫中通常采用更復(fù)雜的文件組織方式，允許多個(gè)表中的相關(guān)記錄存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，這種文件組織方式就稱為聚集文件但采用聚集文件也會(huì)使某些查詢的執(zhí)行效率降低，因此，是否采用聚集文件及如何進(jìn)行聚集應(yīng)該由在數(shù)據(jù)庫運(yùn)行過程中各類查詢的頻率決定第24頁，共55頁，2023年，2月20日，星期六索引從理論上來說，只要記錄被正確地存儲(chǔ)于數(shù)據(jù)文件中，DBMS就可以正常工作，但實(shí)際上，單純依賴數(shù)據(jù)文件處理查詢有時(shí)候效率是非常低的DBMS中索引的工作方式與書后面關(guān)鍵詞索引的工作方式是相似的DBMS索引中與關(guān)鍵詞相對(duì)應(yīng)的概念稱為索引鍵(或索引字段)，由一個(gè)或多個(gè)字段組成，DBMS可以借助于索引找到包含指定鍵值的記錄的位置B+樹索引和哈希索引第25頁，共55頁，2023年，2月20日，星期六B+樹的結(jié)構(gòu)B+樹屬于多級(jí)多叉平衡樹，從根到每個(gè)葉節(jié)點(diǎn)的路徑長度相等B+樹中每個(gè)節(jié)點(diǎn)大小相同，且擁有相似的內(nèi)部結(jié)構(gòu)對(duì)于n階的B+樹，每個(gè)B+樹節(jié)點(diǎn)最多可以包含n-1個(gè)排列有序的索引鍵值和n個(gè)指針。對(duì)一個(gè)節(jié)點(diǎn)中的鍵值編號(hào)為K1,K2,…,Kn-1，節(jié)點(diǎn)的鍵值遞增排列，即K1<K2<…<Kn-1。指針編號(hào)為P1,P2,…,Pn，一個(gè)指針、索引鍵值對(duì)<Pi,Ki>又稱為一個(gè)入口項(xiàng)第26頁，共55頁，2023年，2月20日，星期六B+樹的結(jié)構(gòu)（續(xù)）B+樹節(jié)點(diǎn)的大小與緩沖塊大小相同，因此，具有不同索引鍵的B+樹的階數(shù)是不同的，可由以下公式計(jì)算得到階數(shù)=(緩沖塊大小+索引鍵大小)/(索引鍵大小+指針大小)在B+樹中存在兩種節(jié)點(diǎn)：葉節(jié)點(diǎn)和非葉節(jié)點(diǎn)，不同類型的節(jié)點(diǎn)具有不同的性質(zhì)第27頁，共55頁，2023年，2月20日，星期六葉節(jié)點(diǎn)對(duì)于i=1,2,…,n-1，指針Pi指向包含鍵值Ki的記錄的位置。如果索引鍵是主鍵，則每個(gè)索引鍵值只對(duì)應(yīng)一條記錄，指針Pi指向的是含有索引鍵Ki的記錄。如是索引鍵不是主鍵，則可能有多條記錄具有相同的索引鍵值，指針Pi指向的是一個(gè)包含所有具有索引鍵值Ki記錄位置的指針桶。葉節(jié)點(diǎn)的最后一個(gè)指針Pn指向該它的右兄弟節(jié)點(diǎn)，如果該節(jié)點(diǎn)已經(jīng)是最右的葉節(jié)點(diǎn)，則Pn為NULLB+樹的每個(gè)葉節(jié)點(diǎn)中最少需要包含個(gè)索引鍵值所有葉節(jié)點(diǎn)中的索引鍵值也遞增排列，且不同葉節(jié)點(diǎn)中的索引鍵值間不重合，即若Li和Lj為葉節(jié)點(diǎn)，且i<j，則Li中的所有索引鍵值都小于Lj中的所有索引鍵值。葉節(jié)點(diǎn)構(gòu)成B+樹中所有鍵值的一個(gè)劃分第28頁，共55頁，2023年，2月20日，星期六非葉節(jié)點(diǎn)所有的指針指向它的子節(jié)點(diǎn)。除根節(jié)點(diǎn)之外的所有非葉節(jié)點(diǎn)最少需要包含個(gè)指針，根節(jié)點(diǎn)最少可以包含2個(gè)指針(除非B+樹中只有一個(gè)節(jié)點(diǎn)，此時(shí)根節(jié)點(diǎn)是葉節(jié)點(diǎn))。設(shè)一個(gè)非葉節(jié)點(diǎn)中包含m個(gè)指針(此時(shí)m稱為該節(jié)點(diǎn)的扇出度)，則對(duì)于i=2,3,…,m-1，指針Pi指向的子樹中所有索引鍵值都大于或等于Ki-1且小于Ki，指針Pm指向的子樹中所有索引鍵值都大于或等于Km-1，指針P1指向的子樹中所有索引鍵值都小于K1第29頁，共55頁，2023年，2月20日，星期六一個(gè)3階的B+樹第30頁，共55頁，2023年，2月20日，星期六B+樹檢索檢索過程從B+樹的根節(jié)點(diǎn)開始，系統(tǒng)首先找出根節(jié)點(diǎn)中比V大的最小索引鍵值，設(shè)為Ki，然后系統(tǒng)下溯到指針Pi指向的子節(jié)點(diǎn)，若V比根節(jié)點(diǎn)中所有索引鍵都大，則下溯到Pm指向的子節(jié)點(diǎn)。系統(tǒng)循環(huán)執(zhí)行上述過程，直到到達(dá)葉節(jié)點(diǎn)，在該葉節(jié)點(diǎn)上，如果存在與V相等的Ki，則Pi指向所需的記錄或指針桶，本次檢索操作成功；如果不存在與V相等的索引鍵，則檢索失敗，返回空。第31頁，共55頁，2023年，2月20日，星期六B+樹檢索的效率B+樹的每次檢索操作訪問的節(jié)點(diǎn)構(gòu)成了從根節(jié)點(diǎn)到某個(gè)葉節(jié)點(diǎn)的路徑，由于B+樹是平衡樹，因此每次檢索操作訪問的節(jié)點(diǎn)數(shù)相同，都為B+樹的樹高設(shè)B+樹中的索引鍵值為K，則B+樹的高不會(huì)超過。在實(shí)際應(yīng)用中，n的值通常在幾十到幾百之間，因此B+樹的高相對(duì)于索引鍵值數(shù)來說是很小的。設(shè)n為100，則在B+樹中擁有100萬個(gè)索引鍵值時(shí)，進(jìn)行一次B+樹檢索操作只需訪問4個(gè)節(jié)點(diǎn)，由此可見，通過B+樹進(jìn)行數(shù)據(jù)檢索的效率是相當(dāng)高的第32頁，共55頁，2023年，2月20日，星期六B+樹更新索引結(jié)構(gòu)必須與對(duì)應(yīng)的基本表中的數(shù)據(jù)相一致，當(dāng)用戶插入、刪除基本表中的記錄或更新記錄中索引字段的值時(shí)，必須同時(shí)更新相應(yīng)的索引結(jié)構(gòu)B+樹索引支持兩種基本的更新操作：插入和刪除一個(gè)入口項(xiàng)第33頁，共55頁，2023年，2月20日，星期六插入操作首先用B+樹檢索算法找到用于插入該鍵值的葉節(jié)點(diǎn)，若該葉節(jié)點(diǎn)中已經(jīng)包含待插入的鍵值，則將記錄的位置添加到相應(yīng)的指針桶中；否則，將鍵值插入到該葉節(jié)點(diǎn)的合適位置，使得在插入后節(jié)點(diǎn)中的鍵值仍保持遞增排列，當(dāng)索引為unique時(shí)，同時(shí)插入記錄的位置，當(dāng)索引不為unique時(shí)，創(chuàng)建一個(gè)只包含新插入記錄位置的指針桶，同時(shí)插入指針桶的位置B+樹插入操作的復(fù)雜性在于在特定情況下必須進(jìn)行節(jié)點(diǎn)分裂操作。當(dāng)用于插入新索引鍵值的葉節(jié)點(diǎn)原已滿時(shí)，葉節(jié)點(diǎn)分裂為兩個(gè)節(jié)點(diǎn)，原節(jié)點(diǎn)中的n-1個(gè)入口項(xiàng)加上新插入的入口項(xiàng)共n個(gè)入口項(xiàng)中索引鍵值最小的個(gè)入口項(xiàng)保留在原節(jié)點(diǎn)中，其余的移到新創(chuàng)建的節(jié)點(diǎn)中，新節(jié)點(diǎn)中最小的索引鍵值和新節(jié)點(diǎn)的位置構(gòu)成的入口項(xiàng)繼續(xù)插入到原節(jié)點(diǎn)的父節(jié)點(diǎn)中第34頁，共55頁，2023年，2月20日，星期六在前圖所示B+樹中插入30和50第35頁，共55頁，2023年，2月20日，星期六再插入25后的B+樹第36頁，共55頁，2023年，2月20日，星期六刪除操作根據(jù)檢索算法找到該入口項(xiàng)所處的葉節(jié)點(diǎn)，然后將其從該葉節(jié)點(diǎn)中刪除。如果在刪除后使得該葉節(jié)點(diǎn)中余下的入口項(xiàng)不足個(gè)，即產(chǎn)生一次向下溢出(underflow)，則需要盡量找到一個(gè)兄弟節(jié)點(diǎn)以進(jìn)行節(jié)點(diǎn)合并或入口項(xiàng)重新分配，通常是向該節(jié)點(diǎn)“借用”一個(gè)入口項(xiàng)。如果兩個(gè)節(jié)點(diǎn)中的入口項(xiàng)之和不大于n個(gè)，則將兩個(gè)節(jié)點(diǎn)合并為一個(gè)節(jié)點(diǎn)，并將被刪除節(jié)點(diǎn)在父節(jié)點(diǎn)中的入口項(xiàng)刪除；否則，將兩個(gè)節(jié)點(diǎn)間的入口項(xiàng)重新分配，并相應(yīng)地更新在父節(jié)點(diǎn)中的索引鍵值。由于節(jié)點(diǎn)的合并需要在父節(jié)點(diǎn)中刪除入口項(xiàng)，因此又可能導(dǎo)致父節(jié)點(diǎn)向下溢出。節(jié)點(diǎn)的合并操作可能一直上傳到根節(jié)點(diǎn)，如果根節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)合并為一個(gè)節(jié)點(diǎn)，則將原根節(jié)點(diǎn)刪除，而將合并后的子節(jié)點(diǎn)設(shè)為新的根節(jié)點(diǎn)第37頁，共55頁，2023年，2月20日，星期六刪除60后的B+樹第38頁，共55頁，2023年，2月20日，星期六繼續(xù)刪除10后的B+樹第39頁，共55頁，2023年，2月20日，星期六哈希索引哈希索引的基本思想是用一個(gè)哈希函數(shù)將索引鍵值映射到記錄所處的位置，通常稱為桶根據(jù)索引中桶的數(shù)目變化與否，哈希索引又分為靜態(tài)哈希和動(dòng)態(tài)哈希兩種若要查找哈希索引中的入口項(xiàng)，首先對(duì)指定的索引鍵值進(jìn)行同樣的哈希計(jì)算，根據(jù)計(jì)算的結(jié)果找到該入口項(xiàng)所處的桶，然后在其主塊和溢出塊鏈表中進(jìn)行順序查找即可若要向哈希索引中插入一個(gè)入口項(xiàng)，首先對(duì)其鍵值進(jìn)行哈希計(jì)算，然后將其插入到哈希結(jié)果所示的桶中，如果桶中沒有中夠的空間，則為該桶開辟一個(gè)新的溢出塊然后將該入口項(xiàng)插入到新開辟的塊中若要?jiǎng)h除哈希索引中的入口項(xiàng)，首先根據(jù)查找算法找到該項(xiàng)，然后將其從所處的塊中刪除。若刪除后該塊為空且為溢出塊，則將該塊從所處桶的溢出塊鏈表中刪除第40頁，共55頁，2023年，2月20日，星期六靜態(tài)哈希哈希函數(shù)，一個(gè)好的哈希函數(shù)能夠?qū)⑺饕I值比較平均的分配到各個(gè)桶中去桶的數(shù)量：為了不產(chǎn)生溢出現(xiàn)象，桶的數(shù)量nB需要滿足nB

>nr/fr，其中nr為預(yù)期的索引鍵值數(shù)，fr為每個(gè)塊中所能存儲(chǔ)的索引鍵值數(shù)。但在實(shí)際情況下通常無法達(dá)到完全平均分配，因此，在計(jì)算桶的數(shù)量時(shí)應(yīng)適量放寬20%到30%第41頁，共55頁，2023年，2月20日，星期六動(dòng)態(tài)哈希一般說來，數(shù)據(jù)庫中的數(shù)據(jù)總是隨著數(shù)據(jù)庫運(yùn)行時(shí)間的增長而增長，這樣在使用靜態(tài)哈希時(shí)選擇桶的數(shù)量就成了一個(gè)大問題。如果桶的數(shù)量過小，則隨著數(shù)據(jù)庫的運(yùn)行，索引中將會(huì)產(chǎn)生大量溢出塊，從而導(dǎo)致性能降低，反之，如果一開始就將桶的數(shù)量設(shè)得很大，則在很長一段時(shí)間內(nèi)又會(huì)造成空間的浪費(fèi)動(dòng)態(tài)哈希技術(shù)彌補(bǔ)了靜態(tài)哈希的上述缺陷，動(dòng)態(tài)哈希技術(shù)允許文件中的桶數(shù)動(dòng)態(tài)增長，同時(shí)又不需要重整。有兩種常用的動(dòng)態(tài)哈希：可擴(kuò)展哈希和線性哈希

第42頁，共55頁，2023年，2月20日，星期六查詢處理第43頁，共55頁，2023年，2月20日，星期六查詢優(yōu)化的兩種主要途徑代數(shù)優(yōu)化：根據(jù)等價(jià)變換規(guī)則將初始查詢樹轉(zhuǎn)換成另一種形式，代數(shù)優(yōu)化的輸入和輸出都是關(guān)系代數(shù)表達(dá)式，但輸出比輸入更有利于于執(zhí)行。代數(shù)優(yōu)化一般是基于規(guī)則的優(yōu)化，在代數(shù)優(yōu)化過程中一般較少使用統(tǒng)計(jì)信息，不進(jìn)行代價(jià)估計(jì)。由代數(shù)優(yōu)化產(chǎn)生的查詢樹又稱為最終查詢樹。物理優(yōu)化：為代數(shù)優(yōu)化產(chǎn)生的最終查詢樹生成不同的物理執(zhí)行計(jì)劃，并利用統(tǒng)計(jì)信息對(duì)計(jì)劃的執(zhí)行代價(jià)進(jìn)行估計(jì)，最后選擇其中代價(jià)最小的計(jì)劃作為輸出，因此，物理優(yōu)化是基于代價(jià)的優(yōu)化第44頁，共55頁，2023年，2月20日，星期六代數(shù)優(yōu)化Pnameσtitle=‘DatabaseSystemConcepts’bookauthorPnameσtitle=‘DatabaseSystemConcepts’bookauthor第45頁，共55頁，2023年，2月20日，星期六代數(shù)優(yōu)化的等價(jià)變換scustomer.customer_id=interest_in.customer_id

∧interest_in.category_id=category.category_id

∧=’張三’Ptagcustomerinterest_incategory××第46頁，共55頁，2023年，2月20日，星期六代數(shù)優(yōu)化的等價(jià)變換（續(xù)）scustomer.customer_id=interest_in.customer_idPtagcustomerinterest_incategory××s

interest_in.category_id=category.category_=’張三’s

interest_in.category_id=category.category_idPtagcustomerinterest_incategory××s

customer.customer_id=interest_in.customer_=’張三’第47頁，共55頁，2023年，2月20日，星期六物理優(yōu)化物理優(yōu)化在代數(shù)優(yōu)化之后進(jìn)行，其過程可以概括為“枚舉策略－估算代價(jià)－生成計(jì)劃”三步物理優(yōu)化是基于代價(jià)進(jìn)行的。物理優(yōu)化的思想是為每個(gè)操作考慮多種可行的執(zhí)行策略，并對(duì)每種執(zhí)行策略的代價(jià)進(jìn)行估計(jì)，然后選擇其中代價(jià)最小的作為最終的執(zhí)行策略代價(jià)估算是物理優(yōu)化的基礎(chǔ)，在DBMS中，執(zhí)行代價(jià)通常是用讀寫磁盤塊的次數(shù)來衡量的為了對(duì)各種操作的代價(jià)進(jìn)行估算，需要在數(shù)據(jù)庫記錄一些附加的數(shù)據(jù)，這些數(shù)據(jù)稱為統(tǒng)計(jì)信息，通常記錄在系統(tǒng)的數(shù)據(jù)字典中第48頁，共55頁，2023年，2月20日，星期六輔助信息nr：關(guān)系r中的元組數(shù)。br：關(guān)系r的數(shù)據(jù)文件中包含的數(shù)據(jù)塊數(shù)。lr：關(guān)系r中記錄的平均長度。fr：關(guān)系r的塊因子，即一個(gè)塊中平均有多少條記錄，fr≈nr/br。V(A,r)：關(guān)系r中屬性A的不同值個(gè)數(shù)。如果A是主鍵，則V(A,r)=nr。第49頁，共55頁，2023年，2月20日，星期六選擇操作的執(zhí)行策略順序掃描：對(duì)被選擇關(guān)系的數(shù)據(jù)文件進(jìn)行線性掃描，判斷掃描經(jīng)過的每一條記錄是否符合選擇條件。使用B+樹索引：當(dāng)在選擇條件涉及的列上建有B+樹索引時(shí)