MySQL B+Tree インデックスのストレージとクエリ

先に商品テーブルを作成します。id は主キーです（主キーが指定されていない場合、最初の NULL 値を含まない一意の列がクラスター化インデックスのインデックスキーとして選択されます）：

CREATE TABLE `product` (
  `id` int NOT NULL,
  `product_no` varchar(20) DEFAULT NULL,
  `name` varchar(255) DEFAULT NULL,
  `price` decimal(10,2) DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci ROW_FORMAT=DYNAMIC;

INSERT INTO product (id, product_no, name, price) VALUES
(1, 'P001', '商品1', 10.00),
(2, 'P002', '商品2', 20.00),
(3, 'P003', '商品3', 30.00),
(4, 'P004', '商品4', 40.00),
(5, 'P005', '商品5', 50.00),
(6, 'P006', '商品6', 60.00),
(7, 'P007', '商品7', 70.00),
(8, 'P008', '商品8', 80.00),
(9, 'P009', '商品9', 90.00),
(10, 'P010', '商品10', 100.00);

行データ：

上記の挿入された行データは、B+Tree インデックスに保存されると次のようになります：

B+Tree は、葉ノードにのみデータを格納し、非葉ノードにはインデックスのみを格納します。また、各ノードのデータは主キーの順序で格納されます。各親ノードのインデックス値は、下位の子ノードのインデックス値に表示されるため、葉ノードにはすべてのインデックス値情報が含まれ、各葉ノードには次の葉ノードと前の葉ノードを指す 2 つのポインタがあり、双方向リンクリストを形成します（下の葉ノードの画像は単方向リンクリストですが、実際には双方向です。画像に誤りがあります）。

主キーインデックスの B+Tree

主キーを使用して商品データをクエリするプロセス#

たとえば、次のクエリを実行します：

select * from product where id= 5;

このクエリは、主キーインデックスを使用して id が 5 の商品をクエリします。クエリのプロセスは次のようになります。B+Tree はトップダウンで階層ごとに検索を行います：

5 をルートノードのインデックスデータ（1、10、20）と比較し、5 は 1 と 10 の間にあるため、B+Tree の検索ロジックに従って、2 番目の階層のインデックスデータ（1、4、7）を見つけます。
2 番目の階層のインデックスデータ（1、4、7）で検索を行います。5 は 4 と 7 の間にあるため、3 番目の階層のインデックスデータ（4、5、6）を見つけます。
葉ノードのインデックスデータ（4、5、6）で検索を行い、id 値が 5 の行データを見つけます。

データベースのインデックスとデータはすべてディスクに保存されます。ノードの読み取りはディスク I/O 操作としてカウントされます。したがって、上記のクエリプロセス全体では、3 つのノードを経験し、つまり 3 回の I/O 操作が行われます。

B+Tree は、数千万のデータを格納するために 3〜4 層の高さが必要です。つまり、数千万のテーブルから目標のデータをクエリするために最大で 3〜4 回のディスク I/O が必要です。そのため、B+Tree は B ツリーやバイナリツリーと比較して、クエリ効率が非常に高いという最大の利点があります。

二次インデックスを使用して商品データをクエリするプロセス#

主キーインデックスの B+Tree と二次インデックスの B+Tree の違いは次のとおりです：

主キーインデックスの B+Tree の葉ノードには実際のデータが格納されます。すべての完全なデータレコードは、主キーインデックスの B+Tree の葉ノードに格納されます。
二次インデックスの B+Tree の葉ノードには主キー値が格納されますが、実際のデータではありません。

product テーブルの product_no（商品コード）フィールドを二次インデックスとして設定します：

CREATE UNIQUE INDEX product_product_no_IDX USING BTREE ON test.product (product_no);

その B+Tree は次のようになります（下の葉ノードの画像は単方向リンクリストですが、実際には双方向です。画像に誤りがあります）：

非葉ノードのキー値は product_no です（オレンジの部分）、葉ノードには主キー値が格納されます（緑の部分）。

product_no 二次インデックスを使用して商品をクエリします：

select * from product where product_no = '0002';

まず、二次インデックスの B+Tree のインデックス値（商品コード、product_no）をチェックし、対応する葉ノードを見つけて主キー値を取得し、次に主キーインデックスの B+Tree を使用して対応する葉ノードをクエリし、行データを取得します。このプロセスは「リバース」または「カバリングインデックス」と呼ばれ、データを検索するために 2 つの B+Tree を検索する必要があることを意味します。以下の図を参照してください（下の葉ノードの画像は単方向リンクリストですが、実際には双方向です。画像に誤りがあります）：

ただし、クエリするデータ（主キーのみをクエリ）が二次インデックスの B+Tree の葉ノードで見つかる場合、主キーインデックスを検索する必要はありません。次のクエリ文のような場合です：

select id from product where product_no = '0002';

二次インデックスの B+Tree だけで結果をクエリできるプロセスを「カバリングインデックス」と呼びます。

MySQL InnoDB がなぜ B+Tree をインデックスのデータ構造として選択したのか？#

1. B+Tree vs B ツリー#

B+Tree は葉ノードにのみデータを格納し、B ツリーは非葉ノードにもデータを格納します。そのため、B+Tree の単一ノードのデータ量はより小さくなり、同じディスク I/O 回数でより多くのノードをクエリできます。

さらに、B+Tree の葉ノードは双方向リンクリストで接続されており、MySQL の一般的な範囲ベースの順序検索に適していますが、B ツリーではこれを実現できません。

2. B+Tree vs 二分木#

N 個の葉ノードを持つ B+Tree の検索複雑度はO(logdN)です。ここで、d はノードが許容する最大の子ノード数です。

実際のアプリケーションでは、d の値は 100 以上であるため、データが数千万に達しても、B+Tree の高さは依然として 3〜4 層程度に保たれます。つまり、データのクエリ操作はディスク I/O 操作を 3〜4 回行うだけで目標のデータをクエリできます。

一方、二分木の各親ノードの子ノード数は 2 つしかないため、検索複雑度はO(logN)です。これは B+Tree よりもはるかに高いため、二分木で目標のデータを検索するために経験するディスク I/O 回数はより多くなります。

3. B+Tree vs ハッシュ#

ハッシュは等値クエリの場合に非常に高速で、検索複雑度は O (1) です。

ただし、ハッシュテーブルは範囲クエリには適していません。ハッシュテーブルは等値クエリに適しており、そのため B+Tree インデックスはハッシュテーブルインデックスよりも広範な使用シナリオに適しています。