SQL Serverのindexの仕組みについて

B-treeについて

• SQL Server のインデックスはB-tree（B木）
  • 厳密には B+tree
    • 葉ノードに実データを含めることができる
    • 隣接する葉ノード同士がポインタで繋がっている
  • 他の DBMS も B-tree/B+tree が多い
    • MySQL
    • PostgreSQL（Hash とかも選択できるっぽい）
    • Oracle（他も選択できるっぽい）
• B-tree は二分探索木を一般化（N分に）したもの
  • 二分探索木 - Wikipedia
    • https://www.momoyama-usagi.com/entry/info-algo-tree
  • 三分探索木 - Wikipedia
  • B-tree = N分探索木（N >= 2）
    • ハードディスクの読み取り回数を減らすために、二分探索木よりB-treeのほうが都合が良い
      • なぜBTreeがIndexに使われているのか
    • SQL Serverの場合、各ブロックは「Page」（8kb）
• B-treeに値を追加／削除するイメージ
  • B木の基礎を学ぶ

SQL Serverのインデックスの種類

• クラスタ化インデックス
  • インデックスのリーフノードに実レコードが含まれるもの
    • つまり、レコードをテーブルにどういう順で格納しておくか
  • テーブルにつき最大1つ
    • PKを指定なしで作ればデフォルトでクラスタ化インデックスになる
• 非クラスタ化インデックス
  • インデックスのリーフノードにはレコードへのポインタを格納するもの
  • テーブルごとに何個でも作れる
  • 検索時は、非クラスタ化インデックスで目的のリーフノードを見つけた後に、（必要があれば）レコードへのポインタ（※）を使って改めてテーブルからレコードを検索する必要がある
    • クラスタ化インデックスがあればそのキー（普通はPK）をポインタとして使うっぽい
    • クラスタ化インデックスがなければRIDを使う？
• カバリングインデックス
  • 非クラスタ化インデックスで検索したあとに実レコードにアクセスさせずに済むように、インデックスのキーに必要な列をすべて入れておくというメソッド
    • サイズがでかくなるので、普通は次項の付加列インデックスを使う
• 付加列インデックス
  • リーフノードにのみ任意の列を追加できる
  • カバリングインデックスの改善版

参考）SQL Serverのインデックスの理解を深める

• 実際にどのインデックスを使って検索するかは、SQL Serverがよしなに判断する
  • 期待通りになっているかどうかは実行プランを見て確認する必要あり
    • SSMS で Include Actual Execution Plan
• 非クラスタ化インデックスのキーによる検索時、非クラスタ化インデックスで検索 → クラスタ化インデックスからレコード取得 になるかと思いきや、最初からクラスタ化インデックスで実レコードを探すほうが効率が良いと判断される場合もある

インデックスの断片化

• インデックスへの値の追加・削除により断片化が生じる
• 断片化率は sys.dm_db_index_physical_stats により確認
• 再構築ではインデックス全体を、再構成ではリーフノードのみを最適化する
  • Microsoft のドキュメントには、基本的に再構成を優先するとある
    • クエリのパフォーマンスを向上させてリソースの消費を削減するためにインデックスのメンテナンスを最適化する
    • かつては、断片化率が30%以下なら再構成、という指針だった？
      • https://techblog.zozo.com/entry/sqlserver-index-reorganize-vs-rebuild

参考）SQL Serverにおけるインデックスの再構成と再構築の性能比較