索引查找是在索引表和主表(即線性表的索引存儲結構)上進行的查找。
基本介紹
- 中文名：索引查找算法
- 外文名：Index search algorithm
- 性質：算法
- 功能：索引查找
索引查找是在索引表和主表(即線性表的索引存儲結構)上進行的查找。索引查找的過程是：首先根據給定的索引值K1，在索引表上查找出索引值等於K1的索引項，以確定K1對應的子表在主表中的開始位置和長度，然後再根據給定的關鍵字K2，在對應的子表中查找出關鍵字等於K2的元素(結點)。
設數組A是具有mainList類型的一個主表，數組B是具有indexList類型的在主表A 上建立的一個索引表，m為索引表B的實際長度，即所含的索引項的個數，K1和K2分別為給定待查找的索引值和關鍵字，當然它們的類型應分別為索引表中索引值域的類型和主表中關鍵字域在索引存儲中，不僅便於查找單個元素，而且更便於查找一個子表中的全部元素。當需要對一個子表中的全部元素依次處理時，只要從索引表中查找出該子表的開始位置即可。由此開始位置可以依次取出該子表中的每一個元素，所以整個查找過程的時間複雜度為O(1)，若不是採用索引存儲，而是採用順序存儲，即使把它組織成有序表而進行二分查找時，索引查找一個子表中的所有元素與二分查找一個子表中的所有元素相比還是要快的多。
若在主表中的每個子表後都預留有空閒位置，則索引存儲也便於進行插入和刪除運算，因為其運算過程只涉及到索引表和相應的子表，只需要對相應子表中的元素進行比較和移動，與其它任何子表無關，不像順序表那樣需涉及到整個表中的所有元素，即牽一髮而動全身。
線上性表的索引存儲結構上進行插入和刪除運算的算法，也同查找算法類似，其過程為：首先根據待插入或刪除元素的某個域(假定子表就是按照此域的值劃分的)的值查找索引表，確定出對應的子表，然後再根據待插入或刪除元素的關鍵字，在該子表中做插入或刪除元素的操作。因為每個子表不是順序存儲，就是連結存儲，所以對它們做插入或刪除操作都是很簡單的。
