use the index, luke!をよむ

序文

SQLは「どんな情報が欲しいか」と「どのようにして取得するか」が完全に分離している
そのため開発者でも「取得」の内部処理を知らないことが多い
SQLがどのようにクエリを実行するかを知らないと、パフォーマンスの問題を考えることができない
そのため、パフォーマンス上の問題を避けるためには、開発者はデータベースについて多少なりとも知っておく必要がある

すなわち、開発者が知るべき唯一のことは、 どのようにインデックスを張るか、ということになります。

???

具体的なイメージとしてはほんとにただの目次
インデックスの検索について
探す分には問題ないが、インデックス自体の更新を行おうとするとINSERTやDELETE,UPDATEをすぐに実行し、順序を保って更新を行う必要がある
データベースではこの処理をデータ構造を組み合わせることで解決している

データ構造ひとつめ
双方向連結リスト
INSERTでのデータ挿入は実質不可能（処理が遅くなるため）
そのため、メモリ上の物理的なデータの並び順とは別に、論理的な順序づけを行う
これは双方向連結リストによって実現され、テーブル内のデータの並びとインデックスは分離して管理されるため、新規のインデックスを追加する際の処理が軽くなる

データ構造ふたつめ
バランス検索木（Bツリー）
リーフノードの最大値をブランチのノードの要素とするような操作をルートノードに収まるまで続けることで、深さがどこも同じバランスのとれた検索木ができる
走査の際は検索したいインデックスと、ノードの要素の大小を比べて行くだけ

インデックスによる検索は、(1) ツリーを走査し、(2) リーフノードチェーンをたどり、(3) テーブルからデータを読み出す、という3ステップで行われます。ツリーの走査のみ、インデックスの深さによって、アクセスする ブロックの数に限りがあります。それに対して残りの2ステップでは、たくさんのブロックにアクセスする必要があるため、インデックスによる検索が 遅い原因になってしまうのです。

こんな訳でさっきまでの工夫も万全ではないと言うことがわかりましたね

クエリを遅くする一番の原因は、出来の悪い where句なのです。

刺さる