萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 資料庫 >> 資料庫綜合

資料庫索引底層原理深度解析:B+ 樹結構、頁面管理與查詢優化機制

為什麼要理解索引原理?

索引是資料庫效能的靈魂。不懂原理,就無法解釋:為什麼有索引查詢還慢?為什麼不走索引掃描反而更快?為什麼寫入效能隨索引增加而下降?本文以 SQL Server 為例 (原理通用於 InnoDB、Oracle、PostgreSQL),從存儲層層層剖析。

一、資料表物理存儲基礎:頁面與堆

1. 頁面 — 最小 I/O 單位 (8 KB)

  • 資料頁、索引頁、文本/圖像頁、IAM 頁、PFS/GAM/SGAM 空間管理頁
  • 行不跨頁 → 最大行大小 8060 字節 (除 LOB 外)
  • 頁頭 96 字節:頁號、物件 ID、索引 ID、LSN、空閒空間指針、槽位陣列

2. 區 — 8 頁連續空間 (64 KB)

  • 混合區:前 8 頁可能屬於不同物件 (新建表起步)
  • 專用區:8 頁屬於同一物件 (擴展後)

3. IAM 頁 — 空間分配地圖

  • 每個 IAM 頁管理 4 GB 範圍 (約 512,000 頁)
  • 記錄:該物件擁有哪些區、哪些混合區頁面
  • sys.system_internals_allocation_units 可查 IAM 鏈

4. 堆表 vs 叢集索引表

特性 堆表 叢集索引表
資料順序 無序 (插入位置由 PFS/IAM 決定) 按叢集鍵邏輯有序 (物理盡量有序)
定位方式 RID (File:Page:Slot) 叢集鍵值 (Key Lookup 用)
非叢集索引葉層 存 RID 存叢集鍵值
頁分裂 較少 (插入尾部) 隨機鍵頻繁分裂

二、B+ 樹索引結構深度剖析

為什麼是 B+ 樹而非 B 樹、Hash、跳表?

  • B 樹:非葉節點也存資料 → 單頁容納鍵值少 → 樹高增加 → I/O 增加
  • Hash:僅支援等值查詢,不支援範圍/排序/前綴匹配
  • 跳表:記憶體友好,磁碟 I/O 不友好 (指針跳躍非連續)
  • B+ 樹:非葉節點只存鍵值+指針 → 單頁容納更多鍵值 → 樹高更低 (通常 3-4 層支撐億級資料);葉節點雙向鏈表 → 範圍掃描極快;所有資料在葉層 → 查詢路徑長度固定

索引頁面結構 (以非叢集索引為例)

+------------------ 索引頁面 (8KB) ------------------+
| Page Header (96 bytes)                          |
|   - Page ID, Object ID, Index ID, LSN, ...      |
|   - Prev/Next Page Pointers (雙向鏈表)           |
|   - Free Space Offset, Slot Array Offset        |
+-------------------------------------------------+
| Slot Array (每槽 2 bytes,從頁尾向前增長)        |
|   [0] → Offset 96   (Key: 100, Child: Page 101) |
|   [1] → Offset 120  (Key: 200, Child: Page 102) |
|   [2] → Offset 144  (Key: 300, Child: Page 103) |
|   ...                                            |
+-------------------------------------------------+
| Free Space (插入新記錄向前擴展)                  |
+-------------------------------------------------+
| Data Rows (索引記錄:Key + Row Locator)          |
|   Key: 索引鍵值 (含 Included Columns)            |
|   Row Locator: RID (堆) 或 Clustered Key (叢集)  |
+-------------------------------------------------+

三層結構對應 sysindexes / sys.dm_db_index_physical_stats

  • Root Level (Level = Max):單一 Root 頁,sysindexes.root 指向
  • Intermediate Levels (Level 1 to Max-1):非葉層,導航用
  • Leaf Level (Level 0):資料/索引行實際存放處

三、索引查詢過程:從 Root 到 Leaf 的「兩分法」之旅

-- 查詢:SELECT * FROM Orders WHERE OrderID = 50000;
-- 叢集索引 CX_Orders_OrderID (OrderID)

1. 讀取 Root Page (Level 2)
   Keys: [10000, 30000, 50000, 80000] → 50000 >= 50000 走第 4 個指針 → Page 204

2. 讀取 Intermediate Page (Level 1) - Page 204
   Keys: [40000, 45000, 50000, 55000] → 50000 >= 50000 走第 4 個指針 → Page 305

3. 讀取 Leaf Page (Level 0) - Page 305
   Keys: [49990, 49995, 50000, 50005] → 定位 Slot 2 → 讀取完整行資料 (含所有列)

總計:3 次邏輯讀 (若熱頁在記憶體則 0 物理 I/O)

關鍵洞見:

  • 樹高 = 層數 = CEILING(LOG_Fanout(Rows)),Fanout = 頁面容納鍵值數 (通常 100-500)
  • 億級資料 (10^8) → Fanout 200 → 樹高 3-4 → 最多 3-4 次 I/O 定位任意行
  • 非叢集索引查詢若需回表 (Key Lookup) → 額外 3-4 次 I/O → 覆蓋索引 避免回表

四、頁面分裂與填充因子:寫入效能的隱形殺手

頁面分裂過程

  1. 插入鍵值落入已滿頁面
  2. 分配新頁面 (可能非連續 → 邏輯碎片)
  3. 移動 50% 記錄到新頁
  4. 更新父層指針 (可能觸發級聯分裂至 Root)
  5. 產生 邏輯碎片 (邏輯順序 ≠ 物理順序) 與 密度下降 (頁面填充率降低)

Fill Factor (填充因子) 策略

場景 建議 Fill Factor 理由
唯一遞增鍵 (Identity, Sequence) 100 (或 0 = 默認 100) 永遠插入尾部,無分裂
隨機鍵 (UUID, 複合鍵) 70-90 預留空間減少分裂頻率
大量更新導致行長度增長 70-80 預留前向擴展空間
唯讀/極少寫入 100 最大化空間利用率

ALTER INDEX IX_Orders_CustomerID ON Orders REBUILD WITH (FILLFACTOR = 80, ONLINE = ON);

五、統計資料與查詢優化器:索引被選中的數學依據

  • 統計資料: 直方圖 (RANGE_HI_KEY, RANGE_ROWS, EQ_ROWS, DISTINCT_RANGE_ROWS, AVG_RANGE_ROWS) + 密度向量
  • 選擇率估算: 優化器根據統計資料估算 WHERE col = value 返回行數
  • 代價模型: I/O 代價 (頁面讀取) + CPU 代價 (比較/運算) → 選擇最低代價計畫
  • 參數嗅探: 首次編譯時嗅探參數值生成計畫,後續複用可能不適合其他參數值

六、實戰診斷查詢

-- 1. 索引碎片與頁面密度
SELECT 
  OBJECT_NAME(ips.object_id) AS TableName,
  i.name AS IndexName,
  ips.index_type_desc,
  ips.avg_fragmentation_in_percent,
  ips.avg_page_space_used_in_percent,
  ips.page_count,
  ips.record_count
FROM sys.dm_db_index_physical_stats(DB_ID(), NULL, NULL, NULL, 'LIMITED') ips
JOIN sys.indexes i ON ips.object_id = i.object_id AND ips.index_id = i.index_id
WHERE ips.page_count > 1000
ORDER BY ips.avg_fragmentation_in_percent DESC;

-- 2. 缺失索引建議 (優化器記錄的遺憾)
SELECT 
  migs.avg_total_user_cost * migs.avg_user_impact * (migs.user_seeks + migs.user_scans) AS improvement_measure,
  mid.statement AS TableName,
  mid.equality_columns, mid.inequality_columns, mid.included_columns,
  migs.user_seeks, migs.user_scans
FROM sys.dm_db_missing_index_group_stats migs
JOIN sys.dm_db_missing_index_groups mig ON migs.group_handle = mig.index_group_handle
JOIN sys.dm_db_missing_index_details mid ON mig.index_handle = mid.index_handle
WHERE mid.database_id = DB_ID()
ORDER BY improvement_measure DESC;

-- 3. 未使用索引 (維護成本 > 查詢收益)
SELECT 
  OBJECT_NAME(s.object_id) AS TableName,
  i.name AS IndexName,
  s.user_seeks, s.user_scans, s.user_lookups, s.user_updates,
  s.last_user_seek, s.last_user_scan, s.last_user_lookup
FROM sys.dm_db_index_usage_stats s
JOIN sys.indexes i ON s.object_id = i.object_id AND s.index_id = i.index_id
WHERE s.database_id = DB_ID()
  AND i.is_primary_key = 0 AND i.is_unique_constraint = 0
  AND s.user_seeks + s.user_scans + s.user_lookups = 0
  AND s.user_updates > 0
ORDER BY s.user_updates DESC;

總結:索引原理決定設計決策

  1. B+ 樹結構 決定了等值/範圍/排序/分組查詢極快,但不等值 (!=、NOT IN)、函數運算、隱式轉換導致掃描
  2. 葉層存完整行 (叢集) 或 Row Locator (非叢集) 決定了覆蓋索引 (Included Columns) 是避免 Key Lookup 的銀彈
  3. 頁面分裂機制 決定了隨機鍵需 Fill Factor、遞增鍵最適合叢集索引
  4. 統計資料準確性 決定了優化器能否選對索引 → 自動更新統計 + 定期全掃描更新

理解這些原理,您就能從「聽說要加索引」進化為「基於存儲結構、查詢模式、寫入特性做精準索引設計」。

copyright © 萬盛學電腦網 all rights reserved