Java線性索引查找是什么

這篇文章主要介紹“Java線性索引查找是什么”，在日常操作中，相信很多人在Java線性索引查找是什么問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java線性索引查找是什么”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

線性索引查找

索引:就是把一個關鍵字與它對應的記錄相關聯的過程，一個索引由若干個索引項構成，每個索引項至少應包含關鍵字和其對應的記錄在存儲器中的位置等信息。

索引按照結構可以分為：線性索引、樹形索引和多級索引。

線性索引是將索引項集合組織為線性結構，也稱為索引表。包括稠密索引、分塊索引、倒排索引。

1. 稠密索引：

一個完美的引子：將數據集中的每個記錄對應一個索引項

我母親年紀大了，記憶力不好，經常在家里找不到東西，于是她想了一個辦法。她用一個小本子記錄了家里所有小東西放置的位置，比如戶口本放在右手床頭柜下面抽屜中，針線放在電視柜中間的抽屜中，鈔票放在衣柜……總之，她老人家把這些小物品的放置位置都記錄在了小本子上，并且每隔一段時間還按照本子整理一遍家中的物品，用完都放回原處，這樣她就幾乎再沒有找不到東西。從這件事情就可以看出，家中的物品盡管是無序的，但是如果有一個小本子記錄，尋找起來也是非常容易的，而這小本子就是索引。

稠密索引是指在線性表中，將數據集中的每個記錄對應一個索引項。

對于稠密索引這個索引表來說，索引項一定是按照關鍵碼有序的排列。通過對索引項的查找，就可以找到丟應的結果地址，但是如果數據集非常大，比如說上億，那也就意味著索引同樣的數據規模，可能就需要反復查詢內存和硬盤，性能可能反而下降了。

2. 分塊索引

引子：圖書館如何藏書

分塊有序需要滿足兩個條件：塊內無序（有序更好，代價比較大）、塊間有序

對于分塊有序的數據集，將每塊對應一個索引項，這種索引方法叫做分塊索引。

最大關鍵碼、塊長和塊首指針很容易理解。

平均查找長度ASL 為 在索引表中的平均查找長度 + 在記錄（數據集）中的平均查找長度。

假設 有m塊，每塊中共有t條記錄，顯然n = m * t。

故而 ASL = (m+1)/2 + (t+1)/2 = (n/t + t)/2 + 1. 上式的最小值，即n/t = t，n = t^2，則最小的ASL = n^(1/2) + 1;

可見，分塊索引的效率比順序查找o(n) 高了很多，但比折半查找法O(logN)還是有差別的，總的來說，分塊索引在兼顧了對細分塊不需要有序的情況下，大大增加了整體查找的速度，所以普遍被用于數據庫查找等技術的應用當中。

3. 倒排索引

引子：搜索引擎如何進行搜索，能夠在非常快的速度之下顯示搜索的最優匹配內容。

索引項的結構是次關鍵字碼和記錄號表，其中記錄號表存儲具有相同關鍵字的所有記錄的記錄號（可以是指向記錄的指針或者是該記錄的主關鍵字），這樣的索引方法就是倒排索引。

 這時我們輸入book搜索會立馬顯示有1 2 文章。

索引項的通用結構為：

1.次關鍵碼 比如上面的 英文單詞

2.記錄號表 比如上面的文章編號

倒排索引源于實際應用中需要根據屬性（或字段、次關鍵碼）的值來查找記錄。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。由于不是由記錄來確定屬性值，而是由屬性來確定記錄的位置，因而稱為倒排索引。

倒排索引的優點顯然是查找記錄非常快，基本等于生成索引表后，查找時都不用去讀取記錄，即可以得到結果。但是它的缺點是這個記錄號不定長，可多可少。

ps. 現實中的搜索技術要復雜得多，涉及到太多內容。

到此，關于“Java線性索引查找是什么”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！