數(shù)據(jù)庫系統(tǒng)概論：chp9 關(guān)系查詢處理和查詢優(yōu)化

1、數(shù)據(jù)庫系統(tǒng)概論An Introduction to Database System第九章 關(guān)系查詢處理和查詢優(yōu)化1第九章 關(guān)系系統(tǒng)及其查詢優(yōu)化9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.3 代數(shù)優(yōu)化9.4 物理優(yōu)化 9.5 小 結(jié) 2關(guān)系系統(tǒng)及其查詢優(yōu)化（續(xù)）本章目的： RDBMS的查詢處理步驟 查詢優(yōu)化的概念 基本方法和技術(shù) 查詢優(yōu)化分類 ：代數(shù)優(yōu)化物理優(yōu)化39.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1.1 查詢處理步驟1. 查詢分析2. 查詢檢查3. 查詢優(yōu)化 4. 查詢執(zhí)行9.1.2 實(shí)現(xiàn)查詢操作的算法示例 4查詢處理步驟基于規(guī)則(rule based)基于代價(jià)(c

2、ost based)基于語義(semantic based)59.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1.1 查詢處理步驟1. 查詢分析2. 查詢檢查3. 查詢優(yōu)化 4. 查詢執(zhí)行9.1.2 實(shí)現(xiàn)查詢操作的算法示例 一、 選擇操作的實(shí)現(xiàn) 二、 連接操作的實(shí)現(xiàn) 6一、 選擇操作的實(shí)現(xiàn) 例1Select * from student where ；考慮的幾種情況： C1：無條件； C2：Sno200215121； C3：Sage20； C4：SdeptCS AND Sage20； 7選擇操作的實(shí)現(xiàn)（續(xù)）1. 簡單的全表掃描方法 對(duì)查詢的基本表順序掃描，逐一檢查每個(gè)元組是否滿足選擇條件，把滿足條件的元組

3、作為結(jié)果輸出 適合小表，不適合大表2. 索引(或散列)掃描方法 適合選擇條件中的屬性上有索引(例如B+樹索引或Hash索引) 通過索引，先找到滿足條件的元組主碼或元組指針，再通過元組指針，直接在查詢的基本表中找到元組 8選擇操作的實(shí)現(xiàn)（續(xù)）例1-C2 Sno200215121，并且Sno上有索引(或Sno是散列碼)使用索引(或散列)得到Sno為200215121 元組的指針通過元組指針在student表中檢索到該學(xué)生例1-C3 Sage20，并且Sage 上有B+樹索引使用B+樹索引找到Sage20的索引項(xiàng)，以此為入口點(diǎn)在B+樹的順序集上得到Sage20的所有元組指針通過這些元組指針到stud

4、ent表中檢索到所有年齡大于20的學(xué)生。 9選擇操作的實(shí)現(xiàn)（續(xù)）例1-C4 SdeptCS AND Sage20，如果Sdept和Sage上都有索引：算法一：分別用上面兩種方法分別找到SdeptCS的一組元組指針和Sage20的另一組元組指針求這2組指針的交集到student表中檢索得到計(jì)算機(jī)系年齡大于20的學(xué)生算法二：找到SdeptCS的一組元組指針，通過這些元組指針到student表中檢索對(duì)得到的元組檢查另一些選擇條件(如Sage20)是否滿足把滿足條件的元組作為結(jié)果輸出。 10二、 連接操作的實(shí)現(xiàn) 連接操作是查詢處理中最耗時(shí)的操作之一 本節(jié)只討論等值連接(或自然連接)最常用的實(shí)現(xiàn)算法 例

5、2 SELECT * FROM Student，SC WHERE Student.Sno=SC.Sno； 11連接操作的實(shí)現(xiàn)1. 嵌套循環(huán)方法(nested loop) 對(duì)外層循環(huán)(Student)的每一個(gè)元組(s)，檢索內(nèi)層循環(huán)(SC)中的每一個(gè)元組(sc),在連接屬性(sno)上是否相等2. 排序-合并方法(sort-merge join 或merge join)取Student表中第一個(gè)Sno，依次掃描SC表中具有相同Sno的元組200215121200215122200215123200215124.200215121 1 92200215121 2 85200215121 3 882

6、00215122 2 90200215122 3 80.排序-合并連接方法示意圖12連接操作的實(shí)現(xiàn)3. 索引連接(index join)方法 對(duì)Student中每一個(gè)元組，由Sno值通過SC的索引查找相應(yīng)的SC元組 把這些SC元組和Student元組連接起來13連接操作的實(shí)現(xiàn)4. Hash Join方法 把連接屬性作為hash碼，用同一個(gè)hash函數(shù)把R和S中的元組散列到同一個(gè)hash文件中步驟：劃分階段(partitioning phase)：對(duì)包含較少元組的表(比如R)進(jìn)行一遍處理把它的元組按hash函數(shù)分散到hash表的桶中試探階段(probing phase)：也稱為連接階段(join

7、 phase) 對(duì)另一個(gè)表(S)進(jìn)行一遍處理把S的元組散列到適當(dāng)?shù)膆ash桶中把元組與桶中所有來自R并與之相匹配的元組連接起來 14第九章 關(guān)系系統(tǒng)及其查詢優(yōu)化9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 關(guān)系系統(tǒng)的查詢優(yōu)化非關(guān)系系統(tǒng)9.3 代 數(shù) 優(yōu) 化 9.4 物 理 優(yōu) 化 9.5 小 結(jié) 159.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化影響RDBMS性能的關(guān)鍵因素 由于關(guān)系表達(dá)式的語義級(jí)別很高，使關(guān)系系統(tǒng)可以從關(guān)系表達(dá)式中分析查詢語義，提供了執(zhí)行查詢優(yōu)化的可能性 目標(biāo)：選擇有效的策略求得給定關(guān)系表達(dá)式的值使得查詢代價(jià)最小(實(shí)際上是較小) 16查詢優(yōu)化概述 用戶不必考慮如何最好

8、地表達(dá)查詢，系統(tǒng)可以比用戶程序的“優(yōu)化”做得更好 (1) 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息(2)如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的。(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，程序員一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動(dòng)優(yōu)化相當(dāng)于使得所有人都擁有這些優(yōu)化技術(shù)17查詢執(zhí)行策略的執(zhí)行代價(jià)RDBMS通過某種代價(jià)模型,計(jì)算出各種查詢執(zhí)行策略的執(zhí)行代價(jià)，然后選取代價(jià)最小的執(zhí)行

9、方案集中式數(shù)據(jù)庫執(zhí)行開銷主要包括：磁盤存取塊數(shù)(I/O代價(jià))處理機(jī)時(shí)間(CPU代價(jià))查詢的內(nèi)存開銷 I/O代價(jià)是最主要的 分布式數(shù)據(jù)庫總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)通信代價(jià) 189.2.2 一個(gè)實(shí)例例3 求選修了2號(hào)課程的學(xué)生姓名。用SQL表達(dá)： SELECT Student.Sname FROM Student，SC WHERE Student.Sno=SC.Sno AND SC.Cno=2； 假定：學(xué)生-課程數(shù)據(jù)庫中有1000個(gè)學(xué)生記錄，10000個(gè)選課記錄 其中選修2號(hào)課程的選課記錄為50個(gè) 可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式Q1=Sname(Student.Sno=SC.SnoS

10、c.Cno=2 (StudentSC)Q2=Sname(Sc.Cno=2 (Student SC)Q3=Sname(Student Sc.Cno=2(SC)19一、第一種情況 Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 StudentSC)1. 計(jì)算廣義笛卡爾積 把Student和SC的每個(gè)元組連接起來的做法：在內(nèi)存中盡可能多地裝入某個(gè)表(如Student表)的若干塊，留出一塊存放另一個(gè)表(如SC表)的元組。把SC中的每個(gè)元組和Student中每個(gè)元組連接，連接后的元組裝滿一塊后就寫到中間文件上從SC中讀入一塊和內(nèi)存中的Student元組連接，直到SC表處理完。再讀

11、入若干塊Student元組，讀入一塊SC元組重復(fù)上述處理過程，直到把Student表處理完201. 計(jì)算廣義笛卡爾積設(shè)一個(gè)塊能裝10個(gè)Student元組或100個(gè)SC元組，在內(nèi)存中存放5塊Student元組和1塊SC元組，則讀取總塊數(shù)為 =100+20100=2100塊其中，讀Student表100塊。讀SC表20遍，每遍100塊。若每秒讀寫20塊，則總計(jì)要花105s 連接后的元組數(shù)為103104=107。設(shè)每塊能裝10個(gè)元組，則寫出這些塊要用106/20=5104s 總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)通信代價(jià)212. 作選擇操作依次讀入連接后的元組，按照選擇條件選取滿足要求的記錄 假定

12、內(nèi)存處理時(shí)間忽略。讀取中間文件花費(fèi)的時(shí)間(同寫中間文件一樣)需5104s 滿足條件的元組假設(shè)僅50個(gè)，均可放在內(nèi)存 3. 作投影操作把第2步的結(jié)果在Sname上作投影輸出，得到最終結(jié)果 第一種情況下執(zhí)行查詢的總時(shí)間105+25104105s所有內(nèi)存處理時(shí)間均忽略不計(jì)Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 StudentSC)22二、 第二種情況 Q2=Sname(Sc.Cno=2 (Student SC)1. 計(jì)算自然連接 執(zhí)行自然連接，讀取Student和SC表的策略不變，總的讀取塊數(shù)仍為2100塊花費(fèi)105 s 自然連接的結(jié)果比第一種情況大大減少，為104個(gè)

13、 寫出這些元組時(shí)間為104/10/20=50s，為第一種情況的千分之一 2. 讀取中間文件塊，執(zhí)行選擇運(yùn)算，花費(fèi)時(shí)間也為50s。3. 把第2步結(jié)果投影輸出。 第二種情況總的執(zhí)行時(shí)間105+50+50205s 23三、 第三種情況1. 先對(duì)SC表作選擇運(yùn)算，只需讀一遍SC表，存取100塊花費(fèi)時(shí)間為5s，因?yàn)闈M足條件的元組僅50個(gè)，不必使用中間文件。2. 讀取Student表，把讀入的Student元組和內(nèi)存中的SC元組作連接。也只需讀一遍Student表共100塊，花費(fèi)時(shí)間為5s。3. 把連接結(jié)果投影輸出 第三種情況總的執(zhí)行時(shí)間5+510s Q3=Sname(Student Sc.Cno=2(S

14、C)24三、 第三種情況假如SC表的Cno字段上有索引第一步就不必讀取所有的SC元組而只需讀取Cno=2的那些元組(50個(gè))存取的索引塊和SC中滿足條件的數(shù)據(jù)塊大約總共34塊若Student表在Sno上也有索引第二步也不必讀取所有的Student元組因?yàn)闈M足條件的SC記錄僅50個(gè)，涉及最多50個(gè)Student記錄讀取Student表的塊數(shù)也可大大減少 總的存取時(shí)間將進(jìn)一步減少到數(shù)秒 25三種情況的比較把代數(shù)表達(dá)式Q1變換為Q2、 Q3，即有選擇和連接操作時(shí)，先做選擇操作，這樣參加連接的元組就可以大大減少，這是代數(shù)優(yōu)化在Q3中SC表的選擇操作算法,有全表掃描和索引掃描2種方法，經(jīng)過初步估算，索引

15、掃描方法較優(yōu) 對(duì)于Student和SC表的連接，利用Student表上的索引，采用index join代價(jià)也較小，這就是物理優(yōu)化 26第九章 關(guān)系系統(tǒng)及其查詢優(yōu)化9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.3 代數(shù)優(yōu)化 9.3.1 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則 9.3.2 查詢樹的啟發(fā)式優(yōu)化9.4 物理優(yōu)化 9.5 小 結(jié) 279.3.1 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則 代數(shù)優(yōu)化策略：通過對(duì)關(guān)系代數(shù)表達(dá)式的等價(jià)變換,來提高查詢效率 關(guān)系代數(shù)表達(dá)式的等價(jià)：指用相同的關(guān)系,代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系,所得到的結(jié)果是相同的兩個(gè)關(guān)系表達(dá)式E1和E2是等價(jià)的，可記為E1E2 28常

16、用的關(guān)系代數(shù)等價(jià)變換規(guī)則1）連接、笛卡爾積的交換2）連接、笛卡爾積的結(jié)合3）投影的串接4）選擇的串接295）選擇與投影的交換6）選擇與笛卡爾積的交換7）選擇與并的交換8）選擇與差的交換常用的關(guān)系代數(shù)等價(jià)變換規(guī)則(續(xù))309）投影與笛卡爾積的交換10）投影與并的交換常用的關(guān)系代數(shù)等價(jià)變換規(guī)則(續(xù))319.3 代數(shù)優(yōu)化9.3.1 關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則 9.3.2 查詢樹的啟發(fā)式優(yōu)化 選擇運(yùn)算應(yīng)盡可能先做投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行投影同其前或其后的雙目運(yùn)算結(jié)合把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來成為一個(gè)連接運(yùn)算找出公共子表達(dá)式329.3.2 查詢樹的啟發(fā)式優(yōu)化 典型的啟發(fā)式規(guī)則：1.

17、選擇運(yùn)算應(yīng)盡可能先做。在優(yōu)化策略中這是最重要、最基本的一條2. 把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行如有若干投影和選擇運(yùn)算，并且它們都對(duì)同一個(gè)關(guān)系操作，則可以在掃描此關(guān)系的同時(shí)完成所有的這些運(yùn)算以避免重復(fù)掃描關(guān)系33查詢樹的啟發(fā)式優(yōu)化（續(xù)）3. 把投影同其前或其后的雙目運(yùn)算結(jié)合起來4. 把某些選擇，同在它前面要執(zhí)行的笛卡爾積結(jié)合起來成為一個(gè)連接運(yùn)算5. 找出公共子表達(dá)式如果這種重復(fù)出現(xiàn)的子表達(dá)式的結(jié)果不是很大的關(guān)系并且從外存中讀入這個(gè)關(guān)系比計(jì)算該子表達(dá)式的時(shí)間少得多，則先計(jì)算一次公共子表達(dá)式并把結(jié)果寫入中間文件是合算的當(dāng)查詢的是視圖時(shí)，定義視圖的表達(dá)式就是公共子表達(dá)式的情況34優(yōu)化關(guān)系表達(dá)式的算法遵循

18、這些啟發(fā)式規(guī)則，應(yīng)用9.3.1的等價(jià)變換公式來優(yōu)化關(guān)系表達(dá)式的算法。算法：關(guān)系表達(dá)式的優(yōu)化輸入：一個(gè)關(guān)系表達(dá)式的查詢樹輸出：優(yōu)化的查詢樹方法：(1) 利用等價(jià)變換規(guī)則4把形如F1F2Fn(E)變換為F1(F2(Fn(E)。(2) 對(duì)每一個(gè)選擇，利用等價(jià)變換規(guī)則49盡可能把它移到樹的葉端。35查詢樹的啟發(fā)式優(yōu)化（續(xù)）(3) 對(duì)每一個(gè)投影利用等價(jià)變換規(guī)則3，5，10，11中的一般形式，盡可能把它移向樹的葉端。注意： 等價(jià)變換規(guī)則3使一些投影消失規(guī)則5把一個(gè)投影分裂為兩個(gè)，其中一個(gè)有可能被移向樹的葉端 (4) 利用等價(jià)變換規(guī)則35，把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。使

19、多個(gè)選擇或投影能同時(shí)執(zhí)行，或在一次掃描中全部完成 36查詢樹的啟發(fā)式優(yōu)化（續(xù)） (5) 把上述得到的語法樹的內(nèi)節(jié)點(diǎn)分組。每一雙目運(yùn)算(， ，-)和它所有的直接祖先為一組(這些直接祖先是(，運(yùn)算)。如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組但當(dāng)雙目運(yùn)算是笛卡爾積()，而且后面不是與它組成等值連接的選擇時(shí)，則不能把選擇與這個(gè)雙目運(yùn)算組成同一組，把這些單目運(yùn)算單獨(dú)分為一組 37示例SELECT Student.Sname FROM Student，SC WHERE Student.Sno=SC.Sno AND SC.Cno=2； (1) 把SQL語句轉(zhuǎn)換成查詢樹查詢樹 關(guān)系代數(shù)語法樹 38(

20、2) 對(duì)查詢樹進(jìn)行優(yōu)化利用規(guī)則選擇與笛卡爾積的交換律把選擇SC.Cno=2移到葉端，Q1=Sname(Student.Sno=SC.SnoSc.Cno=2 (StudentSC)Q3=Sname(Student Sc.Cno=2(SC) 優(yōu)化后的查詢樹 39例：在教學(xué)數(shù)據(jù)庫Student(Sno,Sname,Age,Sex)、SC(Sno,Cno,Grade)、Course(Cno,Cname,Teacher)中，查詢語句：檢索選修操作系統(tǒng)且成績?cè)?0分以上的所有學(xué)生姓名。（1）畫出關(guān)系代數(shù)表示的語法樹 （2）畫出優(yōu)化后的語法樹40第九章 關(guān)系系統(tǒng)及其查詢優(yōu)化9.1 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理

21、9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.3 代數(shù)優(yōu)化 9.4 物理優(yōu)化 9.5 小 結(jié) 419.4 物理優(yōu)化選擇高效合理的操作算法，或存取路徑，求得優(yōu)化的查詢計(jì)劃 選擇的方法： 基于規(guī)則的啟發(fā)式優(yōu)化基于代價(jià)估算的優(yōu)化兩者結(jié)合的優(yōu)化方法9.4.1 基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化9.4.2 基于代價(jià)的優(yōu)化42基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化一、 選擇操作的啟發(fā)式規(guī)則:全表掃描 VS 索引（有？使用？組合條件？）1. 對(duì)于小關(guān)系，使用全表順序掃描，即使選擇列上有索引 2.對(duì)于大關(guān)系，啟發(fā)式規(guī)則有：對(duì)于選擇條件是主碼值的查詢查詢結(jié)果最多是一個(gè)元組，可以選擇主碼索引一般的RDBMS會(huì)自動(dòng)建立主碼索引。4

22、3基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化3. 對(duì)于選擇條件是非主屬性值的查詢，并且選擇列上有索引4. 對(duì)于選擇條件是屬性上的非等值查詢或者范圍查詢，并且選擇列上有索引要估算查詢結(jié)果的元組數(shù)目如果比例較小(10%)可以使用索引掃描方法否則還是使用全表順序掃描 44基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化5. 對(duì)于用AND連接的合取選擇條件如果有涉及這些屬性的組合索引優(yōu)先采用組合索引掃描方法如果某些屬性上有一般的索引則可以用例1-C4中介紹的索引掃描方法否則使用全表順序掃描。6. 對(duì)于用OR連接的析取選擇條件，一般使用全表順序掃描45基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化二、 連接操作的啟發(fā)式規(guī)則：1. 如果2個(gè)表都

23、已經(jīng)按照連接屬性排序 選用排序-合并方法2. 如果一個(gè)表在連接屬性上有索引 選用索引連接方法3. 如果上面2個(gè)規(guī)則都不適用，其中一個(gè)表較小 選用Hash join方法46基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化4. 可以選用嵌套循環(huán)方法，并選擇其中較小的表，即占用的塊數(shù)(b)較少的表，作為外表(外循環(huán)的表) 。 理由：設(shè)連接表R與S分別占用的塊數(shù)為Br與Bs連接操作使用的內(nèi)存緩沖區(qū)塊數(shù)為K分配K-1塊給外表如果R為外表，則嵌套循環(huán)法存取的塊數(shù)為Br+( Br/K-1)Bs顯然應(yīng)該選塊數(shù)小的表作為外表 479.4.2 基于代價(jià)的優(yōu)化 啟發(fā)式規(guī)則優(yōu)化是定性的選擇，適合解釋執(zhí)行的系統(tǒng)解釋執(zhí)行的系統(tǒng)，優(yōu)化開銷

24、包含在查詢總開銷之中 編譯執(zhí)行的系統(tǒng)中，查詢優(yōu)化和查詢執(zhí)行是分開的可以采用精細(xì)復(fù)雜一些的基于代價(jià)的優(yōu)化方法 一、 統(tǒng)計(jì)信息 二、 代價(jià)估算示例48基于代價(jià)的優(yōu)化（續(xù)）一、 統(tǒng)計(jì)信息基于代價(jià)的優(yōu)化方法，要計(jì)算各種操作算法的執(zhí)行代價(jià)，與數(shù)據(jù)庫的狀態(tài)密切相關(guān) 數(shù)據(jù)字典中存儲(chǔ)的優(yōu)化器需要的統(tǒng)計(jì)信息： 1. 對(duì)每個(gè)基本表2. 對(duì)基表的每個(gè)列3. 對(duì)索引(如B+樹索引)49一、 統(tǒng)計(jì)信息1. 對(duì)每個(gè)基本表該表的元組總數(shù)(N)元組長度(l)占用的塊數(shù)(B)占用的溢出塊數(shù)(BO) 2. 對(duì)基表的每個(gè)列該列不同值的個(gè)數(shù)(m)選擇率(f)如果不同值的分布是均勻的，f1/m如果不同值的分布不均勻，則每個(gè)值的選擇率具有該值的元組數(shù)/N該列最大值該列最小值該列上是否已經(jīng)建立了索引索引類型(B+樹索引、Hash索引、聚集索引)3. 對(duì)索引(如B+樹索引)索引的層數(shù)(L)不同索引值的個(gè)數(shù)索引的選擇基數(shù)S(有S個(gè)元組具有某個(gè)索引值)索引的葉結(jié)點(diǎn)數(shù)(Y) 50二、 代價(jià)估算示例 1.全表掃描算法的代價(jià)估算公式如果基本表大小為B塊，全表掃描算法的代價(jià) costB如果選擇條件是碼值，那么平均搜索代價(jià)