數據庫索引知識點整理

初識索引

索引的概念

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

索引字段

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

行指針

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

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

索引文件組織方式

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

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

散列索引文件:依據索引字段值使用散列函數分配散列桶的方式存儲

索引的作用

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

索引文件比主文件小得多,通過檢索一個小的索引文件(可以完全裝載進內存),快速定位之後,再有針對性的讀取非常大的主文件中的相關記錄;

有索引時,更新操作必須同步更新索引文件和主文件。保持其數據一致性。

SQL語言中的索引創建與維護

基礎知識

當定義table之後,如果定義瞭主鍵,系統自動生成主索引;

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

當索引被創建後,不論是主索引還是用戶定義的索引,DBMS都將自動維護所有索引;

當table被刪除之後,定義在該表上的所有索引自動撤銷。

創建,撤銷索引

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

稠密索引與稀疏索引

稠密索引

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

稀疏索引

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

稀疏索引如何定位記錄

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

首先找相鄰的小於K的最大索引字段值所對應的索引項;從該索引項所對應的記錄開始順序進行table的檢索

稀疏索引的使用要求:主文件必須是按照對應索引字段屬性排序存儲

相比稠密索引:空間占用更少,維護任務更輕,但速度更慢

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

稠密索引如何定位記錄

1.候選鍵屬性的稠密索引 一一對應即可

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

3.非候選鍵屬性的稠密索引,主文件未按照索引字段值排序,不要求索引項中的索引字段唯一,可以重復出現,以實現對主文件中對應索引字段值的指向;

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

主索引

主索引概念

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

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

主索引是按索引字段值進行排序的一個有序文件,通常建立在有序主文件的基於主碼的排序字段上,即主索引的索引字段與主文件的排序碼(主碼)有對應關系。

主索引是稀疏索引。

輔助索引

輔助索引定義

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

當非排序字段為索引字段時,如該字段值不唯一,則要采用一個類似鏈表的結構來保存該字段值的所有記錄的位置;

輔助索引是稠密索引,檢索速度有時候相當高

主索引和輔助索引的區別和聯系

一個主文件僅有一個主索引,但可以有多個輔助索引;

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

可以利用主索引重新組織主文件數據,但輔助索引不能改變主文件數據;

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

聚簇索引和非聚簇索引

聚簇索引

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

非聚簇索引

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

註意:

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

倒排索引

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

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

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

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

多級索引

當索引項較多時,可以對索引再建立索引,稱為多級索引。

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

多屬性索引

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

散列索引

使用散列技術組織的索引

網格索引

使用多索引字段進行交叉聯合定位與檢索

B+樹索引

定義

一種以樹形數據結構來組織索引項的多級索引

由於一個存儲塊是可以存儲多個索引項,每個索引項又由指針和索引字段兩部分構成。用Ki表示索引字段值,Pi表示指針,指向索引塊或者數據塊或者數據塊中記錄。

一塊中通常可以存儲n-1個索引項和1個指針。

B+樹特點

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

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

葉節點和葉子節點的指針分別指向什麼

非葉結點指針指向索引塊,葉結點指針指向主文件的數據塊或數據記錄

葉結點的最後一個指針指向下一個數據塊

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

n/2<=d<=n

根結點至少2個指針被使用

B+樹存儲約定

索引字段值重復出現於葉結點和非葉結點

指向主文件的指針僅出現於葉結點

所有葉結點即可覆蓋所有鍵值的索引

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

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

到此這篇關於數據庫索引知識點整理的文章就介紹到這瞭,更多相關數據庫索引內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!