第五章索引技術(shù)(已修改)
2025-10-09 13:39 本頁面
【正文】 第五章 索引技術(shù) DBMS回答用戶查詢時的檢索操作包括三個要素： 輸入 ：用戶要求（如關(guān)鍵字） 搜索 ：尋找，檢查（匹配關(guān)鍵字），定位。 輸出 ：用戶所需信息。 搜索的效率依賴于被搜索空間的大小和 被搜索對象的組織結(jié)構(gòu)。 搜索的效率 索引的基本思想是以搜索較小的排序集 {（關(guān)鍵字，記錄地址） } 去代替搜索較大的主數(shù)據(jù)集合。從而提高了檢索效率。 散列 (Hash) 通過把關(guān)鍵碼值映射到表中的某個位置來訪問記錄的過程稱為散列。大多數(shù)散列方法根據(jù)計算出的地址來放置記錄，而不需根據(jù)關(guān)鍵碼值的順序來放置。 解決沖突的技術(shù)可以分為兩類：開散列方法（也稱為拉鏈法）和閉散列方法（也稱為開地址方法）。這兩種方法的不同之處在與將沖突記錄是存儲在表外（開散列）還是存儲在表內(nèi)另一個槽內(nèi)（閉散列）。 有 7個數(shù)的開散列方法 無序索引 索引映射 : {關(guān)鍵字 }{記錄號 }。 索引文件本身不排序。平均搜索次數(shù)為關(guān)鍵字總數(shù) /2, 主文件都是排序的。那么，隔 N項抽出一項而建立起來的。索引集合就縮小到原來文件的 1/N。其定位誤差小于 N。然后在N個項中線性搜索。 稀索引 線性索引 線性索引是一個按關(guān)鍵碼 /指針順序組織的索引文件。這個文件按照關(guān)鍵碼的順序進行排序。指針指向磁盤中完整記錄的位置。 倒排表 考慮一個有關(guān)職工記錄的大型數(shù)據(jù)庫。如果主關(guān)鍵碼是職工的標(biāo)識號，次關(guān)鍵碼是職工的名字，那么名字索引中的每一條記錄都把名字與一個或多個標(biāo)識號關(guān)聯(lián)起來。這樣組織起來的次關(guān)鍵碼索引稱為倒排表或稱為倒排文件。它把檢索反過來進行，從次關(guān)鍵碼到主關(guān)鍵碼，再到實際數(shù)據(jù)記錄。它也被稱為一個表，因為每個次關(guān)鍵 一個倒排表的結(jié)構(gòu) B樹 一棵 m階的 B樹，或為空樹，或為滿足下列特性的 m叉樹： 1）樹中每個節(jié)點至多有 m棵子樹； 2）若根節(jié)點不是葉子節(jié)點，則至少有兩棵子樹； 3）除根之外的所有非葉子節(jié)點至少有 [m/2]棵子樹； 4）所有的非葉子節(jié)點中包含下列信息 (n, A0, K1, A1, K2, A2,..., Kn, An) 其中： Ki(i=1,...,n)為關(guān)鍵字，且 KiKi+1(i=1,...,n1)。 Ai(i=0,...,n)為指向子樹根節(jié)點的指針，且指針 Ai1所指子樹中所有節(jié)點的關(guān)鍵字均小于 Ki(i=1,...,n), An所指子樹中所有節(jié)點的關(guān)鍵字均大于 Kn, n([m/2] – 1 = m 1)為
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1