索引查找核心模型
索引查找將「查找」拆解為兩階段：
- 索引表查找：在較小的索引表中按關鍵字定位記錄的存儲地址/塊號。
- 數據區讀取：根據地址直接讀取完整記錄。
索引項結構：{關鍵字, 記錄地址/塊號}。索引表本身可有序（支援折半等）或無序（僅順序查找）。
三大索引結構詳解
1. 稠密索引
- 定義：每個數據記錄對應一個索引項。
- 優點：查找快，直接定位到具體記錄。
- 缺點：索引表大，隨數據量線性增長；大數據量時索引本身需二級索引或分頁。
- 適用：數據量較小、記錄長度固定、頻繁點查詢場景。
2. 分塊索引
- 定義：將數據劃分為若干塊，塊間有序（塊最大關鍵字遞增），塊內無序。每塊對應一個索引項（記錄塊最大關鍵字與塊起始地址）。
- 查找流程：
- 在索引表中（折半/插值/斐波那契）查找目標塊。
- 在目標塊內順序查找具體記錄。
- 優點：索引表小（塊數 ≪ 記錄數），插入刪除只需調整塊內，維護成本低。
- 缺點：塊內順序查找較慢；塊大小選擇需權衡（塊大→索引小但塊內慢；塊小→索引大但塊內快）。
- 適用：大數據量、頻繁動態增刪、磁盤存儲（塊對應磁盤頁/區）。
3. 倒排索引
- 定義：以屬性值（關鍵字/詞項）為主鍵，記錄包含該屬性的所有文檔/記錄 ID 列表。即「詞 → 文檔列表」映射。
- 核心結構：
- 詞典：所有不重複詞項，有序存儲（支援折半/Trie/雜湊查找）。
- 倒排列表：每個詞項對應的文檔 ID 有序序列（可壓縮存儲）。
- 典型應用：全文搜尋引擎、日誌分析、標籤系統、推薦系統倒排表。
- 查找邏輯：多詞查詢 → 分別取出倒排列表 → 布爾運算（交/並/差）合併 → 排序打分 → Top-K 輸出。
三類索引對比總結
| 維度 | 稠密索引 | 分塊索引 | 倒排索引 |
|---|
| 索引粒度 | 記錄級 | 塊級 | 詞項級 |
| 索引大小 | 大（∝ 記錄數） | 小（∝ 塊數） | 中（∝ 不重複詞項數） |
| 查找速度 | 最快（直達記錄） | 中（兩階段） | 視詞項頻率與合併算法 |
| 動態維護 | 困難（插刪需移動索引） | 較易（塊內調整） | 複雜（需合併倒排列表） |
| 典型場景 | 小表點查、主鍵索引 | 大表範圍查、磁盤存儲 | 全文搜尋、多屬性過濾 |
工程延伸：從線性索引到多級索引與 B+ 樹
- 稠密索引過大時 → 建立二級索引（索引的索引） → 形成多級索引。
- 多級索引固化為磁盤頁面大小、平衡多路查找樹 → B+ 樹（資料庫主流索引結構）。
- 倒排索引詞典常用 FST (Finite State Transducer) 或 Trie + 跳表 實現高效前綴匹配與壓縮。
總結
線性索引查找通過「以空間換時間、以結構換速度」的思想，提供了稠密、分塊、倒排三種經典權衡點。理解其結構特性與適用邊界，是設計資料庫索引、搜尋引擎、大數據檢索系統的核心基礎。
