為了快速隨機存取文件中的記錄，可以使用索引結構。不管是從字面意思來講，還是從生活的其他領域來講，索引都可以被解釋為快速定位。

一.聚集索引和非聚集索引

    1.聚集索引：包含記錄的文件按照某個搜索碼指定的順序排序，那該搜索碼對應的索引稱為聚集索引；也稱為主索引；

    2.非聚集索引：搜索碼指定的順序與文件中記錄的物理順序不同的索引；也稱為輔助索引；

這里“索引”是個抽象的概念，或者說是一個狀態概念，而不是具體的某個索引文件；在某個搜索碼上建立了索引，我們就說某個屬性有索引。所以說，記錄文件和索引文件是不同的概念，下面我們來說明

二.索引記錄和索引順序文件

    1.索引記錄（索引項）是由一個搜索碼值和指向具有該搜索碼值得一個或多個記錄的指針構成，是在某個搜索碼上建立了索引之后生成的；

這里的指針指向的是磁盤空間（磁盤塊的標識，標識磁盤塊內內記錄的塊內偏移量）；

    2.索引順序文件是指在某個搜索碼上有聚集索引的文件；

所以可以說，索引記錄是在記錄文件（簡單理解為一個表）的某個屬性上建立了索引而生成的；

三.順序索引的分類

    1.稠密索引：文件中每個搜索碼值都有一個索引記錄；

    2.稀疏索引：相對于稠密索引，稀疏索引只為某些搜索碼值建立索引記錄；在搜索時，找到其最大的搜索碼值小于或等于所查找記錄的搜索碼值的索引項，然后從該記錄開始向后順序查詢直到找到為止。

分情況看利弊，如果記錄量適中，用稠密索引可以獲得較好的響應時間；

如果記錄量很多，百萬級的，用稠密索引，索引（文件）本身就很難以去維護，因為搜索索引時的跨磁盤塊數就至關重要（因為處理數據庫請求的主要時間開銷就是把塊從磁盤讀到主存的時間），而索引在磁盤上以順序文件存儲，對數量很多的索引記錄的查詢就會涉及到多個塊，這是我們不希望的。但是對每個塊建立稀疏索引已經是公認的利遠遠大于弊的做法。

對于上述龐大稠密索引的解決辦法之一就是建立多級索引，于是就引出了B+樹索引的理念。兩個概念很像，但是也有不同；

四.B+樹索引

索引順序文件組織最大的缺點就在于，隨著文件的增大，索引查找性能和數據掃描性能都會下降。

B+樹索引結構是使用最為廣泛的，在數據插入和刪除的情況下仍能保持執行效率的幾種索引結構之一。

B+樹索引中的B就是Balance，顧名思義，平衡樹，是B樹的一種變形；

B+樹索引雖然在有數據插入和刪除時效率不高，但是，用自己的話來說，就是B+樹能做到一步到位，一勞永逸，加上其在查找上的高效，所以才能受到追捧。

上圖是一個B+樹示意圖，葉子節點直接存儲記錄，在搜索時按照稀疏索引的搜索方法，找到大于最小（相當于小于等于）的那個節點，一級一級往下搜索。

關于B+樹的增刪導致的節點變動這里不再說了，具體內容可參照數據結構。

五.散列索引

　　順序文件組織的一個缺點是我們必須訪問索引結構來定位數據，或者使用二分搜索，導致過多的I/O，基于散列的文件組織使我們能夠避免訪問索引結構，直接定位數據。

      散列技術大體上是依賴散列函數，把搜索碼值直接映射到磁盤（桶）上的一系列操作；這是一種文件系統中的文件組織和管理技術。

      桶（bucket）表示能存儲一條或多條記錄的一個存儲單位；通常一個桶就是一個磁盤塊。

      散列函數應該具有的性質：

      1.使搜索碼分布均勻；

      2.使搜索碼隨機分布；即在一般情況下，每個桶分配到的搜索碼不應該與搜索碼值之外的任何可見排序相關，并且分配到每個桶的搜索碼數目應該幾乎相同。

例如，如果我們把某些商標或名字的首字母映射到對應的26個桶中，這個映射就不符合上述性質，因為很多人傾向于取前幾個字母作為名字的首字母，這樣就導致數據的分布不均；

一.靜態散列

    這種散列技術在數據庫設計初期就確定了散列函數和桶的數量；這就是所謂的靜態；

    一個緊臨的問題就是，如果在數據庫壯大的過程中桶或桶內空間不夠用了怎么辦？這就是牽扯到桶溢出處理，桶溢出的發生可能有一下幾個原因；

    1.桶不足：桶的數目小于記錄總數/一個桶能存放的記錄數；

    2.偏斜：某些桶分配到的記錄比其他桶多，所以即使其他同仍有空間，某個通仍可能是溢出的。

為了減少第一種可能，一般多取20%的桶。至于第二種可能，我們用溢出桶解決。溢出桶就是在已滿的桶后面鏈接一個新的桶，從而把這個鏈上的所有桶看成是一個桶，在插入數據時向后順延。

     靜態散列索引將搜索碼及其相應的指針組織成散列文件結構；具體的做法是，將散列函數作用于搜索碼以確定對應的桶，然后將此搜索碼以及相應的指針存入此桶中。

     一般，使用散列索引來表示散列文件結構。所以，是一種文件結構。

二.動態散列

    這是一種從構建開始就與靜態散列不同的散列技術。

    首先來看靜態散列存在的一個嚴重問題就是要固定桶地址集合，但是大多數數據庫是隨時間變大的，而三種解決方案也不盡人意：1.根據初始文件大小選擇散列函數——未來的性能下降；2.根據預計文件大小選擇散列函數——前期的空間浪費；3.周期性重組——重組期間數據庫幾乎不可用；

    動態散列即允許散列函數動態改變，以適應數據庫的增大或縮小。可擴展散列是其中一種：