【文章內(nèi)容簡(jiǎn)介】 RL 情況：（ RL： 表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的 右子樹(shù) 的 左子樹(shù)上 ） A、 處理圖形和 LRA 鏡象相似 B、 處理圖形和 LRB 鏡象相似 C、 處理圖形和 LRC 鏡象相似? 刪除情況：略? 程序?qū)崿F(xiàn)：略、 B_ 樹(shù)和 B+ 樹(shù) 為什么采用 B_ 樹(shù)和 B+ 樹(shù)：大量數(shù)據(jù)存放在外存中，通常存放在硬盤(pán)中。由于是海量數(shù)據(jù)，不可能一次調(diào)入內(nèi)存。因此，要多次 訪問(wèn)外存。但硬盤(pán)的驅(qū)動(dòng)受機(jī)械運(yùn)動(dòng)的制約，速度慢。所以，主要矛盾變?yōu)闇p少訪外次數(shù)。在 1970 年由 R bayer 和 E macreight 提出用 B_ 樹(shù)作為索引組織文件。提高訪問(wèn)速度、減少時(shí)間。 內(nèi)存: 用二叉樹(shù)組織文件，當(dāng)文件的記錄個(gè)數(shù)為 100， 000時(shí)，要找到給定關(guān)鍵字的記錄，需訪問(wèn)外存17次（ log100,000） ,太長(zhǎng)了！5025107515 35 60 9020 30 40 55 70 80 95索引文件數(shù)據(jù)文件文件頭，可常駐內(nèi)存文件訪問(wèn)示意圖：索引文件、數(shù)據(jù)文件存在盤(pán)上 B_ 樹(shù)是一種多分支數(shù)，首先介紹 m 階 B_ 樹(shù)：? 定義： m 階 B_ 樹(shù)滿足或空，或：A、 根結(jié)點(diǎn)要么是葉子，要么至少有兩個(gè)兒子B、 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的兒子個(gè)數(shù)為 : m/2 = s = mC、 有 s 個(gè)兒子的非葉結(jié)點(diǎn)具有 n = s － 1 個(gè)關(guān)鍵字，即 : s = n + 1 這些結(jié)點(diǎn)的數(shù)據(jù)信息為： （ n, A0, K1, R1, A1, K2, R2, A2, ……… Kn, Rn, An） 這里： n: 關(guān)鍵字的個(gè)數(shù) A0： K1 的結(jié)點(diǎn)的地址（指在該 B_ 樹(shù)中） K1： 關(guān)鍵字 R1： 關(guān)鍵字 = K1 的數(shù)據(jù)記錄在硬盤(pán)中的地址 A2： K1 且 K2 的結(jié)點(diǎn)的地址（指在該 B_ 樹(shù)中） 余類推 ……… An： Kn 的結(jié)點(diǎn)的地址（指在該 B_ 樹(shù)中） 注意： K1 =K2 = …... = KnD、 所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層上，不帶信息（可認(rèn)為外部結(jié)點(diǎn)或失敗結(jié)點(diǎn)）。例如： m = 4 階 B_ 樹(shù)。 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的兒子個(gè)數(shù)至少為 m/2 = 2 個(gè)；結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)至少為 1 。該 B_ 樹(shù)的深度為 4。葉子結(jié)點(diǎn)都在第 4 層上。1， 993， 47， 58， 641， 391， 271， 112， 43， 781， 181， 35F F F F F FF F F F F F第 1 層第 2 層第 3 層 (L層 )第 4 層 (L＋ 1層 )B_ 樹(shù)和 B+ 樹(shù) B_ 樹(shù)的查找代價(jià)分析：? 查找過(guò)程，類似于二叉樹(shù)的查找。如查找關(guān)鍵字為 KEY 的記錄。 從根開(kāi)始查找，如果 Ki = KEY 則查找成功， Ri 為關(guān)鍵字為 KEY 的記錄的地址。 若 Ki KEY Ki+1。 查找 Ai 指向的結(jié)點(diǎn) 若 KEY K1。 查找 A0 指向的結(jié)點(diǎn) 若 KEY Kn。 查找 An指向的結(jié)點(diǎn) 若 找到葉子，則查找失敗。注意：每次查找將去掉 （ s1） /s 個(gè)分支，比二分查找快得多。? 設(shè)關(guān)鍵字的總數(shù)為 N ， 求 m階 B_ 樹(shù)的最大層次 L。層次 結(jié)點(diǎn)數(shù) 關(guān)鍵字的個(gè)數(shù)（最少）1 1 12 2 2（ m/2 1）3 2（ m/2 ） 2（ m/2 ） （ m/2 1）4 2（ m/2 ） 2 2（ m/2 ） 2 （ m/2 1）L 2（ m/2 ） L2 2（ m/2 ） L2 （ m/2 1）L+1 2（ m/2 ） L1所以， N=1＋ 2（ m/2 1） +……...+ 2 （ m/2 ） L2 （ m/2 1） = 2 m/2 L1 1故： L＝ log （（ N+1） /2） + 1B_ 樹(shù)和 B+ 樹(shù) B_ 樹(shù)的查找代價(jià)分析：? 設(shè)關(guān)鍵字的總數(shù)為 N ， 求 m階 B_ 樹(shù)的最大層次 L。故： L＝ log m/2 （（ N+1） /2） + 1設(shè) N ＝ 1000， 000 且 m＝ 256 ， 則 L = 3； 最多 3 次訪問(wèn)外存可找到所有的記錄。 B_ 樹(shù)的插入操作確定插入位置，將結(jié)點(diǎn)插入到第 L 層（注意：第 L+1 層為葉子結(jié)點(diǎn)）找到插入位置，將關(guān)鍵字和其它信息按 序 插入。若被插入結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù) m1, 則該結(jié)點(diǎn)滿。必須分裂成兩個(gè)結(jié)點(diǎn)。否則不滿結(jié)束。如結(jié)點(diǎn)原為： （ m1, A0, (K1, A1), (K2, A2), ……… (K m1, Am1)）插入一個(gè)關(guān)鍵字之后變?yōu)椋? （ m, A0, (K1, A1), (K2, A2), ……… (K m, Am)）該結(jié)點(diǎn)將進(jìn)行分裂： …………... (K m/2 , p‘ ) …………...（ m/21, A0, (K1, A1), ……… (K m/2 , A m/2 )） （ m m/2 , A m/2 , ……… (K m, Am)） 生成新結(jié)點(diǎn) p‘, 將原結(jié)點(diǎn)的后半部分復(fù)制過(guò)去。若分裂一直進(jìn)行到根結(jié)點(diǎn)，樹(shù)可能長(zhǎng)高一層。P’P(K m/2 , p‘ ) 數(shù)據(jù)項(xiàng)插入上層結(jié)點(diǎn)之中B_ 樹(shù)和 B+ 樹(shù) 例如： 3 階 B_ 樹(shù)的插入操作。 m=3, m/2 1 = 1。 至少 1 個(gè)關(guān)鍵字，二個(gè)兒子結(jié)點(diǎn)。3， 127 24 3024， 3045， 7053 9026 10039 50 61 85 345， 7053 9026 10039 50 61 851230324 45 7053 9026 10039 50 61 85127 3032453 9026 10039 50 61 85127 45 707插入B_ 樹(shù)和 B+ 樹(shù) B_ 樹(shù)的刪除操作查找具有給定鍵值的關(guān)鍵字 Ki 如果 在 第 L 層，可直接刪除（注意：第 L+1 層為葉子結(jié)點(diǎn)），轉(zhuǎn) 4 。否則，則首先生成 “替身 ”。用 的右子樹(shù)中的最左面的結(jié)點(diǎn)的關(guān)鍵字值，即 處于第 L 層上的最小 關(guān)鍵字值取代 。然后，刪除第 L 層上的該關(guān)鍵字。從第 L 層開(kāi)始進(jìn)行刪除。 A、 不動(dòng)：若刪除關(guān)鍵字值的那個(gè)結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)仍處于 m/2 1和 m1之間。則結(jié)束。 B、 借：若刪除關(guān)鍵字值的那個(gè)結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)原為 m/2 1 。 而它們的左或右鄰居結(jié) 點(diǎn)的關(guān)鍵字的個(gè)數(shù) m/2 1 。 則借一個(gè)關(guān)鍵字過(guò)來(lái)。處理結(jié)束。 C、 并：若該結(jié)點(diǎn)的左或右鄰居結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)為 m/2 1 。 則執(zhí)行合并結(jié)點(diǎn)的操作。如結(jié)點(diǎn)原為： （ …………. ( Ki, Ai), (Ki+1, Ai+1), …………. ） （ A0’, (K1’, A1’ ) ……… ） （ A0’‘, (K1’‘, A1’‘ ) ……… ） …… K 1L ……… 第 L 層：找到了被刪結(jié)點(diǎn)的替身。B_ 樹(shù)和 B+ 樹(shù) 例如： 3 階 B_ 樹(shù)的刪除操作。 m=3, m/2 1 = 1。 至少 1 個(gè)關(guān)鍵字，二個(gè)兒子結(jié)點(diǎn)。3244553 9037 10050 61， 70被刪關(guān)鍵字3244561 9037 10053 70借：向被刪結(jié)點(diǎn)方向旋轉(zhuǎn)假定再刪除該關(guān)鍵字32445 9037 10061， 70假定再刪除該關(guān)鍵字3， 2445 9010061， 70 3， 24 45 9010061， 70并并并并：和父結(jié)點(diǎn)的一個(gè)關(guān)鍵字、及鄰居合并。有可能進(jìn)行到根，使 B_ 樹(shù)的深度降低一層！167。 哈希表– 基本思想： 在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系；這樣，不經(jīng)過(guò)比較，一次存取就能得到所查元素的查找方法– 定義? 哈希函數(shù) —— 在記錄的 關(guān)鍵字 與記錄的 存儲(chǔ)地址 之間建立的一種對(duì)應(yīng)關(guān)系叫 ~–哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲(chǔ)地址空間的一種映象–哈希函數(shù)可寫(xiě)成： addr(ai)=H(ki)187。ai是表中的一個(gè)元素187。addr(ai)是 ai的存儲(chǔ)地址187。ki是 ai的關(guān)鍵字 關(guān)鍵字集合存儲(chǔ)地址集合hash哈希表 —— 應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫 ~哈希查找 —— 又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過(guò)程叫 ~例 30個(gè)地區(qū)的各民族人口統(tǒng)計(jì)表編號(hào) 地區(qū)別 總?cè)丝? 漢族 回族 …...1 北京2 上?！?.. …...以編號(hào)作關(guān)鍵字，構(gòu)造 哈希函數(shù)： H(key)=keyH(1)=1H(2)=2以地區(qū)別作關(guān)鍵字，取地區(qū)名稱第一個(gè)拼音字母的在字母表中序號(hào)作哈希函數(shù)： H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19從例子可見(jiàn)：–哈希函數(shù)只是一種映象，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長(zhǎng)允許的范圍之內(nèi)即可–沖突 ： key1?key2， 但 H(key1)=H(key2)的現(xiàn)象叫 ~–同義詞 ：具有相同函數(shù)值的兩個(gè)關(guān)鍵字，叫該哈希函數(shù)的 ~–哈希函數(shù)通常是一種壓縮映象，所以沖突不可避免 ，只能盡量減少；同時(shí)，沖突發(fā)生后，應(yīng)該有處理沖突的方法 哈希函數(shù)的構(gòu)造方法? 直接定址法–構(gòu)造：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)作哈希地址，即 H(key)=key 或 H(key)=akey+b–特點(diǎn)?直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會(huì)發(fā)生沖突?實(shí)際中能用這種哈希函數(shù)的情況很少? 數(shù)字分析法–構(gòu)造：對(duì)關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或若干位組合作哈希地址–適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事先知道的情況例 有 80個(gè)記錄，關(guān)鍵字為 8位十進(jìn)制數(shù)，哈希地址為 2位十進(jìn)制數(shù)8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5…..…..?? ? ??? ??分析： ?只取 8 ?只取 1 ?只取 4 ?只取 5 ????數(shù)