初識(shí)索引

索引的概念

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

索引字段

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

行指針

指向表中包含索引字段值的記錄在磁盤(pán)上的存儲(chǔ)位置。

存儲(chǔ)索引項(xiàng)文件的為索引文件，存儲(chǔ)表稱(chēng)為主文件。

索引文件組織方式

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

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

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

索引的作用

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

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

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

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

基礎(chǔ)知識(shí)

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

索引可以由用戶(hù)定義或者撤銷(xiāo)；

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

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

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

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

稠密索引與稀疏索引

稠密索引

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

稀疏索引

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

稀疏索引如何定位記錄

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

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

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

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

平衡：索引項(xiàng)不指向記錄指針，而是指向記錄所在的存儲(chǔ)塊的指針，即每一存儲(chǔ)塊有一個(gè)索引項(xiàng)，而不是每條記錄有一索引項(xiàng)——主索引

稠密索引如何定位記錄

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

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

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

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

主索引

主索引概念

通常是對(duì)每一個(gè)存儲(chǔ)塊有一個(gè)索引項(xiàng)，索引項(xiàng)的總數(shù)和存儲(chǔ)表所占的存儲(chǔ)塊數(shù)目相同，存儲(chǔ)表的每一存儲(chǔ)塊的第一條記錄，又稱(chēng)為錨記錄，簡(jiǎn)稱(chēng)塊錨。

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

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

主索引是稀疏索引。

輔助索引

輔助索引定義

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

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

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

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

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

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

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

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

聚簇索引和非聚簇索引

聚簇索引

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

非聚簇索引

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

注意：

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

倒排索引

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

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

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

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

多級(jí)索引

當(dāng)索引項(xiàng)較多時(shí)，可以對(duì)索引再建立索引，稱(chēng)為多級(jí)索引。

常見(jiàn)的多級(jí)索引：B樹(shù)/B+樹(shù)索引

多屬性索引

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

散列索引

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

網(wǎng)格索引

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

B+樹(shù)索引

定義

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

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

一塊中通?？梢源鎯?chǔ)n-1個(gè)索引項(xiàng)和1個(gè)指針。

B+樹(shù)特點(diǎn)

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

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

葉節(jié)點(diǎn)和葉子節(jié)點(diǎn)的指針?lè)謩e指向什么

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

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

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

n/2=d=n

根結(jié)點(diǎn)至少2個(gè)指針被使用

B+樹(shù)存儲(chǔ)約定

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

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

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

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

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

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