索引分為順序索引(ordered indixes)和散列(hash indices)索引，前者基于值的順序；後者将值平均分布到若幹bucket中，值所屬的bucket由散列函數決定。
索引和散列的實作技術有多種，但沒有哪一種是絕對最好的，每種方式有其最适合的場景，可通過這幾個方面來進行評估：通路類型（能有效支援的通路類型，如特定值查找、範圍查找）、通路時間、插入時間、删除時間、空間開銷（索引額外占用的空間）。
一、順序索引
a)為了快速随機通路記錄，可以使用順序索引。用于在檔案中查找記錄的屬性或屬性集稱為搜尋碼(search key)，每個索引結構與一個特定的搜尋碼關聯，并按順序存儲搜尋碼的值，将每個搜尋碼與對應的記錄關聯起來。
被索引的記錄本身也可以按一定的順序存儲，如果記錄按照某個搜尋碼指定的順序排序，則該搜尋碼對應的索引稱為聚集索引(clustering
index)或主索引(primary
index)，聚集索引的搜尋碼一般是主鍵，但不是必須這樣。搜尋碼指定的順序與記錄的實體存儲順序不同的索引稱為非聚集索引(noclustering
index)或輔助索引(secondary index)。
b)稠密索引和稀疏索引
索引項由搜尋碼和指向具有該搜尋碼值的若幹條記錄的指針構成，指針包含block的辨別和辨別磁盤塊内記錄的塊内偏移量。順序索引又分為稠密索引(dense index)和稀疏索引(sparse index)。
稠密索引中，每個搜尋碼都有一個索引項。索引項包含搜尋碼值以及指向具有該搜尋碼值的第一條資料記錄的指針。如果是稠密聚集索引，具有相同搜尋碼值的其餘記錄可以順序地存儲在第一條資料記錄之後；對于非聚集索引，則需要為每條搜尋碼值建立索引。
稀疏索引中，隻為搜尋碼的某些值建立索引項。隻有索引是聚集索引時才可以使用稀疏索引，這樣，即使索引中沒有要查找的搜尋碼，也可以根據索引确定搜尋碼的區間，進而找到要查找的記錄。
c)多級索引
如果記錄數很多，其索引也會變得很大。假定100條索引占用一個4K的block，那麼100,000,000條記錄的索引的體積會高達4G。隻有将全部索引都裝載到記憶體，才能最大化索引的速度，如果計算機記憶體小于4G，那麼索引就無法完全放入記憶體中，即使記憶體夠大，也還要供給其他應用程式使用。
在資料量很大、索引檔案較大時可以使用多級索引，即在原先内層索引的基礎上再建立若幹層外層索引，外層索引與内層索引之間的關系同前面索引與資料檔案的關系一樣。多級索引與樹結構緊密相關，比如用于記憶體索引的二叉樹。
二、索引的更新
在插入、删除資料的時候，對應的索引需要更新；而資料被修改時，其索引項不是直接修改，而是分為“删除就搜尋碼值，插入新搜尋碼值”這兩步執行的，是以索引的更新隻涉及插入和删除。
a)插入
稠密索引
如果插入資料的搜尋碼值在索引中不存在，則直接插入索引。
如果插入的搜尋碼值已經存在且指向多條資料，則在這條索引項下新增指向插入資料的指針。
如果插入的搜尋碼值已經存在但隻指向第一條包含該搜尋碼值的記錄，則僅将插入資料放到具有相同搜尋碼值的其他記錄之後。
稀疏索引
假設稀疏索引為每個塊儲存了一個索引項。如果插入資料時，系統需要新建立一個塊，則在索引中插入針對新塊中第一條記錄的搜尋碼的索引項。如果新插入的資料重新整理了塊中記錄的最小搜尋碼值（按照搜尋碼的順序存儲），這個指向這個塊的索引項需要被更新；其餘情況不需要更新索引。
b)删除
如果待删除的記錄的搜尋碼值是唯一的，則删除對應的索引。
如果待删除記錄的搜尋碼值不唯一，且索引項指向所有具有該搜尋碼值的記錄，則隻删除索引項中指向待删除記錄的指針。
如果待删除記錄的搜尋碼值不唯一、索引項僅指向第一條具有該搜尋碼值的記錄，而且第一條記錄待删除，在删除這條記錄的同時，将索引項指向下一條具有該搜尋碼值的記錄。
如果不存在包含被删除記錄的索引項，則不做任何操作。
如果被删除的記錄是具有該搜尋碼值的唯一記錄，則索引項A指向下一個包含該搜尋碼值的記錄，但如果下一個包含該搜尋碼值的記錄已經有索引項，則删除索引項A。
如果被删除的記錄并非是具有該搜尋碼值的唯一記錄，則索引項指向下一條具有相同搜尋碼值的記錄。
學習資料：Database System Concepts, by Abraham Silberschatz, Henry F.Korth, S.Sudarshan