B+Treeインデックスに関してよく出る言葉の正誤とその解説

お決まり

はじめに

  • B+Treeインデックスって意外とちゃんと知られてないなぁという印象があり、ふと考えた所具体例が意外と出てないので理解されにくいのではないかと仮説を立ててみたので用意してみた次第です。
  • 新しい技術とか書きたくなるのですが、たまにはこういう基礎系もいいよね。
    • そろそろ社会人エンジニア歴5年目になるので、後輩に向けて書くという側面も持ってます(予防線)

B+Treeインデックス?

①「主キーで検索することが最も速い」

  • 例えば以下の様なテーブルがあったとします。
CREATE TABLE `users` (
  `id`          int(11)     NOT NULL AUTO_INCREMENT,
  `name`        varchar(32) NOT NULL,
  `created_at`  int(11)     NOT NULL,
  `updated_at`  int(11)     NOT NULL,
  PRIMARY KEY (`id`),
  KEY `created_at` (`created_at`)
)
id name created_at updated_at
1 AAAA 1481100000 1481600000
2 BBBB 1481100000 1481700000
3 CCCC 1481200000 1481800000
4 DDDD 1481300000 1481900000
5 EEEE 1481400000 1482000000
6 FFFF 1481500000 1482100000

同じ1件を取得するときの動作の違いを比較する

1. PRIMARY KEYでの検索
SELECT * FROM users WHERE id = 4;

f:id:gotyoooo:20161219210936p:plain

  • ここで重要なのはレコードデータはPRIMARY KEYインデックスのリーフノードに紐付いているということ
2. SECONDARY KEYでの検索
SELECT * FROM users WHERE created_at = 1481300000;
  • ここで重要なのはSECONDARY KEYインデックスにはPRIMARY KEYが紐付いているということ

f:id:gotyoooo:20161219213203p:plain

結論

  • 図を見て分かる通り「主キーで検索することが最も速い」は正しい
  • SECONDARY KEYインデックスにはPRIMARY KEYが紐付いているため、内部では最終的にPRIMARY KEYによる探索が入るため

②「SELECT *が遅い」

  • ①のテーブルでSELECT id,created_at FROM users WHERE created_at = 1481300000; のようにSECONDARY KEYで検索をかけたとします
  • すると必要なデータがSECONDARY KEYインデックスのみで完結するため、COVERING INDEXとなりPRIMARY KEYによる探索がかかりません。 f:id:gotyoooo:20161219220555p:plain

結論

  • SELECT *が遅い」は正しい。
  • だがしかし、今回の例でnameやupdated_atのINDEXが貼られていないカラムのデータを必要とする場合は、「*」でも 「id,name,created_at」のように直接指定しても探索手法は変わりません。

③「インデックスを貼るとINSERT/UPDATE/DELETEが遅くなる」

  • 先程の①で利用したブランチノード・リーフノードは以下のようになっているとします。 f:id:gotyoooo:20161220134422p:plain
  • ココに次のレコードをINSERTしたとすると、かなりざっくりかつイメージですが以下のようなロジックでインデックスの更新が入ります。
    • あとに入ったレコードのcreated_atが最大値になることとかないかと思いますが、今回は説明のためなのでご容赦ください。
    • 実際にはありえませんが、ブランチノードの容量は3つで一杯になるとして話をすすめます。
id name created_at updated_at
7 GGGG 1481450000 1481450000

f:id:gotyoooo:20161220143138p:plain

PRIMARY KEYインデックスの更新

f:id:gotyoooo:20161220144015p:plain

SECONDARY KEY(created_at)インデックスの更新

f:id:gotyoooo:20161220144913p:plain

結論

  • 今回は2つインデックスがあったので上記2つの更新が入ります。
  • インデックスが増えれば増えるほどこの更新数が増えるため「インデックスを貼るとINSERT/UPDATE/DELETEが遅くなる」は正しい
  • 定期的にそのインデックスは本当に利用されているかを見ることが重要ですね。

最後に

  • 今回は3つ書きましたが、他にも「フルテーブルスキャンは悪」とか色々あるのでまた書きます。
  • 結局はちゃんと知ることと、改善が重要なわけです。
  • SQLアンチパターン 12章にも書かれていますがMENTORの原則が重要です。お忘れなきよう
    • Measure(測定)
      • スロークエリログとか取ろうね。
    • Explain(解析)
      • EXPLAIN 構文叩いて実行計画ちゃんと見ようね。
    • Nominate(指名)
      • 実行計画見るなりして修正方法考えようね。
    • Test(テスト)
      • 修正して実行して改善されているか確認しようね。良くなるまでMENを回そうね。
    • Optimize(最適化)
      • インデックスの容量を見て、できるだけキャッシュにのせようね。
    • Rebuild(再構築)
      • WindowsデフラグツールみたいにインデックスもOPTIMIZE TABLEとかでメンテナンスしようね。

アドベントカレンダーのお決まり