核心定義體系
| 術語 | 定義 | 關鍵點 |
|---|
| 查找表 | 同類型數據元素/記錄的集合 | 所有待查數據的統稱 |
| 關鍵字 | 數據元素中某數據項的值 | 用於標識記錄，不一定唯一 |
| 主關鍵字 | 能唯一標識記錄的關鍵字 | 對應數據項稱主關鍵碼 |
| 次關鍵字 | 可識別多個記錄的關鍵字 | 非唯一標識 |
| 查找 | 根據給定值在表中確定關鍵字相等的記錄 | 成功返回記錄/位置；失敗返回空 |
查找表分類與操作特徵
靜態查找表
- 僅支援查詢操作：
1) 某特定元素是否存在；2) 檢索特定元素屬性。
- 數據結構固定，適合排序後的高效查找（折半、斐波那契等）。
動態查找表
- 支援查找過程中
插入不存在元素、刪除已存在元素。
- 需維護結構平衡，典型結構：二叉排序樹、平衡二叉樹（AVL）、紅黑樹、B樹、哈希表。
查找結構的邏輯與存儲權衡
- 邏輯層面：查找基於「集合」，記錄間無本質關係。
- 存儲層面：為獲高效能，可組織為線性表（順序/鏈式）、樹結構（二叉排序樹、B+樹）、雜湊表。
- 選擇原則：
- 靜態 + 有序 → 順序表 + 折半查找
- 動態 + 頻繁增刪 → 平衡二叉樹 / 紅黑樹
- 極致查找速度、鍵值分布均勻 → 雜湊表
- 磁盤/外部存儲、範圍查詢 → B+ 樹
經典查找算法譜系
| 類別 | 算法 | 前提條件 | 時間複雜度 | 備註 |
|---|
| 線性表 | 順序查找 | 無 | O(n) | 最基礎，哨兵優化可減少邊界判斷 |
| 有序表 | 折半查找 | 有序、順序存儲 | O(log n) | 經典二分 |
| 有序表 | 插值查找 | 有序、鍵值均勻分布 | O(log log n) 平均 | 利用鍵值分布估算位置 |
| 有序表 | 斐波那契查找 | 有序、順序存儲 | O(log n) | 黃金分割點，僅加減法 |
| 索引表 | 稠密/分塊/倒排索引 | 大數據量 | 視索引結構 | 塊間有序、塊內無序 |
| 樹結構 | 二叉排序樹 | 動態增刪 | O(h) 平均 O(log n) | 最壞退化鏈表 |
| 樹結構 | 平衡二叉樹(AVL) | 動態增刪+平衡 | O(log n) 最壞 | 旋轉維護平衡因子 |
| 雜湊 | 哈希表 | 鍵值可哈希 | O(1) 平均 | 處理衝突：鏈地址/開放定址 |
總結
查找算法的核心在於「根據業務特徵選擇合適的邏輯模型與存儲結構」。靜態場景追求極致查找速度（折半、斐波那契、哈希）；動態場景追求增刪查平衡（平衡樹、B+樹、哈希）。理解各算法的前提條件、複雜度邊界與工程權衡，是設計高效存儲引擎、索引系統、快取層的基石。
