數據庫的索引方式

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

索引的好處：

• 在查詢中提高程序的性能。
• 通過創建唯一性索引，可以保證數據庫表中每一行數據的唯一性。
• 在使用分組和排序子句進行數據檢索時，可以減少查詢中分組和排序的時間。

索引的壞處：

• 創建索引和維護索引耗費資源和時間，且隨數據量的增大而增大。
• 索引需要占用物理空間，如果要建立聚簇索引，所需要的空間會更大。
• 在對表中的數據進行刪除和修改時需要耗費較多的時間，因為索引也要動態的維護。

數據庫中有兩種基本的索引類型：

1. 順序索引：索引中的記錄基于搜索碼值順序排序，包括索引順序文件和 B+ 樹索引文件等。
2. 散列索引：索引中的記錄基于搜索碼值的散列函數的值平均地，隨機地分布在若干個散列桶中。

順序索引

1. 索引順序文件

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

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

在順序文件組織的基礎上，索引順序文件分為兩種：稠密索引和稀疏索引。

1. 稠密索引：對應索引文件中搜索碼的每一個值在索引中都有一個索引記錄。每一個索引項包含搜索碼值和指向既有該搜索碼值的第一個數據記錄（或文件塊）的指針，因為在順序文件組織基礎上，所以知道第一個，下一個也會是相同的。
2. 稀疏索引：只為文件中搜索碼的某些值建立索引記錄。每一個索引項包含搜索碼值和指向具有該搜索碼值的第一個數據記錄的指針。

2. 多級索引文件

即使采用稀疏索引，對于一個大型數據庫而言，索引本身也可能變得很大。

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

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

3. 輔助索引

輔助索引是相對于聚集索引而言的，也叫非聚集索引。輔助索引的行存儲的不是對應記錄的全部信息，而是指向對應記錄的指針。

所以，輔助索引必須是稠密索引，即對于每個搜索碼值都必須有一個索引項，而且該索引項要存放指向數據文件中具有該搜索碼值得所有記錄的指針。

4. B+ 樹索引

索引順文件組織的最大不足在于：隨著文件的增大，索引查找的性能和數據順序掃描的性能會下降。雖然這種性能下降可以通過對文件進行重組來彌補，但頻繁地進行重組也是要避免的。

B+ 樹的特點：

1. 根節點至少有兩個子女。
2. 每個中間節點有 [n/2] 到 n 個孩子節點，n 對特定的樹是固定的。
3. 采用平衡樹結構，每個葉節點到根節點的路徑長度相同。
4. 每個節點中的元素從小到大排列，節點中 k-1 個搜索碼值恰好是 k 個子節點域的劃分。（即有 k-1 個值，k 個子節點）

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

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

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

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

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

散列索引

1. 散列文件組織

在散列的描述中，用散列桶來表示可以存放存儲一條或多條記錄的一個存儲單位，通常一個桶就是一個磁盤塊。通過散列函數計算搜索碼值的散列值，并根據散列值來決定包含該搜索碼值的記錄該存儲在哪個桶中。

散列文件的操作有：

1. 查找：設帶查找記錄的搜索碼值為 Ki，通過計算 h(Ki) 獲取存儲該記錄的桶地址，然后到相應的桶中搜尋此記錄，如果桶中沒有找到，且存在溢出桶，還需要繼續到溢出桶中尋找。
2. 插入：插入一條搜索碼值為 Ki 的記錄，通過計算 h(Ki) 獲得存儲該記錄的桶地址，然后就將該記錄存入相應的桶（或溢出桶）中。
3. 刪除：待刪除記錄的搜索碼值為 Ki，通過計算 h(Ki) 獲得存儲該記錄的桶地址，然后到相應的桶（或溢出桶）中搜尋此記錄并刪除它。

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

閉散列：溢出鏈的散列結構。

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

• 使用下一個未滿的桶，該策略稱為線性探查法；
• 用進一步計算散列函數的方法。

2. 散列索引

散列索引將搜索碼值及其相應的文件記錄（或文件塊）指針組織成一個散列索引項。散列索引的構建方法：

1. 將散列函數作用于一條文件記錄的搜索碼值，以確定該文件記錄所對應的散列索引項的散列桶。
2. 將由該搜索碼值以及相應文件記錄（或文件塊）指針組成的散列索引項存入散列桶（或溢出桶）中。

散列索引只能是一種輔助索引結構。

1. 散列是非聚簇索引，故只能做輔助索引。
2. 散列是稠密索引，如果其是聚簇索引的話，那么就成為了主索引了。

散列索引特點：散列其實就是一種不通過值的比較，而通過值的含義來確定存儲位置的方法，他是為有效地實現等值查詢而設計的。不幸的是，基于散列技術不支持范圍檢索，而基于 B+ 樹的索引技術能有效地支持范圍檢索。但是，散列技術在等值連接等操作是很有用的，尤其是在索引嵌套循環連接方法中。