資料結構的目的就是提高資料的處理速度，索引視為了加快查找速度而設計的一種資料結構。索引就是把一個關鍵字與它對應的記錄相關聯的過程，一個索引由若幹個索引項組成，每個索引項至少應包含關鍵字和其對應的記錄在存儲器中的位置等資訊。索引技術是組織大型資料庫以及磁盤檔案的一種重要技術。
稠密索引
稠密索引是指線上性索引中，将資料集中的每個記錄對應一個索引項。如圖1-1所示。
圖1-1
對于稠密索引這個索引表來說，索引項一定是按照關鍵字有序的排列。
索引項有序也就意味着，我們要查找關鍵字時，可以用到折半，插值，裴波納契等有序查找算大，大大提高了效率。
比如在圖1-1中，我們要查找關鍵字是18的記錄。如果直接中右側的資料表中查找，那麼就隻能順序查找，我們需要查找6次才可以查到結果，而如果我們是從左側的索引表中查找，隻需要兩次折半查找就可以得到18對應的指針，最終查找到結果。
這就是稠密索引的優點，但是如果資料集非常的大，比如幾百萬，那也就意味着索引也得同樣的資料集長度規模，對與記憶體有限的計算機來說，可能就是需要反複去通路磁盤，查找性能反而就下降了。
分塊索引
稠密索引因為索引項與資料集的記錄個數相同，是以空間代價很大，。為了減少索引項的個數，我們可以對資料集進行分塊，使其分塊有序，然後對每一個塊建立一個索引項，進而減少索引項的個數。
分塊有序就是把資料集的記錄分成了若幹塊，并且這些塊小需要滿足兩個條件：
- 塊内無序：每一個塊内的記錄不要求有序。當然你如果能夠讓塊内有序查找來說更理想。不過這就要付出大量時間和空間的代價。是以通常我們不要求塊内有序。
- 塊間有序：例如，要求第二塊所有記錄的關鍵字均要島嶼第一塊中所有記錄的關鍵字，第三塊的所有記錄的關鍵字要大于第二塊的所有記錄的關鍵字，因為隻有塊間有序，才有可能在查找時帶來效率。
對于分塊有序的資料集，将每塊對應一個索引項。這種索引方法叫做分塊索引。
如圖1-2所示，我們定義的分塊索引的索引項結構分三個資料項。
- 最大關鍵碼：它存儲每一個塊中的最大關鍵字，這樣的好處就是可以使得在它之後的下一塊中的最小關鍵字也能比這一塊最大的關鍵字要大。
- 存儲了塊中的記錄個數，以便于循環使用。
- 用于指向塊首資料元素的指針，便于開始對這一塊中記錄進行周遊。
圖1-2 在分塊索引表中查找，就是分兩部分進行：
- 在分塊索引中表彙查找要查關鍵字的所在的塊。由于分塊索引表是塊間有序的，是以很容易使用折半，插值等算法得到結果。
- 根據塊的首指針找到對應的塊。并在快中順序查找關鍵碼。因為塊中是無序的，是以隻能順序查找。
step1 先選取各塊中的最大關鍵字構成一個索引表； 時間複雜度 log2(m)
step2 查找分兩個部分：先對索引表進行二分查找或順序查找，以确定待查記錄在哪一塊中；在已确定的塊中用順序法進行查找。 時間複雜度 n/m
總複雜度 log2(m) + n/m
當 m = 1時，即為順序查找
當 m = n時，即為索引查找，
否則 時間複雜度介于二者之間
反向索引
反向索引源于實際應用中需要根據屬性的值來查找記錄。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的位址。由于不是由記錄來确定屬性值，而是由屬性值來确定記錄的位置，因而稱為反向索引(inverted index)。帶有反向索引的檔案我們稱為反向索引檔案，簡稱倒排檔案(inverted file)。
優缺點：反向索引的優點是速度快，缺點就是記錄不等長，維護比較困難，插入和删除都要做相應的處理。比如删除某個文章，就可能要對所有的單詞都進行考察。