初識索引

索引的概念

索引是定義在存儲表的基礎(chǔ)上，有助于無需檢查所有記錄而快速定位所需記錄的一種輔助存儲結(jié)構(gòu)，由一系列存儲在磁盤上的索引項組成，每一索引項又由兩部分構(gòu)成。即索引字段和行指針。

索引字段

由表中某些列通常是一列中的值串接而成。索引中通常存儲了索引字段的每一個值。

行指針

指向表中包含索引字段值的記錄在磁盤上的存儲位置。

存儲索引項文件的為索引文件，存儲表稱為主文件。

索引文件組織方式

（相對照的，主文件組織有堆文件，排序文件，散列文件，聚簇文件等多種方式）

排序索引文件：按索引字段值的某一種順序組織存儲

散列索引文件：依據(jù)索引字段值使用散列函數(shù)分配散列桶的方式存儲

索引的作用

在一個表上針對不同屬性或者屬性組合建立不同的索引文件，索引字段值可以是表中任何一個屬性的值或者屬性值的組合；

索引文件比主文件小得多，通過檢索一個小的索引文件（可以完全裝載進內(nèi)存），快速定位之后，再有針對性的讀取非常大的主文件中的相關(guān)記錄；

有索引時，更新操作必須同步更新索引文件和主文件。保持其數(shù)據(jù)一致性。

SQL語言中的索引創(chuàng)建與維護

基礎(chǔ)知識

當(dāng)定義table之后，如果定義了主鍵，系統(tǒng)自動生成主索引；

索引可以由用戶定義或者撤銷；

當(dāng)索引被創(chuàng)建后，不論是主索引還是用戶定義的索引，DBMS都將自動維護所有索引；

當(dāng)table被刪除之后，定義在該表上的所有索引自動撤銷。

創(chuàng)建，撤銷索引

CREATE INDEX idxSname ON Student(Sname)；
DROP INDEX idxSname;

稠密索引與稀疏索引

稠密索引

對于主文件中每一個記錄（形成的每一個索引字段值），都有一個索引項和它相對應(yīng)，指明該記錄所在位置。這樣的索引稱稠密索引。（dense index)

稀疏索引

對于主文件中的部分記錄（形成的索引字段值），有索引項和它對應(yīng)，這樣的索引稱為非稠密索引或者稀疏索引（sparse index)。

稀疏索引如何定位記錄

定位索引字段值為K的記錄，需要

首先找相鄰的小于K的最大索引字段值所對應(yīng)的索引項；從該索引項所對應(yīng)的記錄開始順序進行table的檢索

稀疏索引的使用要求：主文件必須是按照對應(yīng)索引字段屬性排序存儲

相比稠密索引：空間占用更少，維護任務(wù)更輕，但速度更慢

平衡：索引項不指向記錄指針，而是指向記錄所在的存儲塊的指針，即每一存儲塊有一個索引項，而不是每條記錄有一索引項——主索引

稠密索引如何定位記錄

1.候選鍵屬性的稠密索引 一一對應(yīng)即可

2.非候選鍵屬性的稠密索引，主文件按照索引字段值排序，對每一個不重復(fù)的第一個索引字段值建立索引項，相同索引字段值則在附近尋找；

3.非候選鍵屬性的稠密索引，主文件未按照索引字段值排序，不要求索引項中的索引字段唯一，可以重復(fù)出現(xiàn)，以實現(xiàn)對主文件中對應(yīng)索引字段值的指向；

4.非候選鍵屬性的稠密索引，主文件未按照索引字段值排序，若要求索引中索引字段是唯一的，則可以引入一個中間層，指針桶；該指針桶就是第3種情況。

主索引

主索引概念

通常是對每一個存儲塊有一個索引項，索引項的總數(shù)和存儲表所占的存儲塊數(shù)目相同，存儲表的每一存儲塊的第一條記錄，又稱為錨記錄，簡稱塊錨。

主索引的索引字段值為塊錨的索引字段值，而指針指向其所在的存儲塊。

主索引是按索引字段值進行排序的一個有序文件，通常建立在有序主文件的基于主碼的排序字段上，即主索引的索引字段與主文件的排序碼（主碼）有對應(yīng)關(guān)系。

主索引是稀疏索引。

輔助索引

輔助索引定義

是定義在主文件的任一或者多個非排序字段上的輔助存儲結(jié)構(gòu)；通常是對某一非排序字段上的不同值有一個索引項，索引字段即是該字段的不同值，而指針則指向包含該紀錄的塊或者記錄本身；

當(dāng)非排序字段為索引字段時，如該字段值不唯一，則要采用一個類似鏈表的結(jié)構(gòu)來保存該字段值的所有記錄的位置；

輔助索引是稠密索引，檢索速度有時候相當(dāng)高

主索引和輔助索引的區(qū)別和聯(lián)系

一個主文件僅有一個主索引，但可以有多個輔助索引；

主索引通常建立在主碼或者排序碼上；而輔助索引建立在非排序字段上；

可以利用主索引重新組織主文件數(shù)據(jù)，但輔助索引不能改變主文件數(shù)據(jù)；

主索引是稀疏索引，輔助索引是稠密索引。

聚簇索引和非聚簇索引

聚簇索引

是指索引中鄰近的記錄在主文件中也是臨近存儲的；

非聚簇索引

是指索引中鄰近的記錄在主文件中不一定是臨近存儲的

注意：

如果主文件的某一排序字段不是主碼，則該字段上每個記錄取值不唯一，此時該字段稱為聚簇字段；聚簇索引通常是定義在聚簇字段上;聚簇索引通常是對聚簇字段上的每一個不同值有一個索引項（索引項的總數(shù)和主文件中聚簇字段上不同值的數(shù)目相同），索引字段即是聚簇字段的不同值，由于有相同聚簇字段值的記錄可能存儲在若干塊中，則索引項的指針指向其中的第一塊。一個主文件只能有一個聚簇索引文件，但可以有多個非聚簇索引文件。主索引通常是聚簇索引（但其索引項總數(shù)不一定和主文件中聚簇字段上不同值的數(shù)目相同，其和主文件存儲塊數(shù)目相同）；輔助索引通常是非聚簇索引。主索引/聚簇索引是能夠決定記錄存儲位置的索引；而非聚簇索引則只能用于查詢，指出已存儲記錄的位置。

倒排索引

倒排索引是實現(xiàn)“單詞-文檔矩陣”的一種具體存儲形式，通過倒排索引，可以根據(jù)單詞快速獲取包含這個單詞的文檔列表。倒排索引主要由兩個部分組成：“單詞詞典”和“倒排文件”。

單詞詞典(Lexicon)：搜索引擎的通常索引單位是單詞，單詞詞典是由文檔集合中出現(xiàn)過的所有單詞構(gòu)成的字符串集合，單詞詞典內(nèi)每條索引項記載單詞本身的一些信息以及指向“倒排列表”的指針。

倒排列表(PostingList)：倒排列表記載了出現(xiàn)過某個單詞的所有文檔的文檔列表及單詞在該文檔中出現(xiàn)的位置信息，每條記錄稱為一個倒排項(Posting)。根據(jù)倒排列表，即可獲知哪些文檔包含某個單詞。

倒排文件(Inverted File)：所有單詞的倒排列表往往順序地存儲在磁盤的某個文件里，這個文件即被稱之為倒排文件，倒排文件是存儲倒排索引的物理文件。

多級索引

當(dāng)索引項較多時，可以對索引再建立索引，稱為多級索引。

常見的多級索引：B樹/B+樹索引

多屬性索引

索引字段由表的多個屬性值組合在一起形成的索引

散列索引

使用散列技術(shù)組織的索引

網(wǎng)格索引

使用多索引字段進行交叉聯(lián)合定位與檢索

B+樹索引

定義

一種以樹形數(shù)據(jù)結(jié)構(gòu)來組織索引項的多級索引

由于一個存儲塊是可以存儲多個索引項，每個索引項又由指針和索引字段兩部分構(gòu)成。用Ki表示索引字段值，Pi表示指針，指向索引塊或者數(shù)據(jù)塊或者數(shù)據(jù)塊中記錄。

一塊中通?？梢源鎯-1個索引項和1個指針。

B+樹特點

• 能夠自動保持與主文件大小相適應(yīng)的樹的層次
• 每個索引塊的指針利用率都在50%~100%

索引字段值x在Ki-1<=x<Ki的由Pi指向，而Ki<=x<Ki+1的由Pi+1指向。

葉節(jié)點和葉子節(jié)點的指針分別指向什么

非葉結(jié)點指針指向索引塊，葉結(jié)點指針指向主文件的數(shù)據(jù)塊或數(shù)據(jù)記錄

葉結(jié)點的最后一個指針指向下一個數(shù)據(jù)塊

一個索引塊實際使用的索引指針個數(shù)d,滿足（根結(jié)點除外）

n/2<=d<=n

根結(jié)點至少2個指針被使用

B+樹存儲約定

索引字段值重復(fù)出現(xiàn)于葉結(jié)點和非葉結(jié)點

指向主文件的指針僅出現(xiàn)于葉結(jié)點

所有葉結(jié)點即可覆蓋所有鍵值的索引

索引字段值在葉結(jié)點中是按順序排列的

僅葉結(jié)點的集合就是主文件完整的索引

到此這篇關(guān)于數(shù)據(jù)庫索引知識點整理的文章就介紹到這了,更多相關(guān)數(shù)據(jù)庫索引內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論