索引分為順序索引(ordered indixes)和散列(hash indices)索引，前者基于值的順序；后者將值平均分布到若干bucket中，值所屬的bucket由散列函數(shù)決定。
索引和散列的實現(xiàn)技術(shù)有多種，但沒有哪一種是絕對最好的，每種方式有其最適合的場景，可通過這幾個方面來進(jìn)行評估：訪問類型（能有效支持的訪問類型，如特定值查找、范圍查找）、訪問時間、插入時間、刪除時間、空間開銷（索引額外占用的空間）。
一、順序索引
a)為了快速隨機(jī)訪問記錄，可以使用順序索引。用于在文件中查找記錄的屬性或?qū)傩约Q為搜索碼(search key)，每個索引結(jié)構(gòu)與一個特定的搜索碼關(guān)聯(lián)，并按順序存儲搜索碼的值，將每個搜索碼與對應(yīng)的記錄關(guān)聯(lián)起來。
被索引的記錄本身也可以按一定的順序存儲，如果記錄按照某個搜索碼指定的順序排序，則該搜索碼對應(yīng)的索引稱為聚集索引(clustering index)或主索引(primary index)，聚集索引的搜索碼一般是主鍵，但不是必須這樣。搜索碼指定的順序與記錄的物理存儲順序不同的索引稱為非聚集索引(noclustering index)或輔助索引(secondary index)。
b)稠密索引和稀疏索引
索引項由搜索碼和指向具有該搜索碼值的若干條記錄的指針構(gòu)成，指針包含block的標(biāo)識和標(biāo)識磁盤塊內(nèi)記錄的塊內(nèi)偏移量。順序索引又分為稠密索引(dense index)和稀疏索引(sparse index)。
稠密索引中，每個搜索碼都有一個索引項。索引項包含搜索碼值以及指向具有該搜索碼值的第一條數(shù)據(jù)記錄的指針。如果是稠密聚集索引，具有相同搜索碼值的其余記錄可以順序地存儲在第一條數(shù)據(jù)記錄之后；對于非聚集索引，則需要為每條搜索碼值建立索引。
稀疏索引中，只為搜索碼的某些值建立索引項。只有索引是聚集索引時才可以使用稀疏索引，這樣，即使索引中沒有要查找的搜索碼，也可以根據(jù)索引確定搜索碼的區(qū)間，進(jìn)而找到要查找的記錄。
c)多級索引
如果記錄數(shù)很多，其索引也會變得很大。假定100條索引占用一個4K的block，那么100,000,000條記錄的索引的體積會高達(dá)4G。只有將全部索引都裝載到內(nèi)存，才能最大化索引的速度，如果計算機(jī)內(nèi)存小于4G，那么索引就無法完全放入內(nèi)存中，即使內(nèi)存夠大，也還要供給其他應(yīng)用程序使用。
在數(shù)據(jù)量很大、索引文件較大時可以使用多級索引，即在原先內(nèi)層索引的基礎(chǔ)上再建立若干層外層索引，外層索引與內(nèi)層索引之間的關(guān)系同前面索引與數(shù)據(jù)文件的關(guān)系一樣。多級索引與樹結(jié)構(gòu)緊密相關(guān)，比如用于內(nèi)存索引的二叉樹。
二、索引的更新
在插入、刪除數(shù)據(jù)的時候，對應(yīng)的索引需要更新；而數(shù)據(jù)被修改時，其索引項不是直接修改，而是分為“刪除就搜索碼值，插入新搜索碼值”這兩步執(zhí)行的，所以索引的更新只涉及插入和刪除。
a)插入
稠密索引
如果插入數(shù)據(jù)的搜索碼值在索引中不存在，則直接插入索引。
如果插入的搜索碼值已經(jīng)存在且指向多條數(shù)據(jù)，則在這條索引項下新增指向插入數(shù)據(jù)的指針。
如果插入的搜索碼值已經(jīng)存在但只指向第一條包含該搜索碼值的記錄，則僅將插入數(shù)據(jù)放到具有相同搜索碼值的其他記錄之后。
稀疏索引
假設(shè)稀疏索引為每個塊保存了一個索引項。如果插入數(shù)據(jù)時，系統(tǒng)需要新創(chuàng)建一個塊，則在索引中插入針對新塊中第一條記錄的搜索碼的索引項。如果新插入的數(shù)據(jù)刷新了塊中記錄的最小搜索碼值（按照搜索碼的順序存儲），這個指向這個塊的索引項需要被更新；其余情況不需要更新索引。
b)刪除
稠密索引
如果待刪除的記錄的搜索碼值是唯一的，則刪除對應(yīng)的索引。
如果待刪除記錄的搜索碼值不唯一，且索引項指向所有具有該搜索碼值的記錄，則只刪除索引項中指向待刪除記錄的指針。
如果待刪除記錄的搜索碼值不唯一、索引項僅指向第一條具有該搜索碼值的記錄，而且第一條記錄待刪除，在刪除這條記錄的同時，將索引項指向下一條具有該搜索碼值的記錄。
稀疏索引
如果不存在包含被刪除記錄的索引項，則不做任何操作。
如果被刪除的記錄是具有該搜索碼值的唯一記錄，則索引項A指向下一個包含該搜索碼值的記錄，但如果下一個包含該搜索碼值的記錄已經(jīng)有索引項，則刪除索引項A。
如果被刪除的記錄并非是具有該搜索碼值的唯一記錄，則索引項指向下一條具有相同搜索碼值的記錄。
學(xué)習(xí)資料：Database System Concepts, by Abraham Silberschatz, Henry F.Korth, S.Sudarshan
