aachapter時(shí)空權(quán)衡市公開(kāi)課一等獎(jiǎng)省賽課獲獎(jiǎng)?wù)n件

算法分析與設(shè)計(jì)

AnalysisandDesignofComputerAlgorithms

第七章時(shí)空權(quán)衡

SpaceandTimeTradeoffsaachapter時(shí)空權(quán)衡第1頁(yè)教學(xué)內(nèi)容時(shí)空權(quán)衡方法計(jì)數(shù)排序串匹配中輸入增強(qiáng)技術(shù)散列法B樹(shù)要求掌握時(shí)空權(quán)衡概念及基本方法，掌握時(shí)空權(quán)衡方法在常見(jiàn)問(wèn)題中應(yīng)用。算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院2aachapter時(shí)空權(quán)衡第2頁(yè)時(shí)空權(quán)衡時(shí)空權(quán)衡是指在算法設(shè)計(jì)中，對(duì)算法時(shí)間和空間作出權(quán)衡。通常使用額外存放空間來(lái)實(shí)現(xiàn)更加快或更方便數(shù)據(jù)存取。算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院3aachapter時(shí)空權(quán)衡第3頁(yè)空間換時(shí)間技術(shù)常見(jiàn)以空間換取時(shí)間方法輸入增強(qiáng)對(duì)問(wèn)題部分或全部輸入做預(yù)處理,然后對(duì)得到額外信息進(jìn)行存放,以加速后面問(wèn)題求解。比如：計(jì)數(shù)排序，串匹配算法改進(jìn)預(yù)結(jié)構(gòu)存取結(jié)構(gòu)—使用額外存放空間來(lái)實(shí)現(xiàn)更加快或更方便數(shù)據(jù)存取散列法，B樹(shù)動(dòng)態(tài)規(guī)劃(Chapter8)動(dòng)態(tài)規(guī)劃法也是與空間換時(shí)間思想相關(guān)，其基礎(chǔ)是把給定問(wèn)題重復(fù)子問(wèn)題解統(tǒng)計(jì)在表中，然后求所討論問(wèn)題解。算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院4aachapter時(shí)空權(quán)衡第4頁(yè)注意事項(xiàng)時(shí)間和空間必須相互競(jìng)爭(zhēng)？一個(gè)算法使用一個(gè)空間效率很高數(shù)據(jù)結(jié)構(gòu)，這種算法又會(huì)反過(guò)來(lái)提升算法時(shí)間效率。

比如：圖遍歷-領(lǐng)接鏈表數(shù)據(jù)壓縮目標(biāo)是節(jié)約空間而不是作為處理其它問(wèn)題技術(shù)算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院5空間換時(shí)間技術(shù)aachapter時(shí)空權(quán)衡第5頁(yè)7.1計(jì)數(shù)排序思緒：對(duì)待排序列表中每一個(gè)元素，算出列表中小于該元素元素個(gè)數(shù)，并把結(jié)果統(tǒng)計(jì)在一張表中。顯然地，這個(gè)“個(gè)數(shù)”指出了該元素在有序列表中位置。排序時(shí)只需簡(jiǎn)單地把列表中元素復(fù)制到它在新列表中對(duì)應(yīng)位置上。算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院6aachapter時(shí)空權(quán)衡第6頁(yè)算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院7623184961947000000301100122014300501022314502193147628496待排序初始i=0i=1i=2i=3i=4i=5最終排序后7.1計(jì)數(shù)排序舉例aachapter時(shí)空權(quán)衡第7頁(yè)算法ComparisonCountingSort(A[0..n-1])//用比較計(jì)數(shù)法對(duì)數(shù)組排序//輸入：可排序數(shù)組A[0..n-1]//輸出：有序數(shù)組S[0..n-1]for(i0ton-1)Count[i]0;for(i0ton-2)for(ji+1ton-1)if(A[i]<A[j])Count[j]Count[j]+1;else Count[i]Count[i]+1;for(i0ton-1)S[Count[i]]A[i];returnS;7.1計(jì)數(shù)排序算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院8aachapter時(shí)空權(quán)衡第8頁(yè)算法效率實(shí)際應(yīng)用時(shí)，計(jì)數(shù)排序法極少用到。不過(guò)，在一個(gè)情況下還是卓有成效，即待排序元素值都來(lái)自一個(gè)已知小集合。

比如：僅包含1，27.1計(jì)數(shù)排序算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院9aachapter時(shí)空權(quán)衡第9頁(yè)計(jì)數(shù)排序法一個(gè)應(yīng)用是分布計(jì)數(shù)假如元素值是來(lái)自位于[l,u]之間整數(shù)，我們能夠計(jì)算出這些值出現(xiàn)頻率，然后把它們存在數(shù)組F[0..u-l]中。然后把有序列表前F[0]個(gè)位置填l，接下來(lái)F[1]個(gè)位置填入l+1.7.1計(jì)數(shù)排序算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院10aachapter時(shí)空權(quán)衡第10頁(yè)7.1計(jì)數(shù)排序?qū)嵗嚎紤]下面數(shù)組排序

其中全部數(shù)字都來(lái)自于集合{11,12,13}，于是我們?nèi)ビ?jì)算它們出現(xiàn)得頻率：

接下來(lái)用這么從右到左掃描原始數(shù)組進(jìn)行排序：

131112131212位置123456111212121313數(shù)組值111213頻率132分布值146分布計(jì)數(shù)排序算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院11aachapter時(shí)空權(quán)衡第11頁(yè)D[0]D[1]D[2]

S[0]S[1]S[2]S[3]S[4]S[5]146136126125115015121213121113A[5]=12A[4]=12A[3]=13A[2]=12A[1]=11A[0]=137.1計(jì)數(shù)排序分布計(jì)數(shù)排序算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院12aachapter時(shí)空權(quán)衡第12頁(yè)7.1計(jì)數(shù)排序分布計(jì)數(shù)排序算法：DistributionSort(A[0..n-1])//用分布計(jì)數(shù)法，對(duì)來(lái)自于有限范圍整數(shù)一個(gè)數(shù)組進(jìn)行排序//輸入：可排序數(shù)組A[0..n-1]，其元素值位于l和u之間（l<=u）//輸出：將A中元素按照升序排列數(shù)組S[0..n-1]forj=0tou-ldoD[j]=0fori=ton-1doD[A[i]-l]=D[A[i]-l]+1forj=1tou-ldoD[j]=D[j-1]+D[j]fori=n-1to0do j=A[i]-l S[D[j]-1]=A[i] D[j]=D[j]-1returnS 算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院13aachapter時(shí)空權(quán)衡第13頁(yè)7.1計(jì)數(shù)排序分布計(jì)數(shù)排序

算法效率：線性效率算法

它是我們當(dāng)前為止碰到過(guò)時(shí)間效率最高排序算法。

然而，分布計(jì)數(shù)排序這種高效率是因?yàn)槔昧溯斎肓斜愍?dú)特自然屬性。作為一個(gè)思索題：你是否能夠預(yù)計(jì)對(duì)于這么算法比起其它排序來(lái)講，需要多少額外空間？！算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院14aachapter時(shí)空權(quán)衡第14頁(yè)7.2串匹配中輸入增強(qiáng)技術(shù)串匹配中輸入增強(qiáng)思想對(duì)模式進(jìn)行預(yù)處理，得到它一些信息，然后在查找過(guò)程中使用這些信息。兩種著名算法Knuth-Morris-Part(abbr.KMP)Boyer-Moore(abbr.BM)算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院15aachapter時(shí)空權(quán)衡第15頁(yè)7.2.1Horspool算法考慮在一些文本中查找模式BARBERs0s1...c...sn-1BARBERs0s1...S...sn-1BARBER

BARBERs0s1...B...sn-1BARBER

BARBERs0s1...MER...sn-1LEADER

LEADERs0s1...OR...sn-1REORDER

REORDER移動(dòng)幅度等于模式長(zhǎng)度移動(dòng)幅度等于模式長(zhǎng)度模式中最右邊字符c和文本中c對(duì)齊把模式中前m-1個(gè)字符中c和文本中c對(duì)齊算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院16aachapter時(shí)空權(quán)衡第16頁(yè)模式移動(dòng)距離

對(duì)于每一個(gè)字符c，移動(dòng)距離t(c)為：t(c)=模式長(zhǎng)度m ,假如c不包含在模式前m-1個(gè)字符中模式前m-1個(gè)字符中最右邊c到模式最終一個(gè)字符距離 ,其它比如：對(duì)于模式BAEBER，E,B,R,A移動(dòng)距離分別為1,2,3,4，其它為6算法ShiftTable(P[0..m-1])//用Horspool算法和Boyer-Moore算法填充移動(dòng)表//輸入：模式p[0..m-1]以及一個(gè)可能出現(xiàn)字符字符表//輸出：以字母表中字符為索引數(shù)組table[0..size-1]把Table中全部元素初始化為m；for(j0tom-2)doTable[P[j]]m-1-j;returnTable;127.2.1Horspool算法算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院17aachapter時(shí)空權(quán)衡第17頁(yè)小結(jié)：

第一步：對(duì)于給定長(zhǎng)度為m模式和在模式中用到字母表，按照一定描述結(jié)構(gòu)字符移動(dòng)表；

第二步：將模式與文本開(kāi)始對(duì)齊；

第三步：重復(fù)下面過(guò)程，直到發(fā)覺(jué)了一個(gè)匹配字串或則模式抵達(dá)了文本最終一個(gè)字符以外。

第四步：從模式最終一個(gè)字符開(kāi)始，比較模式和文本中對(duì)應(yīng)字符，假如全部m個(gè)字符都匹配，那么匹配成功，算法停頓；不然，進(jìn)入第五步；

第五步：假如碰到了一個(gè)不匹配字符，找到之前最終一個(gè)對(duì)齊字符c，然后將模式沿著文本向右移動(dòng)t(c)個(gè)字符距離；

算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院187.2.1Horspool算法aachapter時(shí)空權(quán)衡第18頁(yè)7.2.1Horspool算法算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院19aachapter時(shí)空權(quán)衡第19頁(yè)Horspool算法最差效率Θ(mn)對(duì)于隨機(jī)文本，它效率為Θ(n)7.2.1Horspool算法算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院20aachapter時(shí)空權(quán)衡第20頁(yè)7.2.2Boyer-Moore算法假如在碰到一個(gè)不匹配字符之前，假如已經(jīng)有k(0<k<m)個(gè)字符匹配成功，則Boyer-Moore算法與Horspool算法處理不一樣。在這種情況下，Boyer-Moore算法參考兩個(gè)數(shù)值來(lái)確定移動(dòng)距離。第一個(gè)數(shù)值是有文本中第一個(gè)字符c所確定，用公式t1(c)-k來(lái)計(jì)算其中t1(c)是Horspool算法用到預(yù)先算好值，k是成功匹配字符個(gè)數(shù)算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院21aachapter時(shí)空權(quán)衡第21頁(yè)t1(A)-2=4-2=2d1=max{t1(c)-k,1}t1(S)-2=6-2=4壞符號(hào)移動(dòng)用i表示不匹配位置,i=i+patlen用i表示不匹配位置,i=i+t(‘A’)7.2.2Boyer-Moore算法算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院22aachapter時(shí)空權(quán)衡第22頁(yè)第二個(gè)數(shù)值是由模式中最終k>0個(gè)成功匹配字符所確定。稱(chēng)為好后綴移動(dòng)把模式結(jié)尾部分叫做模式長(zhǎng)度為k后綴，記作suff(k)情況1：當(dāng)模式中存在兩個(gè)以上suff(k)情況時(shí)，移動(dòng)距離d2就是從第一個(gè)后綴最右元素位置數(shù)到第二個(gè)suff(k)最右邊距離。7.2.2Boyer-Moore算法算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院23aachapter時(shí)空權(quán)衡第23頁(yè)情況2：當(dāng)模式中存在1個(gè)suff(k)情況時(shí)：k=3移動(dòng)6k=3移動(dòng)？次7.2.2Boyer-Moore算法算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院24aachapter時(shí)空權(quán)衡第24頁(yè)為了防止情況2出現(xiàn)，我們需要找出長(zhǎng)度為l<k最長(zhǎng)前綴，它能夠和長(zhǎng)度一樣為l后綴完全匹配。假如存在這么前綴，我們經(jīng)過(guò)求出這么前綴和后綴之間距離來(lái)作為移動(dòng)距離d2值，不然移動(dòng)距離就是m7.2.2Boyer-Moore算法算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院25aachapter時(shí)空權(quán)衡第25頁(yè)7.2.2Boyer-Moore算法：流程圖26算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院aachapter時(shí)空權(quán)衡第26頁(yè)7.2.2Boyer-Moore算法算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院27aachapter時(shí)空權(quán)衡第27頁(yè)在一個(gè)由英文字母和空格組成文本中查找BAOBABcABCD...O...Z-t1(c)126663666壞符號(hào)移動(dòng)表好后綴移動(dòng)表7.2.2Boyer-Moore算法：舉例aachapter時(shí)空權(quán)衡第28頁(yè)7.3散列法散列法基本思想：把鍵分布在一個(gè)稱(chēng)為散列表一維數(shù)組H[0..m-1]中。能夠利用散列函數(shù)來(lái)計(jì)算每個(gè)鍵值，該函數(shù)為每個(gè)鍵指定一個(gè)稱(chēng)為散列地址值，該值是位于0到m-1之間整數(shù)。假如鍵是一個(gè)非負(fù)整數(shù)，則h(K)=Kmodm假如鍵是某個(gè)字母表中字母，則能夠把該字母在字母表中位置指定個(gè)鍵，記為ord(K)假如鍵是一個(gè)字符串c0c1...cs-1，則定義h(K)=(∑ord(ci))modm或者h(yuǎn)0;fori0tos-1doh(h*C+ord(ci))modm算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院29aachapter時(shí)空權(quán)衡第29頁(yè)一個(gè)散列函數(shù)必須滿足兩個(gè)要求：需要把鍵在散列表單元中盡可能均勻分布必須是輕易計(jì)算碰撞當(dāng)散列表長(zhǎng)度m小于鍵數(shù)量n時(shí)，會(huì)有兩個(gè)或多個(gè)鍵被散列到同一個(gè)單元中即使m相對(duì)于n足夠大，碰撞還是會(huì)發(fā)生散列法兩個(gè)版本開(kāi)散列（分離鏈）閉散列（開(kāi)式尋址）7.3散列法算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院30aachapter時(shí)空權(quán)衡第30頁(yè)在開(kāi)散列中，鍵被存放于散列表單元鏈表中。A,FOOL,AND,HIS,MONEY,ARE,SOON,PARTED鍵AFOOLANDHISMONEYARESOONPARTED散列地址1961071111127.3散列法-開(kāi)散列/分離鏈31算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院aachapter時(shí)空權(quán)衡第31頁(yè)普通來(lái)說(shuō)，查找效率取決于鏈表長(zhǎng)度，而這個(gè)長(zhǎng)度有取決于字典和散列表長(zhǎng)度以及散列函數(shù)質(zhì)量。假如該散列函數(shù)大致均勻地將n個(gè)鍵分布在散列表m個(gè)單元中，每個(gè)鏈表長(zhǎng)度大約相當(dāng)于n/m，其α=n/m稱(chēng)為散列表負(fù)載因子。成功查找中平均需檢驗(yàn)指針個(gè)數(shù)S=1+α/2不成功查找中平均需檢驗(yàn)指針個(gè)數(shù)U=α通常情況下，我們希望負(fù)載因子和1不要相差太大。7.3散列法-開(kāi)散列/分離鏈算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院32aachapter時(shí)空權(quán)衡第32頁(yè)全部鍵都存放在散列表本身，采取線性探查處理沖突，即碰撞發(fā)生時(shí)，假如下一個(gè)單元格空，則放下在一個(gè)單元格，假如不空，則繼續(xù)找到下一個(gè)空單元格，假如到了表尾，則返回到表首繼續(xù)。鍵AFOOLANDHISMONEYARESOONPARTED散列地址1961071111120123456789101112AFOOLAFOOLAANDFOOLHISAANDFOOLHISAANDMONEYFOOLHISAANDMONEYFOOLHISAREAANDMONEYFOOLHISARESOONPAETEDAANDMONEYFOOLHISARESOON7.3散列法-閉散列/開(kāi)式尋址33算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院aachapter時(shí)空權(quán)衡第33頁(yè)閉散列查找和插入操作是簡(jiǎn)單而直接，不過(guò)刪除操作則會(huì)帶來(lái)不利后果。比起分離鏈，現(xiàn)行探查數(shù)學(xué)分析是一復(fù)雜多問(wèn)題。對(duì)于復(fù)雜因子為α散列表，成功查找和不成功查找必須要訪問(wèn)次數(shù)分別為：S≈(1+1/(1-α))/2 U≈(1+1/(1-α)2)/2散列表規(guī)模越大，該近似值越準(zhǔn)確7.3散列法-閉散列/開(kāi)式尋址算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院34aachapter時(shí)空權(quán)衡第34頁(yè)

當(dāng)數(shù)據(jù)膨脹到一個(gè)可怕程度時(shí)，連索引都不能被全部裝入內(nèi)存——見(jiàn)過(guò)印刷版EI檢索都有這個(gè)感覺(jué)，光一個(gè)檢索目錄都比我們用字典厚。處理方法就是索引再索引，顯而易見(jiàn)，每個(gè)索引塊都應(yīng)該盡可能大，以幫助我們?nèi)〉帽M可能多信息，而防止再次查索引（此時(shí)普通都會(huì)包括外存存?。?。AVL樹(shù)此時(shí)便力不從心了，我們需要一個(gè)新結(jié)構(gòu)——B樹(shù)。算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院357.4B樹(shù)aachapter時(shí)空權(quán)衡第35頁(yè)在B樹(shù)中，全部數(shù)據(jù)統(tǒng)計(jì)都按照鍵增序存放在葉子中，它們父節(jié)點(diǎn)作為索引。一棵次數(shù)為m≥2B樹(shù)必須滿足下面這些結(jié)構(gòu)上特征：它根要么是一個(gè)葉子，要么含有2到m個(gè)兒女；除了根和葉子節(jié)點(diǎn)以外每個(gè)節(jié)點(diǎn)，含有[m/2]到m個(gè)兒女；這個(gè)樹(shù)是（完美）平衡，即它全部葉子節(jié)點(diǎn)都在同一層上。7.4B樹(shù)算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院36aachapter時(shí)空權(quán)衡第36頁(yè)在查找鍵給定某條統(tǒng)計(jì)中，需要訪問(wèn)多少個(gè)B樹(shù)節(jié)點(diǎn)？對(duì)于任何包含n個(gè)節(jié)點(diǎn)、次數(shù)為m、高度為h>0B樹(shù)來(lái)說(shuō)，有：7.4B樹(shù)算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院37aachapter時(shí)空權(quán)衡第37頁(yè)7.4B樹(shù)B樹(shù)即平衡樹(shù)B樹(shù)索引是關(guān)系型數(shù)據(jù)庫(kù)中最為普通索引。它特點(diǎn)是以樹(shù)形式存放數(shù)據(jù)，不但存放了對(duì)應(yīng)列數(shù)據(jù)，還存放了ROWID。索引基礎(chǔ)是（ROOTNODE）根節(jié)點(diǎn)，根節(jié)點(diǎn)包含指向索引下一層其它節(jié)點(diǎn)（分枝節(jié)點(diǎn)）指針，分枝節(jié)點(diǎn)指向索引最高/下層即葉節(jié)點(diǎn)。在葉節(jié)點(diǎn)索引項(xiàng)中包含了被索引列值及存放這些列值行對(duì)應(yīng)（ROWID）算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院38aachapter時(shí)空權(quán)衡第38頁(yè)B-樹(shù)結(jié)點(diǎn)規(guī)模

在信息存放過(guò)程中，對(duì)于大數(shù)據(jù)庫(kù)存放，為了能確保數(shù)據(jù)高效檢索，降低IO訪問(wèn)次數(shù)?，F(xiàn)有多數(shù)數(shù)據(jù)庫(kù)系統(tǒng)采取是b樹(shù)或者b+樹(shù)索引算法。

普通做法是：對(duì)于存放在物理單元上數(shù)據(jù)，進(jìn)行邏輯分頁(yè)。然后緩存頁(yè)面索引。有甚至進(jìn)行二次分頁(yè)。目標(biāo)只有一個(gè)就是盡可能降低IO訪問(wèn)。檢索時(shí)經(jīng)過(guò)對(duì)物理數(shù)據(jù)分頁(yè)，在內(nèi)存或者外存中維護(hù)關(guān)鍵字頁(yè)索引數(shù)據(jù)。當(dāng)進(jìn)行數(shù)據(jù)檢索時(shí)，經(jīng)過(guò)關(guān)鍵字頁(yè)匹配，把外存上物理數(shù)據(jù)讀入內(nèi)存，然后再進(jìn)行匹配。對(duì)于大數(shù)據(jù)情況下，有可能需要進(jìn)行屢次頁(yè)數(shù)據(jù)讀取。7.4B樹(shù)算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院39aachapter時(shí)空權(quán)衡第39頁(yè)

在大多數(shù)系統(tǒng)中，B-樹(shù)上算法執(zhí)行時(shí)間主要由讀、寫(xiě)磁盤(pán)次數(shù)來(lái)決定，每次讀寫(xiě)盡可能多信息可提升算法得執(zhí)行速度。

B-樹(shù)中結(jié)點(diǎn)規(guī)模普通是一個(gè)磁盤(pán)頁(yè)，而結(jié)點(diǎn)中所包含關(guān)鍵字及其孩子數(shù)目取決于磁盤(pán)頁(yè)大小。

注意：

①對(duì)于磁盤(pán)上一棵較大B-樹(shù)，通常每個(gè)結(jié)點(diǎn)擁有孩子數(shù)目(即結(jié)點(diǎn)度數(shù))m為50至不等

②一棵度為mB-樹(shù)稱(chēng)為m階B-樹(shù)。

③選取較大結(jié)點(diǎn)度數(shù)可降低樹(shù)高度，以及降低查找任意關(guān)鍵字所需磁盤(pán)訪問(wèn)次數(shù)。B-樹(shù)結(jié)點(diǎn)規(guī)模

7.4B樹(shù)算法分析與設(shè)計(jì)蘭州大學(xué)信息學(xué)院40aachapter時(shí)空權(quán)衡第40頁(yè)7.4B樹(shù)查找方法

在B-樹(shù)中查找給定關(guān)鍵字方法類(lèi)似于二叉排序樹(shù)上查找。不一樣是在每個(gè)