第五章索引技術(shù)-文庫(kù)吧
2025-08-25 13:39 本頁(yè)面
【正文】 關(guān)鍵字的個(gè)數(shù) . 5）樹中所有葉節(jié)點(diǎn)都出現(xiàn)在同一層上。 B樹 例 第五章 82 12 3 2 58 7 0 8 9 94 6 8 12 1 5 1 8 3 2 35 40 50 5 1 5 2 5 8 60 62 70 指向物理記錄 職工號(hào) 姓名 。5 王一 12 王二 。B樹中由小到大的結(jié)構(gòu)層次是：索引項(xiàng)－節(jié)點(diǎn)－樹。 ?索引項(xiàng)結(jié)構(gòu) 索引項(xiàng)的結(jié)構(gòu)可表示如下： struct IdxItemStruct{ /*索引項(xiàng)的結(jié)構(gòu)，長(zhǎng) 64字節(jié) */ long N。 /*記錄號(hào)，長(zhǎng) 4字節(jié) */ long A。 /*索引項(xiàng)的右兒子指針， 4字節(jié) */ long K。 /*關(guān)鍵字 K, 56字節(jié) */ }。 typedef struct IdxItemStruct IdxItem。 /*索引類別名 */ ?節(jié)點(diǎn)結(jié)構(gòu) struct NodeStruct{ int ItesOnNode。 /*節(jié)點(diǎn)上實(shí)際項(xiàng)數(shù) */ long A0。 /*節(jié)點(diǎn)的左兒子指針 */ IdxItem IA[MaxItem]。 /*索引項(xiàng)數(shù)組 */ }。 實(shí)有項(xiàng)數(shù) 關(guān)鍵字 記錄號(hào) 2 A0 K1 ， N1 ， A1 K2 ， N2 ， A2 左兒子節(jié)點(diǎn)指針 右兒子 1 節(jié)點(diǎn)指針 右兒子 2 節(jié)點(diǎn)指針B樹的三大特點(diǎn) 1. 平衡性 。在動(dòng)態(tài)活動(dòng)（查、刪、改、重建）中，始終保持了平衡，即從任一個(gè)葉節(jié)點(diǎn)到根的路徑一樣長(zhǎng)。 B樹正是得名于平衡（ balanced）。平衡性保證了 1≤ 搜索步數(shù) ≤ B樹高度。從而避免了搜索效率因記錄而異引起的 “ 貧富不均 ” 。 2. 過半性 。除了根節(jié)點(diǎn)外（它至少有一個(gè)索引項(xiàng)），其余的節(jié)點(diǎn)上裝載因子永遠(yuǎn)過半。保證了在非根節(jié)點(diǎn)上 最大項(xiàng)數(shù) /2≤ 實(shí)有項(xiàng)數(shù) ≤ 最大項(xiàng)數(shù) 3. 順序性 。在動(dòng)態(tài)活動(dòng)中，始終左小右大。 對(duì)于每個(gè)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1