【概述】

分塊索引既適用于靜態索引，又適用于動態索引。

在稠密索引中，索引項的個數與文件記錄個數相同，空間代價很大，為減少索引項的個數，可以對文件分塊，使分塊有序。

分塊有序，是指數據集的記錄分為若干塊，并且這些塊滿足兩個條件：

• 塊間有序：后一塊的所有記錄的關鍵字要大于前一塊的所有記錄的關鍵字
• 塊內無序：每一塊的記錄不要求有序

在分塊索引表中進行的查找稱為分塊查找，其分兩步進行：

在索引表中確定待查關鍵碼所在的塊：塊間是有序的，可使用二分查找、插值查找等提高效率

在相應塊中查找待查關鍵碼：塊內是無序的，只能使用順序查找

【方法】

對于分塊有序的數據集，將每塊對應一個索引項，其結構分為三個部分：

• 最大關鍵碼：存儲每一塊的最大關鍵字，以便在下一塊中的最小關鍵字也能比這一塊的最大關鍵字大
• 塊長：存儲塊中記錄個數
• 塊首地址：指向塊首數據元素的指針

【時間復雜度分析】

設 n 個記錄的文件分成 m 個塊，每個塊內均有 t 條記錄，則：n=m*t

設 Lb 為查找索引表確定關鍵碼所在塊的平均查找長度，Lw 為在塊內查找關鍵碼的平均查找長度，則分塊查找的平均查找長度為：ASL=Lb+Lw

若采用順序查找對索引表進行查找，則分塊查找的平均查找長度為：

根據上面的式子可以發現，平均查找長度不僅取決于數據集的總記錄數 n，還和每一個塊的記錄個數 t 有關，最佳的情況就是分的塊數 m 與塊中的記錄數 t 相同，此時有：n=m*t=t*t

那么有：

可見，分塊查找的時間復雜度 O(√n) 比順序查找的 O(n) 提高不少，但與二分查找的 O(logn) 相比還是有不小的差距，因此在確定塊的過程中，由于塊間有序，所以可以采用二分、插值等方法來提高效率。

總結

以上是生活随笔為你收集整理的理论基础 —— 索引 —— 分块索引的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。