B-treeとデータベースインデックスの仕組み：効率的なデータ検索の基礎技術
本記事は、データベース管理システム（DBMS）の根幹をなすデータ構造であるB-treeと、その改良版であるB+treeについて詳細に解説している。B-treeは、キーと値のペアを「木構造」に格納し、効率的なデータ検索を可能にする。この構造は、ノード（節）と子ポインタ（接続線）で構成され、各ノードは特定の順序付けられたキー/値ペアを保持する。検索時にはルートノードから開始し、目的のキーが挿入されるべき位置をたどりながら、各レベルで一度のノード訪問で検索を完了できるため、非常に高速である。
B-treeが特に優れているのは、大量のデータを長期保存するディスク（HDD/SSD）での利用に適している点である。なぜなら、各ノードのサイズをディスクブロック（例：16KB）に合わせることができ、これによりノードの読み書きが効率的だからである。例えば、16KBのブロックを前提とすると、3レベルのツリーで3億以上のキー/値ペアを格納できる計算になる。
しかし、多くのデータベースインデックスは「B+tree」というより洗練されたバリアントを使用する。B+treeは、キー/値ペアをリーフノード（最下層のノード）にのみ格納し、非リーフノードにはキーと子ポインタのみを格納するというルール変更が加えられている。これにより、非リーフノードに値の格納が不要となり、より多くのキーを詰め込むことができ、ツリーをより浅く保つことができる。さらに、すべての値が同じレベル（リーフ）にあり、これらが「次」と「前」のポインタを持つ二重リンクリストとして走査できる点が大きな利点である。
世界で最も普及しているDBMSの一つであるMySQLのInnoDBエンジンは、B+treeを全面的に利用し、テーブルの全データをB+tree構造で格納する。この際、ユーザーが指定した主キー（PRIMARY KEY）がツリーのキーとなり、残りの列の値が値としてリーフノードに格納される。二次インデックス（Secondary Index）も同様にB+treeとして構築され、検索時には二次インデックスのB+treeで検索し、得られた主キーを使ってメインテーブルのB+treeで最終的なデータ検索を行うという二段階のプロセスを経る。したがって、クエリの実行速度を最大化するためには、主キーの選択が極めて重要となる。特に、ランダムなUUIDv4を主キーとして使用した場合、挿入時に訪問するノードが予測不可能になり、パフォーマンスに悪影響を及ぼす可能性があることが示唆されている。
背景
B-treeは、コンピュータサイエンスにおける基本的なデータ構造の一つであり、特に大量のデータをディスク（永続ストレージ）に保存し、高速に検索・管理するために設計されました。データベースのインデックス構造の基礎を築き、データの検索効率を劇的に向上させました。B+treeは、このB-treeの欠点を補い、データベースの要求に特化して最適化されたバージョンです。
重要用語解説
- B-tree: キーと値のペアを格納する木構造のデータ構造。ノードのサイズをディスクブロックに合わせることで、ディスクI/Oを最小限に抑え、高速なデータ検索を実現する。
- B+tree: B-treeを改良したデータ構造。値（データ本体）をすべて最下層（リーフノード）に集約し、非リーフノードをポインタのみにすることで、ツリーの深さを浅く保ち、検索効率を最大化する。
- インデックス: データベースにおいて、特定のデータ（列）を検索しやすくするために作成される構造。B+treeがこのインデックスの主要な実装技術として使用される。
今後の影響
この技術は、現代のあらゆる大規模データベースシステムの根幹を支えている。主キーの設計（特にUUIDの使用）は、データベースの挿入性能やクエリの実行速度に直接影響を与えるため、システム設計において極めて重要な考慮事項となる。適切なインデックス設計は、アプリケーションのパフォーマンスを決定づける。