資料庫的索引方式

資料庫的索引方式

由於許多查詢只涉及檔案中的少量記錄，故我們需要能直接定位滿足查詢條件的功能。

索引的好處：

在查詢中提高程式的效能。

透過建立唯一性索引，可以保證資料庫表中每一行資料的唯一性。

在使用分組和排序子句進行資料檢索時，可以減少查詢中分組和排序的時間。

索引的壞處：

建立索引和維護索引耗費資源和時間，且隨資料量的增大而增大。

索引需要佔用物理空間，如果要建立聚簇索引，所需要的空間會更大。

在對錶中的資料進行刪除和修改時需要耗費較多的時間，因為索引也要動態的維護。

資料庫中有兩種基本的索引型別：

順序索引：索引中的記錄基於搜尋碼值順序排序，包括索引順序檔案和 B+ 樹索引檔案等。

雜湊索引：索引中的記錄基於搜尋碼值的雜湊函式的值平均地，隨機地分佈在若干個雜湊桶中。

順序索引

1。 索引順序檔案

基本上克服了邊長記錄的順序檔案不能隨機訪問，以及不便於記錄到的增加或刪除。

記錄仍然以關鍵字的順序組織起來。引入了檔案索引表，透過該表可以實現對索引順序檔案的隨機訪問。

在順序檔案組織的基礎上

，索引順序檔案分為兩種：稠密索引和稀疏索引。

稠密索引：對應索引檔案中搜索碼的每一個值在索引中都有一個索引記錄。每一個索引項包含搜尋碼值和指向既有該搜尋碼值的第一個資料記錄（或檔案塊）的指標，

因為在順序檔案組織基礎上，所以知道第一個，下一個也會是相同的

。

稀疏索引：只為檔案中搜索碼的某些值建立索引記錄。每一個索引項包含搜尋碼值和指向具有該搜尋碼值的第一個資料記錄的指標。

2。 多級索引檔案

即使採用稀疏索引，對於一個大型資料庫而言，索引本身也可能變得很大。

如果索引過大，主存中不能讀入所有的索引塊，這樣的查詢處理過程中，搜尋索引就必須讀大量的索引塊。當然在索引上可以用二分法來定位索引塊，但遺憾的是二分法不能處理有移除塊的情況。

所謂多級索引就是在索引之上再建立稀疏索引，像對待其他順序檔案那樣對待順序索引。

3。 輔助索引

輔助索引是相對於聚集索引而言的，也叫非聚集索引。輔助索引的行儲存的不是對應記錄的全部資訊，而是指向對應記錄的指標。

所以，輔助索引必須是稠密索引，即對於每個搜尋碼值都必須有一個索引項，而且該索引項要存放指向資料檔案中具有該搜尋碼值得所有記錄的指標。

4。 B+ 樹索引

索引順檔案組織的最大不足在於：隨著檔案的增大，索引查詢的效能和資料順序掃描的效能會下降。雖然這種效能下降可以透過對檔案進行重組來彌補，但頻繁地進行重組也是要避免的。

B+ 樹的特點：

根節點至少有兩個子女。

每個中間節點有 ［n/2］ 到 n 個孩子節點，n 對特定的樹是固定的。

採用平衡樹結構，每個葉節點到根節點的路徑長度相同。

每個節點中的元素從小到大排列，節點中 k-1 個搜尋碼值恰好是 k 個子節點域的劃分。（即有 k-1 個值，k 個子節點）

Mysql 不同搜尋引擎的 B+ 樹處理

MYISAM：按列值和行號來組織索引，它的葉子節點中儲存的實踐上是指向存放資料的物理課的指標。（即使用輔助索引）

InnoDB：按聚簇索引的形式儲存資料，每個葉子節點除了包含整行記錄，還包含事務 ID，回滾指標等。

聚簇索引：聚簇索引就是按照每張表的主鍵構造一顆B+樹，同時葉子節點中存放的就是整張表的行記錄資料，也將聚集索引的葉子節點稱為資料頁。這個特性決定了索引組織表中資料也是索引的一部分，每張表只能擁有一個聚簇索引。

優點：B+ 樹的資訊全部存放在葉子節點中，非葉子節點用來做索引，且葉子節點中有一個指標指向下一個葉子節點，這樣做的目的是為了提高區間訪問的效能。而正是這個特性決定了 B+ 樹更適合用來儲存外部資料。

雜湊索引

1。 雜湊檔案組織

在雜湊的描述中，用雜湊桶來表示可以存放儲存一條或多條記錄的一個儲存單位，通常一個桶就是一個磁碟塊。透過雜湊函式計算搜尋碼值的雜湊值，並根據雜湊值來決定包含該搜尋碼值的記錄該儲存在哪個桶中。

雜湊檔案的操作有：

查詢：設帶查詢記錄的搜尋碼值為 Ki，透過計算 h（Ki） 獲取儲存該記錄的桶地址，然後到相應的桶中搜尋此記錄，如果桶中沒有找到，且存在溢位桶，還需要繼續到溢位桶中尋找。

插入：插入一條搜尋碼值為 Ki 的記錄，透過計算 h（Ki） 獲得儲存該記錄的桶地址，然後就將該記錄存入相應的桶（或溢位桶）中。

刪除：待刪除記錄的搜尋碼值為 Ki，透過計算 h（Ki） 獲得儲存該記錄的桶地址，然後到相應的桶（或溢位桶）中搜尋此記錄並刪除它。

溢位桶：如果一條記錄必須插入桶 b 中，而桶 b 已滿，系統會為桶 b 提供一個溢位桶，並將此記錄插入到這溢位桶中。所有溢位桶用一個連線連結串列連線在一起，形成溢位鏈。

閉雜湊：溢位鏈的雜湊結構。

開雜湊：另一種接近溢位的方式，它的桶的數量是固定的，當一個桶滿了，系統將記錄插入到其他桶去，選擇其他同的策略有：

使用下一個未滿的桶，該策略稱為線性探查法；

用進一步計算雜湊函式的方法。

2。 雜湊索引

雜湊索引將搜尋碼值及其相應的檔案記錄（或檔案塊）指標組織成一個雜湊索引項。雜湊索引的構建方法：

將雜湊函式作用於一條檔案記錄的搜尋碼值，以確定該檔案記錄所對應的雜湊索引項的雜湊桶。

將由該搜尋碼值以及相應檔案記錄（或檔案塊）指標組成的雜湊索引項存入雜湊桶（或溢位桶）中。

雜湊索引只能是一種輔助索引結構。

雜湊是非聚簇索引，故只能做輔助索引。

雜湊是稠密索引，如果其是聚簇索引的話，那麼就成為了主索引了。

雜湊索引特點：雜湊其實就是一種不透過值的比較，而透過值的含義來確定儲存位置的方法，他是為有效地實現等值查詢而設計的。不幸的是，基於雜湊技術不支援範圍檢索，而基於 B+ 樹的索引技術能有效地支援範圍檢索。但是，雜湊技術在等值連線等操作是很有用的，尤其是在索引巢狀迴圈連線方法中。