[TOC] # 索引 ## 定義： > 索引是為了加快查找速度而設計的一種數據結構。索引就是把一個關鍵字與它對應的記錄相關聯的過程，一個索引由若干索引項構成，每個索引項至少包含關鍵字和其對應記錄在存儲器中的位置等信息。 > 由此可見，索引技術是組織大型數據庫和磁盤文件的一種重要技術。 ## 索引技術的劃分 > 1. 線性索引 > 2. 樹形索引 > 3. 多級索引 ## 線性索引 ### 定義： > 線性索引就是將索引項集合組織為線性結構，也稱索引表。  ### 線性索引分類 > 1. 稠密索引 > 2. 分塊索引 > 3. 倒排索引 ### 稠密索引 #### 定義： > 稠密索引是指在線性表中，將數據集中的每個記錄對應一個索引項。就像我們上面示例圖中的那樣。以主鍵為例，可以將其抽象化如下： >  #### 應用： > 對于稠密索引這個索引表來說，索引項一定按照關鍵碼有序排列，這樣可以應用二分查找，以免索引查找本身影響性能。可見，稠密索引性能可以做到和二分查找相當（找到對應關鍵碼就可以通過指針直接指向對應記錄），但是索引項長度和數據集一樣長，空間復雜度高，如果數據太多需要存放到磁盤上，反復讀取磁盤對性能影響很大。 ### 分塊索引 #### 定義： > 我們對數據集進行分塊，并使其**分塊有序**，然后再給每個分塊建立一個索引項（索引值是分塊中最大關鍵碼），至于分塊內部，則不管其有序性，從而減少索引項的個數。在查找的時候在索引項中通過二分查找找到指定索引項，然后根據該索引項中的關鍵碼去相應分塊遍歷查找指定元素，這是一種折中方案，既兼顧了空間復雜度，又兼顧了時間復雜度。 >  #### 分塊有序 > 1. 塊內無序：每一塊內的記錄不要求有序。當然，有序更理想，只不過要花費大量的時間和空間的代價。 > 2. 塊間有序：要求后一塊的所有關鍵字都大于前一塊的所有關鍵字。只有塊間有序，才能給查找帶來效率。 #### 分塊索引的索引項的組成 > 1. 最大關鍵碼：它存儲每一塊中的最大關鍵字。這樣做的好處是在它之后的下一塊中的最小的關鍵字也能比這一塊最大的關鍵字要大。 > 2. 塊長：存儲塊中的記錄的個數，以便于循環時使用。 > 3. 塊首指針：用于指向塊首數據元素的指針，便于開始對這一塊的記錄開始遍歷。 #### 應用 > 1. 在分塊索引表中查找關鍵字所在的塊。由于塊間有序，所以可以通過二分查找快速定位（通過不小于給定值的第一個元素，不大于給定值的最后一個元素確定區間，以前面給出的示例圖為例，58位與57和96之間，則會去第三塊中查找）。 > 2. 根據塊首指針找到對應的塊，并在塊中順序查找指定的值（即關鍵碼，塊中無序所以只能順序查找）。 #### 性能 > 分塊索引的時間復雜度是：O(log(m)+n)，其中 m 是分塊數，n 是塊內元素個數，在索引表長度和塊內元素相等時，時間復雜度最優。性能要由于順序查找，但是比二分查找要差。 總體來說，分塊索引在兼顧存儲空間和查找性能的情況下，被普遍用于數據庫查找等技術中。 ### 正向索引 #### 定義 > 正向索引指的是通過文檔 ID 找到對應的文檔，如果通過文檔ID查找對應文檔，再在文檔中匹配關鍵詞，意味著要掃描所有文檔，最后還要排序，對于互聯網上的海量資源來說，顯然是不可取的。 ### 倒排索引 > 通過分析每個文檔，提取其中的關鍵字，并建立關鍵詞與文檔 ID 的映射關系，每個關鍵詞都對應著多個文檔 ID。由于不是通過文檔來確定屬性（這里的屬性是關鍵詞），而是通過屬性來確定文檔，故而將其稱作倒排索引。