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