はじめに
最近とある企業の技術面接でSQLの主キーはなぜ検索が速いのかという質問を受けたのですが、その際に全く答えられなかったので調べてみました。
SQLについてあまり詳しくないという方の助けになれば幸いです。
対象読者
- SQLについてあまり詳しくない方
私のSQLレベルとしては、DockerでPostgresサーバーを立てて、Nextjsで書かれたフロントからAPI経由でデータを取得する程度です。
SELECTやWHEREなど基本的なクエリは書けますが、EXISTSやHAVINGなどは勉強中です。
主キーとインデックスって同じもの?
これについてMySQLとSQL Serverのドキュメントを見てみると、以下のように書かれています。(こちらに関して主キー制約とインデックスの話 - Qiitaを非常に参考にさせていただきました)
MySQL
テーブル上で PRIMARY KEY を定義すると、InnoDB ではそれがクラスタ化されたインデックスとして使用されます。 作成するテーブルごとに主キーを定義します。 論理的に一意で、Null 以外のカラムまたはカラムのセットが存在しない場合は、自動的に値が入力される新しい自動インクリメントカラムを追加します。
15.6.2.1 クラスタインデックスとセカンダリインデックス - MySQL 8.0 リファレンスマニュアル
SQL Server
テーブルにクラスター化インデックスがある場合、またはインデックスがインデックス付きビューにある場合は、行ロケーターが行のクラスター化インデックス キーになります。
非クラスター化インデックスのアーキテクチャ - SQL Server 2022
結論
- MySQLのドキュメントからPRIMARY KEYから自動的にクラスタ化されたインデックスが作成されることがわかります。
- そして、SQL Serverのドキュメントからクラスター化インデックスがある場合、行ロケーターが行のクラスター化インデックス キーになることがわかります。
- 従って、主キーとインデックスは異なるものでありますが、主キーを定義するとインデックスが自動的に作成されるため、使用者はそれらの違いを意識する必要はないと考えられます。
インデックスがあるとなぜ検索が速いのか
主キーとインデックスの違いを整理できたところで、インデックスがあるとなぜ検索が速いのかについて勉強したので解説します。
空間インデックスを除き、InnoDB インデックスは B-tree データ構造です。
15.6.2.2 InnoDB インデックスの物理構造 - MySQL 8.0 リファレンスマニュアル
上にある引用文からわかるように、インデックスはB-treeデータ構造であるとのことです。
そして、B-treeは2分木のようなものですが、ノードが持つことのできる子ノードが2個以上でも良いため、2分木に比べて高さが低くなり、高速に検索することが可能となります。
具体的には、計算量がおよそO(logN)となるため、データ量が増えても計算速度を高速に保つことができます。
おわりに
簡単にではありますが、主キーとインデックスの違いについて説明しました。
この話題について調べる中で自身のSQLに対する知識のなさを痛感したため、今後もコツコツ勉強していきたいと思います。