B+Treeで理解するMySQLインデックスの基礎

はじめに
インデックスとは
二分探索木
B-Treeの構造を見ていく
B+Treeの構造を見ていく
インデックスの種類
- クラスター化インデックス
- 非クラスター化インデックス
最後に
参考文献

はじめに

　こんにちは、ｉｉｍｏｎエンジニアのみやこしです、業務の中でSQLを扱う機会が多く、勉強を進めるうちに INDEXの構造にとても興味を持ちました。今回は、MySQLのINDEXである B+treeの基本的な構造について紹介したいと思います。

インデックスとは

　インデックス（Index）とは、データベースのテーブルに対して検索を高速化するための仕組みです。本でいう「目次」や「索引」のような役割を持ち、テーブルの中から目的の行を効率よく探し出せるようにします。MySQLのインデックスはデータベースエンジンのInnoDBで実現して、主に B+Tree が使われています。

二分探索木

インデックスを理解するうえで「二分探索木」の基本について少し紹介します。二分探索木は下記の図のように、各ノードが最大で2つの子ノード（左と右）を持つ木構造で、探索するときは「大小比較」で辿るだけなので効率的です。

しかし昇順だけを順番に入れていくと、ただの線形リストみたいになり、効率が落ちます。二分探索木を詳しく知りたい方は下記の記事を参考にしてみてください！

tech.iimon.co.jp

B-Treeの構造を見ていく

B-Treeインデックスは、二分探索木のアイデアを発展させたものになります。 B-Treeは、ルートノード（木の一番上にあり必ず存在する）、内部ノード（途中にあり検索の分岐点となる）、リーフノード（葉）（一番下にあり子を持たない）という3種類のノードで構成されています。

各ノードにはキーとポインタが含まれます。

キーは昇順に並んでおり、データを格納しています。
ポインタは子ノードへの参照を保持します。

下記の図は最大次数（max-degree）が5のB-treeを例にしています（各ノードは最大4つのキーと5つのポインタを持てます）

※緑の部分はデータ、青の部分はキーになります。

B-Tree では、データの追加や削除が行わらたとき、分割やマージが発生します。これはB-Tree のバランスを保ち、効率的な検索をできるようにしています。

※最大次数（max-degree）が4のB-tree ノードが最大容量に達した場合に分割が発生します。

※データ333を探す時

このように、B-Treeは1つのノードに複数のキーとポインタを格納できるため、二分探索木よりも木の高さを低く抑えることができます。探索は「ノード内のキーを比較し、範囲に応じて子ノードへ移動する」という処理を繰り返して行われます。さらに、葉ノードはすべて同じ高さに揃っているため、探索時間は常に一定に保たれるというメリットがあります。

B+Treeの構造を見ていく

B+Tree は、 B-Treeをさらに発展させたものになります。具体的な違いを見ていきましょう。

※緑の部分はデータになります。

B-treeのすべてのノード（内部ノード & 葉ノード）にデータ（キーと値）が格納されるに対してB+Tree は葉ノードにのみ格納されます。そのため、探索の処理は必ず葉ノードまで進み、動作がシンプルかつ一定時間で完了します。(キー29が内部ノードに存在する時、同じキー29が必ず葉ノードにも存在する)
内部ノードにはデータを格納せずキーだけを持つため、1ノードあたりにより多くのキーを収容できます。その結果、木の高さを抑えられ、大量データでも少ないステップで探索が可能です。
葉ノード同士が連結リストでつながっているため、ある値を見つけたあとは横にたどるだけで効率よく範囲検索できます。

※B+treeの分割とマージ

※データ211を探す時

SQLの BETWEENなどが最適です。例えば下記のSQLでは39〜62の範囲検索になります。

SELECT * 
FROM students
WHERE score BETWEEN 38 AND 62;

B+Treeインデックスでの処理の流れ

B+Tree のルートノードから探索を始め、38 以上の最初の値までたどり着きます。
次はリーフノードの連結リストを横にスキャンします。リーフノードにはデータが昇順で並び、さらにノード同士が連結されているので、38の位置から、次のノードへ、さらに次のノードへと順にたどるだけで 62 を取得できます。
62を超えた時点で終了します。

上記の検索B-treeだとデータが異なるノードに分散されているため、個別でノードを検索するので、「木をたどり直す」必要があります。