B木 とは？

二分木は1ノードに1キー・2つの子ノード。B木は1ノードに数百〜数千のキーと子ノードを持てる。木の高さがB木だと3〜4段で数百万レコードをカバーできる。ディスクから読み込む回数=木の高さだから、B木は3〜4回のディスクI/Oで目的のデータを見つけられるんだよ

メモリアクセスは数十ナノ秒、ディスクアクセス（SSDでも）は数百マイクロ秒。約1万倍の差がある。B木は1回のディスクI/Oで多くのキーをまとめて読み込むから、ディスクアクセス回数を最小化できる。1ノードのサイズをディスクブロックサイズ（通常4KB〜16KB）に合わせるのが効率的なんだよ

B木は全ノードにデータを持つ。B+木はリーフノード（最下段）だけにデータを持ち、内部ノードはキーのみ。B+木のメリットは①内部ノードにキーを詰め込めるから木がさらに低くなる、②リーフノードがリンクリストで繋がっているから範囲検索（WHERE age BETWEEN 20 AND 30）が高速。RDBMSのインデックスはほぼB+木だよ

CREATE INDEX idx_age ON users(age);と書くと、age列の値をキーとしたB+木が作られる。WHERE age = 25のクエリは、B+木を3〜4段たどるだけで該当行のポインタを取得できる。インデックスなしだとテーブル全行をスキャン（Full Table Scan）する必要がある。100万行のテーブルなら、3回vs100万回の比較の差だよ