6.3 索引技術(shù)
6.3.1 基本概念
1、 索引技術(shù):是一種快速文件訪問技術(shù),它將一個(gè)文件的每個(gè)記錄在某個(gè)或某些域(屬性)上的取值與該記錄的物理地址直接聯(lián)系起來,提供了一種根據(jù)記錄域的取值快速訪問文件記錄的機(jī)制;它的關(guān)鍵是建立取值域到記錄的物理地址劉的映射關(guān)系,這種映射關(guān)系叫索引;
2、 索引技術(shù)分類:
(1) 有序索引技術(shù):利用索引文件實(shí)現(xiàn)記錄域(查找碼)取值到記錄物理地址間的映射關(guān)系,索引文件由索引記錄組成,每個(gè)記錄中記載一個(gè)索引項(xiàng),索引項(xiàng)記錄了某個(gè)特定的查找碼值和具有該值的數(shù)據(jù)文件記錄的物理地址;
(2) 散列技術(shù):利用一個(gè)散列函數(shù)實(shí)現(xiàn)記錄域取值到記錄物理地址間的直接映射關(guān)系;
(3) 有序索引:有序索引作為基于索引文件的索引技術(shù),需要考慮兩個(gè)問題:(1)如何組織索引文件中的索引記錄;(2)如何從索引文件出發(fā),訪問數(shù)據(jù)文件中的數(shù)據(jù)記錄;
(A) 當(dāng)需要采用有序索引機(jī)制快速訪問數(shù)據(jù)文件時(shí),首先要為該數(shù)據(jù)文件建立一個(gè)索引文件,它是索引記錄和索引項(xiàng)的集合;
(B) 索引文件建立的方法:首先選定某些記錄域作為查找碼,然后建立數(shù)據(jù)記錄在查找碼上的取值與物理地址間的映射關(guān)系,組成索引項(xiàng)。所有索引項(xiàng)作為索引記錄存儲(chǔ)在索引文件中,索引文件根據(jù)某個(gè)特定的查找碼值的順序組織為順序文件;
(C) 一個(gè)數(shù)據(jù)文件可以有多個(gè)查找碼和索引文件;
6.3.2 有序索引的分類及特點(diǎn)
1、 聚集索引與非聚集索引
(1) 對(duì)數(shù)據(jù)文件和它的一個(gè)特定的索引文件,如果數(shù)據(jù)文件中數(shù)據(jù)記錄的排列順序與索引文件中索引項(xiàng)的排列順序相一致,則該索引文件稱為聚集索引,否則稱為非聚集索引;
(2) 在一個(gè)數(shù)據(jù)文件上除了建立一個(gè)聚集索引外,還可建立多個(gè)非聚集索引;
2、 稠密索引和稀疏索引
如果數(shù)據(jù)文件中的每個(gè)查找碼都在索引文件中都對(duì)應(yīng)一個(gè)索引記錄,稱為稠密索引,如果只一部分對(duì)應(yīng),則稱為稀疏索引;
3、 主索引和輔索引
在數(shù)據(jù)文件包含主碼的屬性集上建立索引稱為主索引,在非主碼屬性上建立的索引稱為輔索引;
4、單層索引和多層索引
(1) 單層索引(線性索引):索引項(xiàng)根據(jù)鍵值在索引文件中順序排列,組織成一維線性結(jié)構(gòu),每個(gè)索引項(xiàng)直接指向數(shù)據(jù)文件中的數(shù)據(jù)記錄;
(2) 當(dāng)數(shù)據(jù)文件很大時(shí),即使采用稀疏索引,建成的索引文件也很大,導(dǎo)致效率低下,為解決該問題,可對(duì)索引文件中的索引項(xiàng)本身再建立一級(jí)稀疏索引,組成2層索引結(jié)構(gòu);進(jìn)一步地,可建立多層樹型索引結(jié)構(gòu)來快速定位;
6.4 散列技術(shù)
6.4.1 散列文件
1、 散列是一種快速查找技術(shù),它利用定義在文件記錄上的查找碼,通過計(jì)算一個(gè)散列函數(shù),以散列函數(shù)值作為記錄的物理地址,實(shí)現(xiàn)對(duì)文件記錄直接快速訪問。
2、 首先指定文件記錄的一個(gè)域作為查找碼(散列域),然后定義一個(gè)查找碼上的函數(shù)(散列函數(shù)),函數(shù)的輸入為查找碼值,輸出為物理地址;
3、 一般使用桶作為基本的存儲(chǔ)單位,一個(gè)桶可存放多個(gè)文件記錄,物理地址可以是記錄所在的桶號(hào),散列函數(shù)的輸出可以是桶號(hào);
6.4.2 散列函數(shù)
1、 散列方法依賴于好的散列函數(shù),它應(yīng)該盡可能均勻地將查找碼分布到各個(gè)桶中,具體要滿足如下兩個(gè)條件:
(1) 地址的分布是均勻的;
(2) 地址的分布是隨機(jī)的;
6.4.3 桶溢出
1、 產(chǎn)生桶溢出的兩個(gè)原因:
(1) 文件初始設(shè)計(jì)時(shí),為文件記錄預(yù)留的存儲(chǔ)空間不足;
(2) 散列函數(shù)的均勻分布性不好;
2、 設(shè)計(jì)散列函數(shù)時(shí),應(yīng)根據(jù)文件大小決定物理空間,一般應(yīng)有20%余量,再設(shè)計(jì)合適的桶數(shù)目和桶大小,盡可能留有一些空閑桶,降低桶溢出的可能性;
3、 桶溢出的現(xiàn)象是難免的,需要DBS采用相應(yīng)的桶溢出處理機(jī)制;
4、 散列方法的缺點(diǎn):為了避免桶溢出。必須選一合適的散列函數(shù),但這比較復(fù)雜,而且不象索引文件那樣可以據(jù)數(shù)據(jù)記錄變化動(dòng)態(tài)調(diào)整。
北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |