【正文】 于或小于m。設 mleaf是葉結(jié)點可容納的最大失敗結(jié)點個數(shù)，則其中的實際關(guān)鍵字個數(shù) n應滿足： 1≤?mleaf/2? – 1≤n mleaf。 JYP 111 B+樹的葉結(jié)點被鏈接成雙鏈表 ， 以便范圍查詢 。 圖 B+樹的例子： 其中 ， m=3， mleaf=5。 以后的例子都假設 m=3，mleaf=5。 JYP 112 除了需要一直查到葉結(jié)點以外， B+樹的 查找 方法與 B樹的基本相同。 即使中間結(jié)點中已有需要查找的關(guān)鍵字，但那也只是“路標”，并不提供實際元素的地址。 例如，在圖 35。 35在根結(jié)點中，表示關(guān)鍵字為 35的元素在第 2棵子樹中。由根結(jié)點的第 2棵子樹的第 1個分枝，可到達關(guān)鍵字為 35的元素所在的葉結(jié)點。 JYP 113 往 B+樹中 插入 關(guān)鍵字為 x的元素的方法與 B樹的類似。 首先，定位到關(guān)鍵字為 x的元素可插入的葉結(jié)點 p。 如果結(jié)點 p不滿，則加入新元素，并將修改后的結(jié)點 p寫到磁盤即可。 如果結(jié)點 p已滿，則將其分裂為 p和 q兩個結(jié)點，這兩個結(jié)點平均承載原來結(jié)點 p中的內(nèi)容和新元素，且結(jié)點 q中元素的關(guān)鍵字大于結(jié)點 p中的。再將結(jié)點q中最小關(guān)鍵字和指針 q插入結(jié)點 p的雙親。 JYP 114 這又可能使雙親結(jié)點分裂，直至使根結(jié)點分裂，整個 B+樹長高一層。 圖 ，其中，中間結(jié)點的粗體字表示新插入的“路標”，葉結(jié)點的粗體字表示新插入的關(guān)鍵字。 JYP 115 圖 — 1 JYP 116 圖 — 2 JYP 117 從 B+樹中 刪除 關(guān)鍵字 x的方法也與 B樹的類似 。 首先 ， 定位到關(guān)鍵字 x所在的葉結(jié)點 p。 如果刪除后結(jié)點 p中的關(guān)鍵字個數(shù)仍然大于等于 ?mleaf/2?–1， 則將修改后的結(jié)點 p寫到磁盤即可 。 JYP 118 例如 ， 從圖 B+樹中刪除 30， JYP 119 得到圖 B+樹 。 注意 ， 雖然元素 30已被刪除 ，但作為 “ 路標 ” 的 30不必從中間結(jié)點中刪除 。 JYP 120 如果刪除后結(jié)點 p中只有 ?mleaf/2? – 2個關(guān)鍵字 ，且其最鄰近兄弟 q至少有 ?mleaf/2?個關(guān)鍵字 ， 則可從結(jié)點 q移一個到結(jié)點 p， 從而使這兩個結(jié)點都滿足要求 。 此過程還需要改變雙親結(jié)點中的 “ 路標 ” ， 以反映結(jié)點 p或 q中第一個關(guān)鍵字的值 。 JYP 121 例如 ， 從圖 B+樹中刪除 31， 使得第 2個葉結(jié)點中的 28被移來替代其原來的位置 ， 得到圖 的 B+樹 。 JYP 122 如果刪除后結(jié)點 p中只有 ?mleaf/2? – 2個關(guān)鍵字 ，且其最鄰近兄弟 q只有 ?mleaf/2? – 1個關(guān)鍵字 ， 則需要將結(jié)點 q的內(nèi)容合并到結(jié)點 p， 并刪除整個結(jié)點 q。 這又可能導致雙親結(jié)點關(guān)鍵字個數(shù)不足 ， 引起新一輪的旋轉(zhuǎn)與合并 ， 直至刪除根結(jié)點 。 JYP 123 圖 B+樹中刪除 35的過程 ，注意 ， “ 路標 ” 28移到根結(jié)點 ， 35移到根結(jié)點的右子女 。 圖 — 1 JYP 124 圖 — 2 JYP 125 實驗作業(yè) ： 設計一個磁盤資源管理系統(tǒng) ， 實現(xiàn) B+樹的查詢 、插入和刪除操作 ， 并生成測試數(shù)據(jù)集 ， 驗證這些操作的正確性 。 JYP 126 動態(tài)散列 （ ） 靜態(tài)散列必須靜態(tài)分配散列表空間。 如果分配的表空間過大，則會浪費空間；如果分配的表空間過小，則會導致沖突頻繁，而且當數(shù)據(jù)量大于散列表的容量時整個散列表需要重組。 動態(tài)散列 又稱為 可擴展散列 ，其目的就是要既保持靜態(tài)散列的快速查找性能，又具備動態(tài)適應數(shù)據(jù)文件大小變化的能力。 假設文件 F是記錄 R的集合。每個記錄有一個關(guān)鍵字 key。記錄存儲在 頁面 （或桶）中，每個頁面的容量是 p個記錄。 JYP 127 在設計算法時，應盡量減少對頁面的訪問次數(shù)，因為頁面通常存儲在磁盤上。 空間利用率 定義為 n/(mp)，其中， n是記錄個數(shù)，m是頁面數(shù)。 JYP 128 帶目錄動態(tài)散列 每個關(guān)鍵字由一個二進制編碼表示 。 給定一個散列表 ht， 關(guān)鍵字 x在 ht中的位置可通過其編碼的 k個最低二進制位確定 。 目錄 實際上是一個散列表 ， 該表的每個目錄項存放一個頁面指針 。 如果用 k個二進制位區(qū)分關(guān)鍵字 ， 則目錄有 2k個目錄項 ， 分別對應下標 0, … , 2k–1。 查找關(guān)鍵字 x時 ， 用與 x的最低 k個二進制位對應的整數(shù)定位目錄項 ， 再搜索該目錄項指向的頁面 。 JYP 129 下面通過一個例子來觀察目錄的動態(tài)擴展過程。 假設關(guān)鍵字由2個字符組成，每個字符由 3個二進制位表示。 右圖是一些關(guān)鍵字及其二進制表示。 JYP 130 假設初始時目錄有 4項。每個頁面可容納 2個記錄。需用關(guān)鍵字的 2個最低位來確定目錄項。 將關(guān)鍵字 A0, B0, C2, A1, B1和 C3加入表中后的結(jié)果如下圖（ a）所示： JYP 131 再將 C5加入表中。由于 C5的 2個最低位是 01，因此應存入頁面 b。但 b已滿，從而發(fā)生溢出。 這時新增加一個頁面 e，同時改用 3個最低位區(qū)分關(guān)鍵字，并使目錄的目錄項數(shù)擴大一倍，如右圖（ b）所示。 JYP 132 觀察圖（ b），雖然整個散列表需要 3個最低二進制位確定關(guān)鍵字所在頁面，但實際上不是所有頁面都需要 3個最低二進制位來確定。 例如頁面 a被 2個目錄項指向，且我們實際只需要2個最低位即可確定其中關(guān)鍵字所在頁面。因為 a中關(guān)鍵字的 2個最低位是 00，在 00前面加上 0或 1得到000或 100，由此對應的 2個目錄項都指向頁面 a。 如果對于一個頁面內(nèi)的關(guān)鍵字，實際只需要 i個最低位即可確定其所在頁面，則稱該頁面的 局部深度 為 i。 在整個散列表中，所有局部深度的最大者稱為 全局深度 。 JYP 133 在圖（ a）中，每個頁面只被 1個目錄項指向，全局深度為 2。 在圖（ b）中，頁面 b和 e分別只被 1個目錄項指向，局部深度為 3；其余頁面都被 2個目錄項指向，局部深度為 2；全局深度為 3。 JYP 134 訪問任何頁面都需要兩個步驟： （ 1）通過散列函數(shù)確定目錄項，并得到頁面地址； （ 2）訪問該頁面。 如果關(guān)鍵字在頁面中的分布不均勻，目錄增長可能過大，而大多數(shù)目錄項都指向同一頁面。 為防止這種情況，不宜直接使用關(guān)鍵字的二進制位序列，而應通過均勻散列函數(shù)將這些二進制位轉(zhuǎn)換為隨機序列。 JYP 135 還需要一個 散列函數(shù)簇 ，因為在整個表動態(tài)變化的不同時刻，需要不同的二進制位個數(shù)來區(qū)分關(guān)鍵字。 以下是一種解決方案： hashi: key ? {0, …, 2 i – 1}， 1≤i≤d 其中， hashi的結(jié)果只是簡單地在 hashi1的結(jié)果前端加上二進制位 0或 1。 因此，散列函數(shù) hash(key, i) 根據(jù)關(guān)鍵字 key生成一個與 i個二進制位對應的隨機數(shù)。 JYP 136 當局部深度為 i的頁面溢出時，分配一個新頁面，并將關(guān)鍵字重新散列到這兩個頁面。 這兩個頁面中的關(guān)鍵字的 i個最低位相同，稱它們?yōu)?伙伴 。 當兩個伙伴頁面中的關(guān)鍵字個數(shù)不大于一個頁面的容量時，就將這兩個頁面 合并 ，釋放多余的頁面，并將結(jié)果頁面的局部深度減少 1。 假設需要向一個局部深度為 i，容量為 p且已經(jīng)包含 p個記錄的頁面加入一個新記錄，則先從操作系統(tǒng)獲得一個新頁面。 JYP 137 利用 i + 1個二進制位將 p + 1個關(guān)鍵字重新散列到這兩個頁面，并將這些頁面的局部深度設置為 i + 1。 如果 i + 1大于全局深度，則整個目錄增長一倍，全局深度加 1。 如果所有 p + 1個關(guān)鍵字被散列到兩頁面之一，則上述分裂過程還須繼續(xù)。 JYP 138 以下程序給出了實現(xiàn)帶目錄的動態(tài)散列的概要性描述： template class Type struct record { // 記錄結(jié)構(gòu) Type key。 // 其它數(shù)據(jù)字段 }。 template class Type struct page { // 頁面結(jié)構(gòu) record names[PageSize]。 // 假設 PageSize是已定義的常數(shù) int NumRecords。 // 本頁面的記錄個數(shù) }。 JYP 139 template class Type struct DirEntry { // 目錄項結(jié)構(gòu) int LocalDepth。 // 該目錄項所指頁面的局部深度 pageType* paddr。 // 注意這是用指針模擬頁面地址 }。 template class Type DirEntry rdirectory[MaxDir]。 // 目錄，假設 MaxDir是已 // 定義的常數(shù) int gdepth。 // 全局深度，要求 1≤gdepth≤KeySize， // 假設 KeySize是已定義的常數(shù) int NumGdepthPage。 // 局部深度達到全局深度的頁面數(shù) JYP 140 template class Type int hash(const Typeamp。 key, const int i)。 // 用均勻散列將 key //轉(zhuǎn)換為二進制位序列，返回與 i個最低位對應 // 的整數(shù)，并作為目錄項下標 int buddy(const int index)。 // 根據(jù)指向一個頁面的目錄項下 // 標 index，返回指向其伙伴頁面的目錄項下標，這可 // 以通過對 index的首個二進制位作取反操作實現(xiàn) template class Type int size(const pageType* p)。 // 返回頁面 p中記錄個數(shù) template class Type void coalesce(const pageType* p, const pageType* buddy)。 // 將頁面 p及其伙伴 buddy的記錄合并到頁面 p，并釋放頁 // 面 buddy JYP 141 template class Type Boolean PageSearch(const Typeamp。 key, const pageType* p)。 // 在頁面 p中查找關(guān)鍵字 key。找到返回 TRUE，否則返回 // FALSE template class Type void enter(const recordamp。 r, const pageType* p)。 // 將新記錄 r //插入頁面 p，并執(zhí)行 p?NumRecords++。 template class Type void PageDelete(const Typeamp。 key, const pageType* p)。 // 從 // 頁面 p中刪除關(guān)鍵字為 key的記錄，并執(zhí)行 p?NumRecords。 JYP 142 template class Type pageType* find(const Typeamp。 key) { // 在整個表中查找關(guān)鍵 // 字為 key的記錄。找到返回該記錄所在頁面的地址， //否則返回 0 int index = hash(key, gdepth)。 pageType* p = rdirectory[index].paddr。 if (PageSearch(key, p) return p。 else return 0。 } template class Type void insert(const recordTypeamp。 r, const Typeamp。 key) { // 將新 // 記錄 r插入整個表中 pageType* p = find(key)。 // 檢查 key是否已存在 if (p) return。 // key已存在 int index = hash(key, gdepth)。 JYP 143 Boolean StillFull = FALSE。 p = rdirector