資料庫儲存與索引：等值、範圍與分析查詢
本頁為依教材與考古題整理的原創摘要；考古題答案經技術覆核，但不是官方答案。
第一次接觸也沒關係
這堂先懂這些詞
先記住白話意思，不必急著背英文。看到正文時，再把正式名稱接回來。
資料庫索引
也會看到：index、B-tree、B+ tree、hash index、索引建立額外查找結構，讓資料庫不必每次掃完整張表。
- 生活例子：
- 像書末索引讓你直接找到頁碼，不必從第一頁翻起。
- 別搞混：
- 索引會占空間並增加寫入維護成本，不是每個欄位都建越多越好。
雜湊碰撞
也會看到：hash collision、collision、雜湊衝突不同輸入經雜湊後落到同一位置，需要額外規則分開保存。
- 生活例子：
- 兩位同姓客人被分到同一取餐代號，櫃台還要用其他資訊辨認。
- 別搞混：
- 碰撞是有限位置下的正常可能，不等於雜湊函式壞掉或被攻擊。
選擇率與查詢最佳化器
也會看到：selectivity、query optimizer、query plan選擇率描述條件能縮小多少資料；最佳化器估算不同執行方式成本後選擇 query plan。
- 生活例子：
- 找唯一訂單編號比找『今年訂單』縮得更小，較可能適合精準索引。
- 別搞混：
- 有索引不代表一定使用；掃描大量資料時全表掃描可能更便宜。
資料倉儲與 OLAP
也會看到：data warehouse、OLAP、multidimensional analysis資料倉儲整合歷史資料供分析；OLAP 從時間、地區、商品等多個維度快速彙總比較。
- 生活例子：
- 像主管用同一批銷售歷史，切換查看各月份、城市與品類。
- 別搞混：
- OLAP 偏分析查詢，不等同處理日常逐筆訂單的 OLTP。
從 page I/O 與資料排列理解 heap file、B+ tree、hash index、多維分析結構及 optimizer 選擇，避免把所有索引都當成無條件加速器。
先抓住這幾件事
- 說明索引以額外空間與維護成本換取讀取效率
- 比較 B+ tree 與 hash index 的等值及範圍能力
- 辨識 data warehouse/OLAP 與多維分析需求
- 解釋 selectivity 與 query plan 為何影響索引使用
先想像這個場景
圖書館找書與月度分析
館員既要讓讀者用 ISBN 立刻找到一本書，也要查出版年份區間，月底還要分析各館別、月份與類別的借閱量。單一目錄結構不一定同時最佳。
先別急著往下看，花十秒想一想：
把 2020、2021、2022 經 hash 後放進不同櫃位，是否仍能從 2020 的櫃位一路掃到 2022？
把故事換成電腦語言
| 生活中的角色 | 對應到 | 技術概念 |
|---|---|---|
| 書架上的實體批次 | Database pages 與 page I/O | |
| 依 ISBN 直接查櫃位 | Equality lookup 與 hash index | |
| 沿年份排序目錄查一段區間 | B+ tree leaf range scan | |
| 依月份、館別、類別切換報表 | OLAP dimensions 與 measures | |
| 人太多時乾脆順著整排巡一次 | Optimizer 選 sequential scan |
題目出現這些字，先想到
- 看到 range query：優先想到保留排序且葉節點相連的 B+ tree。
- 看到 hash 不適合 range：理由是破壞 ordering，不是單純 storage 較大。
- 看到 warehouse、OLAP、slice/dice：辨識 multidimensional analysis。
- 看到『有 index 為何沒用』：檢查 selectivity、回表與 page I/O 成本。
1.資料庫成本常由 page I/O 主導
Records 儲存在 pages；heap file 不維持 key 順序，插入通常直接，但搜尋可能掃描多頁。Index 保存 search key 到 record/page 的導引，讓查詢少讀 pages，代價是額外空間與 INSERT/UPDATE/DELETE 維護。
- Index 不是資料本身的免費副本
- Sequential scan 對大量結果可能更划算
- 更多 indexes 會增加寫入成本
- Physical design 取決於 workload
2.B+ tree 保留排序，適合 range scan
B+ tree 是高扇出的平衡搜尋樹，內部節點導引搜尋，葉節點依 key 排序並通常相連。等值查詢可沿 root-to-leaf，範圍查詢找到起點後沿葉節點順序掃描。
- 所有資料 entries 位於葉層
- 樹高通常很低
- 葉節點排序支援 BETWEEN、<、>
- 平衡性讓搜尋成本穩定
3.Hash index 擅長 equality，會破壞順序
Hash function 將相近 key 映射到可能完全不同 buckets，因此 `key = value` 可直接定位候選 bucket，但 `20 <= key <= 30` 沒有連續路徑可循。碰撞策略仍會影響等值查詢成本。
- Equality predicate 是 hash index 強項
- Range predicate 通常不是
- Hash collision 不等於查不到資料
- Hash index 不保留 key ordering
4.OLAP 與 optimizer 看的是整體工作負載
Data warehouse 常服務聚合、切片、鑽取等 OLAP 分析；多維資料庫或 cube 以 dimensions 與 measures 組織分析。Relational optimizer 會依符合比例、statistics、join cost 與預估 page I/O 選 scan 或 index，索引存在不代表一定使用。
- Highly selective predicate 通常只讓少量 rows 符合；用符合比例描述可避免 high/low selectivity 的教材歧義
- Statistics 過期可能選錯 plan
- Covering index 可減少回表
- OLTP 與 OLAP 的 workload 不同
一起拆題目
範例 1：查詢 `age BETWEEN 20 AND 30`，B+ tree 與 hash index 何者較合適？
- 此條件需要 key order
- B+ tree 找到 20 後沿葉節點掃到 30
- Hash mapping 不保留 20 到 30 的連續關係
所以答案是：通常選 B+ tree；hash index 較適合 `age = 25`。
範例 2：一個查詢會讀取全表 70% rows，optimizer 為何可能不用現有 index？
- 走 index 需讀大量 index entries
- 還可能對每筆回表造成隨機 I/O
- Sequential scan 可能以較少且連續的 page I/O 完成
所以答案是：索引不是必然較快；低選擇性的查詢可能以全表掃描成本更低。
這裡最容易選錯
- 認為建 index 永遠加速所有操作
- 說 hash index 能自然支援 range query
- 把 B+ tree 與 binary tree 的扇出混為一談
- 忽略寫入維護與額外空間
- 認為 optimizer 一定使用已存在的 index
換你快速判斷
先在心中作答，再展開答案。答不出來時，回頭找本課的對照關係。
1B+ tree 為何適合 range query？
Keys 在葉節點保持排序且葉節點相連；找到範圍起點後可順序掃描到終點。
高扇出與平衡性也讓 root-to-leaf page I/O 維持低高度。
2Hash index 為何通常不適合 range query？
Hash function 破壞 key 的排序關係，相鄰值可能落到完全不同 buckets，無法沿連續位置掃描。
Hash index 通常適合 equality lookup，而非 BETWEEN、<、>。
最後用考古題驗證
本課連結的題目都已通過可重現的技術覆核，可逐題練習與判分。
開始本課考古題練習參考來源
- Computer Science: An Overview, 13th Edition — J. Glenn Brookshear
- 資料庫課程 — 陳士杰（杰哥數位教室）