🐬
MySQLのインデックスにおけるB+木
MySQLのインデックスは、B+木と呼ばれるデータ構造に基づいて構築されています。B+木は、データの効率的な検索と挿入・削除を実現するデータ構造です。
B+木の構造
B+木は以下の特徴を持つ木構造です。
- すべてのノードは、キー値と子ノードへのポインタを持つ。
- 各ノードは、最大M個の子ノードを持つ。
- すべてのリーフノードは同じ高さである。
- リーフノードには、データへのポインタも含まれる。
B木の例
[23][71][-][-]
[ ] [ ] [ ] [/] [/]
/ \ \
x<23 / \ \
/ \ \ 71<x
/ 23<x<71 \ \
/ \ \
[8][11][19][-] [33][44][56][57] [75][92][-][-]
[/][/][/][/][/] [/][/][/][/][/][/] [/][/][/][/][/][/]
B+木の利点
B+木は、以下の利点を持つデータ構造です。
- 検索速度が速い：B+木は、対数時間でデータの検索を行うことができます。
- 挿入・削除が速い：B+木は、常に平衡状態を保っているため、挿入・削除処理を効率的に実行できます。
- ディスク容量の効率的な利用：B+木は、リーフノードにのみデータを格納するため、ディスク容量を効率的に利用できます。
B+木とMySQLインデックス
MySQLでは、B+木をベースとしたインデックスが利用されています。
- インデックスツリー：B+木を使用して構築されるデータ構造。
- リーフノード：データレコードへのポインタを格納する。
- 中間ノード：インデックスツリーの枝分かれを管理する。
MySQLは、インデックスツリーを辿ることで、特定のデータレコードを効率的に検索することができます。
関連記事
MySQLのインデックスとは？
Discussion