數(shù)據(jù)庫索引技術(shù)new

《數(shù)據(jù)庫索引技術(shù)new》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、高級數(shù)據(jù)庫系統(tǒng)及其應用第2部分關(guān)系數(shù)據(jù)庫系統(tǒng)實現(xiàn)第5章數(shù)據(jù)庫索引技術(shù)xshxie@ustc.edu.cnLOGO第5章數(shù)據(jù)庫索引技術(shù)5.1幾種文件組織方式的特性對比分析5.2索引技術(shù)基礎5.3B+樹索引5.4散列索引5.5位圖索引5.6多維空間索引2011年11月2日25.1幾種文件組織方式的特性對比分析5.1.1文件的記錄組織方式5.1.2各種文件組織方式的特性分析2011年11月2日35.1.1文件的記錄組織方式?堆文件(heapfile)?排序文件(sortedfile)?散列文件(hashedfi

2、le)?以記錄的某個屬性值為參數(shù)，通過特定散列函數(shù)求得有限范圍內(nèi)的一個值作為記錄的存儲地址(即頁地址或桶號)。?用于計算散列的屬性也稱為散列鍵，它與搜索鍵具有類似的概念。2011年11月2日45.1.2各種文件組織方式的特性分析??掃描假設文件有(Scan)B個數(shù)據(jù)頁，每頁有R個記錄；平均?等值搜索讀寫1個頁的時間為(EqualitySearch)D，(CPU)處理一個記錄的時間為?取文件中滿足等值選擇條件的所有記錄C。對于散列文件組織，散列函數(shù)映射的?包含滿足條件記錄的所有頁須從磁盤讀到主存。時間為H。

3、?范圍搜索(RangingSearch)?分析時采用如下簡單代價模型：?插入(insert)??必須先定位新記錄應插入的頁，并將該頁讀入主存，I/O操作代價具有主導性。在主存頁中完成插入修改，然后，再將該頁寫回磁盤。?DB緩沖區(qū)大小對DB操作有重要影響。?刪除(delete)?如采用等值或范圍條件選擇刪除記錄，則操作過程與?為了行較全面的性能評價，分析時我們選擇幾種‘插入/范圍搜索’操作類似；具有代表性的典型?如直接給定刪除記錄DBrid操作，則可直接定位到記錄所在頁。：2011年11月2日55.1.2.

4、1堆文件的操作特性分析?掃描－－操作代價為B(D+RC)?等值搜索?假設:滿足條件的記錄只有一個,平均需檢查一半的頁?操作代價取0.5DB?范圍搜索－－必檢查所有的頁，操作代價B(D+RC)?插入?取文件的最后頁到主存，插入后，再寫回磁盤?操作代價為2D+C?刪除?不考慮記錄被刪除后的空間合并?操作代價為：搜索時間＋C+D?若已知rid，可直接定位到目標頁，可省去搜索時間2011年11月2日65.1.2.2排序文件的操作特性分析?掃描－－操作代價為B(D+RC)?等值搜索?假設：滿足條件的記錄只有一個?可

5、用二分法搜索，操作代價取D*logB＋ClogR22?若滿足條件記錄有多個，則該代價還應加上讀取包含所有這些記錄的若干個連續(xù)頁。?范圍搜索－－等值搜索代價＋matches?插入?插入后，需進行排序調(diào)整，假設需調(diào)整約一半的記錄?插入操作的代價=等值搜索代價＋2*0.5B(D+RC)。?刪除?如果等值或范圍刪除條件，則代價與插入操作相同?若已知rid，可直接定位到目標頁，可省去搜索時間2011年11月2日75.1.2.3散列文件的操作特性分析?掃描－－頁空間通常只保持約80%的占用率，掃描的實際操作代價取1.

6、25B(D+RC)?等值搜索?能非常有效支持等值選擇?假設滿足條件的記錄只有一條且相應桶中沒有溢出頁，則等值搜索操作代價僅為H+D+0.5RC?范圍搜索?需要掃描所有的頁，操作代價＝1.25B(D+RC)?插入－－插入操作代價=等值搜索代價＋D+C。?刪除?對等值或范圍選擇刪除，代價=搜索代價＋D+C?如果直接給定rid，則可省去搜索時間，代價=D+C2011年11月2日8各種文件組織方式的特性對比2011年11月2日95.2索引技術(shù)基礎5.2.1索引技術(shù)綜述5.2.2順序索引及其特性5.2.3創(chuàng)建索引語

7、句2011年11月2日105.2.1索引技術(shù)綜述?索引?是一種能幫助我們有效找出滿足指定條件記錄rid的輔助數(shù)據(jù)結(jié)構(gòu)，是一種特殊類型的記錄文件。?索引記錄?常被稱為索引項(indexentry)，簡記為k*?除了索引項按索引鍵值順序組織的順序索引外，也有按樹結(jié)構(gòu)(如B+樹)和桶結(jié)構(gòu)(散列)進行組織的索引。?RDBMS中，索引項可能具有的三種形式?（1）索引項k*是數(shù)據(jù)記錄本身，無單獨的索引文件。?這時數(shù)據(jù)文件可視為一種特殊的數(shù)據(jù)文件組織，即散列文件。?（2），有獨立的索引文件。?（3）

8、rid-list>，有獨立的索引文件，且每個索引項中允許包含多個rid。2011年11月2日115.2.1順序索引及其特性?聚集與非聚集索引?聚集索引(clusteredindex)：指索引項的排序方式和數(shù)據(jù)文件記錄排序方式一致的索引?稠密索引與稀疏索引?稠密索引：每個索引鍵值都對應有一索引項?稀疏索引：只為某些搜索鍵值建立索引項?多級索引?為處理索引項過多帶來的索引性能下降問題，可以將索引文本本身當作一般順序數(shù)據(jù)文件，在其上