2013計算機等考四級數(shù)據(jù)庫技術(shù)復(fù)習(xí)筆記(6)

　　6.3 索引技術(shù)

　　6.3.1 基本概念

　　1、 索引技術(shù)：是一種快速文件訪問技術(shù)，它將一個文件的每個記錄在某個或某些域(屬性)上的取值與該記錄的物理地址直接聯(lián)系起來，提供了一種根據(jù)記錄域的取值快速訪問文件記錄的機制;它的關(guān)鍵是建立取值域到記錄的物理地址劉的映射關(guān)系，這種映射關(guān)系叫索引;

　　2、 索引技術(shù)分類：

　　(1) 有序索引技術(shù)：利用索引文件實現(xiàn)記錄域(查找碼)取值到記錄物理地址間的映射關(guān)系，索引文件由索引記錄組成，每個記錄中記載一個索引項，索引項記錄了某個特定的查找碼值和具有該值的數(shù)據(jù)文件記錄的物理地址;

　　(2) 散列技術(shù)：利用一個散列函數(shù)實現(xiàn)記錄域取值到記錄物理地址間的直接映射關(guān)系;

　　(3) 有序索引：有序索引作為基于索引文件的索引技術(shù)，需要考慮兩個問題：(1)如何組織索引文件中的索引記錄;(2)如何從索引文件出發(fā)，訪問數(shù)據(jù)文件中的數(shù)據(jù)記錄;

　　(A) 當(dāng)需要采用有序索引機制快速訪問數(shù)據(jù)文件時，首先要為該數(shù)據(jù)文件建立一個索引文件，它是索引記錄和索引項的集合;

　　(B) 索引文件建立的方法：首先選定某些記錄域作為查找碼，然后建立數(shù)據(jù)記錄在查找碼上的取值與物理地址間的映射關(guān)系，組成索引項。所有索引項作為索引記錄存儲在索引文件中，索引文件根據(jù)某個特定的查找碼值的順序組織為順序文件;

　　(C) 一個數(shù)據(jù)文件可以有多個查找碼和索引文件;

　　6.3.2 有序索引的分類及特點

　　1、 聚集索引與非聚集索引

　　(1) 對數(shù)據(jù)文件和它的一個特定的索引文件，如果數(shù)據(jù)文件中數(shù)據(jù)記錄的排列順序與索引文件中索引項的排列順序相一致，則該索引文件稱為聚集索引，否則稱為非聚集索引;

　　(2) 在一個數(shù)據(jù)文件上除了建立一個聚集索引外，還可建立多個非聚集索引;

　　2、 稠密索引和稀疏索引

　　如果數(shù)據(jù)文件中的每個查找碼都在索引文件中都對應(yīng)一個索引記錄，稱為稠密索引，如果只一部分對應(yīng)，則稱為稀疏索引;

　　3、 主索引和輔索引

　　在數(shù)據(jù)文件包含主碼的屬性集上建立索引稱為主索引，在非主碼屬性上建立的索引稱為輔索引;

　　4、單層索引和多層索引

　　(1) 單層索引(線性索引)：索引項根據(jù)鍵值在索引文件中順序排列，組織成一維線性結(jié)構(gòu)，每個索引項直接指向數(shù)據(jù)文件中的數(shù)據(jù)記錄;

　　(2) 當(dāng)數(shù)據(jù)文件很大時，即使采用稀疏索引，建成的索引文件也很大，導(dǎo)致效率低下，為解決該問題，可對索引文件中的索引項本身再建立一級稀疏索引，組成2層索引結(jié)構(gòu);進一步地，可建立多層樹型索引結(jié)構(gòu)來快速定位;

　　6.4 散列技術(shù)

　　6.4.1 散列文件

　　1、 散列是一種快速查找技術(shù)，它利用定義在文件記錄上的查找碼，通過計算一個散列函數(shù)，以散列函數(shù)值作為記錄的物理地址，實現(xiàn)對文件記錄直接快速訪問。

　　2、 首先指定文件記錄的一個域作為查找碼(散列域)，然后定義一個查找碼上的函數(shù)(散列函數(shù))，函數(shù)的輸入為查找碼值，輸出為物理地址;

　　3、 一般使用桶作為基本的存儲單位，一個桶可存放多個文件記錄，物理地址可以是記錄所在的桶號，散列函數(shù)的輸出可以是桶號;

　　6.4.2 散列函數(shù)

　　1、 散列方法依賴于好的散列函數(shù)，它應(yīng)該盡可能均勻地將查找碼分布到各個桶中，具體要滿足如下兩個條件：

　　(1) 地址的分布是均勻的;

　　(2) 地址的分布是隨機的;

　　6.4.3 桶溢出

　　1、 產(chǎn)生桶溢出的兩個原因：

　　(1) 文件初始設(shè)計時，為文件記錄預(yù)留的存儲空間不足;

　　(2) 散列函數(shù)的均勻分布性不好;

　　2、 設(shè)計散列函數(shù)時，應(yīng)根據(jù)文件大小決定物理空間，一般應(yīng)有20%余量，再設(shè)計合適的桶數(shù)目和桶大小，盡可能留有一些空閑桶，降低桶溢出的可能性;

　　3、 桶溢出的現(xiàn)象是難免的，需要DBS采用相應(yīng)的桶溢出處理機制;

　　4、 散列方法的缺點：為了避免桶溢出。必須選一合適的散列函數(shù)，但這比較復(fù)雜，而且不象索引文件那樣可以據(jù)數(shù)據(jù)記錄變化動態(tài)調(diào)整。