申論題

B+-tree 索引的結構和特性

B+-tree 是一種平衡樹結構，廣泛應用於資料庫和文件系統中的索引。它的主要特性包括：

• 自平衡：B+-tree 保持平衡，使所有葉節點在同一深度。
• 有序性：葉節點按鍵值排序，有助於範圍查詢和順序訪問。
• 分層結構：分為內部節點和葉節點，內部節點用來引導搜索，葉節點存放實際的索引資料。

葉節點和內部節點所存放的資料

• 葉節點：

  • 存放 Name 欄位的鍵值及其對應的表格資料位置（如指向記錄的指標）。
  • 按 Name 鍵值排序，並形成鏈表結構以便於範圍查詢。
  • 例如：葉節點可能包含 [(Anna, 指標1), (Bob, 指標2), (Mary, 指標3), ...]。

• 內部節點：

  • 存放索引鍵值，用來引導搜索路徑，但不存放實際資料。
  • 內部節點用來分割和組織子樹，使搜索操作高效。
  • 例如：內部節點可能包含 [Anna, Bob, Mary]，指向相應的子樹。

查詢句效能分析

查詢句一： select ID from USER where Name = ‘Mary’;

• 索引有效性：
  • 該查詢使用 Name 欄位作為搜索條件，與索引欄位一致。
  • 利用 B+-tree 索引，能夠快速找到 Name 為 Mary 的位置。
  • 搜索過程：從根節點開始，通過內部節點的鍵值快速導航到包含 Mary 的葉節點，然後讀取葉節點中對應的資料指標以獲取 ID。
  • 效能提升：由於索引的存在，大大減少了需要掃描的記錄數量，從而提升了查詢效率。

查詢句二： select Name from USER where ID = ‘B001’;

• 索引有效性：
  • 該查詢使用 ID 欄位作為搜索條件，而索引是基於 Name 欄位建立的。
  • 索引不包含 ID 欄位，無法直接利用 B+-tree 索引來加速此查詢。
  • 搜索過程：需要對 USER 表進行全表掃描以找到 ID 為 B001 的記錄，然後提取 Name 欄位。
  • 效能提升：索引對此查詢無助，因為 ID 欄位不是索引的一部分，查詢效率不會因索引而提升。