🦮

【MySQL】InnoDBのB+ treeインデックスの深掘りまとめ

に公開
MySQL
index
InnoDB
tech

はじめに

MySQLのデフォルトのストレージエンジンである InnoDB は、インデックスの管理に B+ tree を使用しています。

本記事では、まず InnoDB における B+ tree インデックスの概要について整理します。その後、クラスタインデックスとセカンダリインデックスの仕組みや、それぞれのデータ検索フローを解説した上で、 B+ tree インデックスのメリット・デメリットも取り上げます。

B+ treeの特徴

B+ tree は一般的に以下のような特徴を持つデータ構造です。

  1. 内部ノードはキーのみを持ち実データを持たない
  2. 葉ノードのみが実データを持つ
  3. 葉ノードは連結リストを構成する
  4. 平衡木
    → 常にO(logN)で検索・追加・削除が可能

B-treeとの違いは、葉ノードでのみ実データを保持すること、葉ノード間がポインタで連結されることです。


次数 3の B+ tree

B+ Tree Visualization


次数 3の B-tree

B-Tree Visualiztion

InnoDBのB+ treeインデックス構造

B+ tree のデータ構造としての特徴は先の通りですが、その実装はデータベースやストレージエンジンによって大きく異なります。ここでは、「InnoDB の B+ tree インデックス構造」ということで、InnoDB が B+ tree を用いてどのようにインデックスを管理しているのかを見ていきます。

各ページ内の構造

各ページ内のすべてのレコードは次のレコードへのポインタを持ち、単方向リストを形成します。単方向リストの先頭はInfimumと呼ばれるレコードで、その後キー値の昇順でレコードが並び、末尾にSupremumと呼ばれるレコードがきます。

Infimumは、ページ内の全レコードよりも小さいキー値を持ち、Supremumはページ内の全レコードより大きいキー値を持ちます。これにより、ページ内の各レコードを昇順に辿ることができます。

葉ページの具体的な構造が以下です。
葉ページは、キー値に加えて、実際のレコードデータも保持します。

葉ページの構造

内部ページも基本的には同じ構造ですが、以下の2点が異なります。

  1. キー値ではなく、子ページが持つ最小のキー値を持つ
  2. 実データではなく、子ページの番号を持つ


内部ページの構造

同階層のページ構造

同階層のページは以下のように、双方向リストで連結されます。


同階層のページ

これにより、B+ treeは範囲検索を高速に行うことができます。具体的には、Key >= 3のレコードを取得したい場合に、葉ページ間の双方向リストを辿ることで効率的な範囲検索が可能です。

B+ treeインデックスの全体構造

B+ tree の全体構造を示すために、まずexamplesテーブルを作成します。

CREATE TABLE examples (
  id INT NOT NULL,
  c1 INT NOT NULL,
  c2 INT NOT NULL,
  PRIMARY KEY(id)
) ENGINE=InnoDB;

INSERT INTO examples (id, c1, c2)
  VALUES (0, 8, 16), (1, 3, 6), (2, 5, 10), (3, 6, 12), (4, 2, 4), (5, 7, 14), (6, 1, 2), (7, 4, 8);

作成されたテーブルが以下です。

id (PK) c1 c2
0 8 16
1 3 6
2 5 10
3 6 12
4 2 4
5 7 14
6 1 2
7 4 8

このexamplesテーブルの主キーidは、後述のクラスタインデックスとして B+ tree で管理されます。その B+ tree の全体構造が以下になります。


B+ treeインデックスの全体構造

クラスタインデックス

InnoDB の各テーブルはクラスタインデックスと呼ばれる特別なインデックスを一つだけ持っています。↓の引用にもあるように、多くの場合クラスタインデックス = 主キーと考えても問題なさそうです。
（厳密には、テーブルに主キーを定義してない場合、InnoDB は NOT NULL かつ UNIQUE キーのついたカラムをクラスタインデックスとして使用します。NOT NULL かつ UNIQUE なカラムが存在しない場合は、 InnoDB が自動でクラスタインデックスを生成します。ただし、開発者が常に主キーを明示的に定義することが推奨されています。）

Each InnoDB table has a special index called the clustered index that stores row data. Typically, the clustered index is synonymous with the primary key.
17.6.2.1 Clustered and Secondary Indexes

クラスタインデックスは B+ tree で実装されており、葉ページには実際のレコードデータが格納されています。以下再掲。


B+ tree（クラスタインデックス）

クラスタインデックスでの実際のデータ検索フローが以下になります。主キーid = 3を持つレコードデータの取得を考えます。

SELECT * FROM examples WHERE id = 3;


クラスタインデックスでのデータ検索

詳細:
The physical structure of records in InnoDB > Clustered indexes

セカンダリインデックス

クラスタインデックス以外のインデックスをセカンダリインデックスと呼びます。

先ほども使用したexamplesテーブルの c1 カラムにインデックスを張るケースを考えます。

CREATE TABLE examples (
  id INT NOT NULL,
  c1 INT NOT NULL,
  c2 INT NOT NULL,
  PRIMARY KEY(id),
  KEY (c1) -- c1 カラムにインデックスを張る
) ENGINE=InnoDB;

INSERT INTO examples (id, c1, c2)
  VALUES (0, 8, 16), (1, 3, 6), (2, 5, 10), (3, 6, 12), (4, 2, 4), (5, 7, 14), (6, 1, 2), (7, 4, 8);

examplesテーブルが以下です。

id (PK) c1 (Idx) c2
0 8 16
1 3 6
2 5 10
3 6 12
4 2 4
5 7 14
6 1 2
7 4 8

c1 カラムにはセカンダリインデックスが作成され、クラスタインデックスと同様に B+ tree で管理されます。ただし、葉ページに格納されるデータが異なります。

セカンダリインデックスの葉ページには、

  • インデックスキー（ここでは c1 の値）
  • 対応するレコードの主キー値（クラスタインデックスへのポインタとして機能）

の2つが格納されます。


B+ tree（セカンダリインデックス）

InnoDB では、実際のレコードデータ（主キー以外のカラム値）はクラスタインデックスにのみ格納されるため、セカンダリインデックスからレコードを取得する際は、葉ページで得た主キー値を使ってクラスタインデックスを検索します。

実際のデータ検索フローが以下になります。c1 = 5のレコードを取得するケースを考えます。

SELECT * FROM examples WHERE c1 = 5;


セカンダリインデックスでのデータ検索

詳細:
The physical structure of records in InnoDB > Secondary indexes

B+ treeインデックスのメリット・デメリット

メリット

  • クラスタインデックスの葉ページに主キーの昇順でテーブルデータが格納されるため、主キーでのデータ検索が高速
  • クラスタインデックスは主キーの昇順になっているため、範囲検索に強い
  • ソートキーにインデックスを張ることで、クエリ時のソート処理が不要になる
  • カバリングインデックスの恩恵
    → c1 カラムで id（主キー）をクエリする場合、セカンダリインデックスが主キーを持つためクラスタインデックスを調べる必要がなくなる。

パフォーマンスを意識したインデックス設計については MySQL with InnoDB のインデックスの基礎知識とありがちな間違い が参考になりそうです。

デメリット

  • 主キーのデータサイズが大きいと、セカンダリインデックスが肥大化する（セカンダリインデックスも主キーを持つため）
  • セカンダリインデックスでのデータ検索には2回のルックアップが必要（セカンダリインデックス → クラスタインデックス）
  • UUID v4やランダム文字列を主キーにする場合、INSERT 時のパフォーマンスが劣化する

最後の点についてですが、AUTO INCREMENT や時刻などのシーケンシャルな主キーを使用する場合は、クラスタインデックスの右端のリーフページに INSERT が行われるためバッファプールのキャッシュが効きやすいです。しかし、ランダムな主キーを使用する場合、挿入位置が B+ tree 内でランダムになるためバッファプールでのキャッシュミスが頻発し、その度に挿入対象のページをディスクから読み込む必要があるため性能が劣化します。MySQLでプライマリキーをUUIDにする前に知っておいて欲しいこと が参考になりそうです。

参照

B+Tree index structures in InnoDB - Jeremy Cole
The physical structure of InnoDB index pages - Jeremy Cole
The physical structure of records in InnoDB - Jeremy Cole
The basics of InnoDB space file layout - Jeremy Cole
Efficiently traversing InnoDB B+Trees with the page directory - Jeremy Cole
Understanding InnoDB clustered indexes - Ovais Tariq
15-445/645 Database Systems (Fall 2022) 08 B+ Tree Indexes - CMU

15.6.2.1 クラスタインデックスとセカンダリインデックス - MySQL
MySQL with InnoDB のインデックスの基礎知識とありがちな間違い - cookpad Developers Blog
MySQLでプライマリキーをUUIDにする前に知っておいて欲しいこと - RACCOON TECH BLOG

Discussion