概要
インデックスに対してMongoDBはB Treeを採用し、MySQLのInnoDBはB+ Treeを採用しています。
どうして採用しているアルゴリズムが違うのだろう？と思って調べてみました。
主な違い
B+ TreeはほとんどB Treeと同じですが、以下の点が異なります。
- リーフノードとリーフノードを結ぶポインタがある
- データはリーフノードのみに保持する
具体例
言葉だけだと分かりにくいので、Visualizeするツールを使って具体例を表示します。
[1, 2, 3, 4, 5, 6, 8, 10, 15, 18]という数列に対し、Order: 3で作ってみます。
Orderは１ノードから出る枝の数のことです。
B Tree
B+ Tree
先程のB Treeと違って、データはリーフノードに持つので、途中の子ノードとリーフノードで同じキーがあることが分かります（2、5、15など）
また、末端のリーフノードたちはポインタで結ばれています。
それぞれの優位性
この画像が非常に分かりやすいです。
ref: database - What are the differences between B trees and B+ trees? - Stack Overflow
B Tree
- 子ノードもデータを持つので、探索途中でヒットすればレスポンスが早い。つまり等価条件の探索が向いている。
B+ Tree
- リーフノードがポインタでつながっているので、範囲検索に強い（リーフノードのみ見ればいい）
- 子ノードがキーしか持たないため、ページ（ブロック）に載せられるキーが多い。つまりOrderが高くなるため、Treeの階層が少なくなり計算量が減る。
- ロジック上無理やりOrderを高くすることは出来るが、その場合複数のブロックにキーが分散して存在することになる。つまり各ブロックにアクセスするためI/Oが増え、結果的に処理が遅くなる。
MongoDBは範囲検索に強いって聞いたけど？
MongoDBはB Treeの方を採用しています。しかし先程の話だとB+ Treeの方が範囲検索に向いています。
ではなぜ範囲検索に強いと言われるのでしょうか？
MongoDBのシャーディングのパーティショニングは他のNoSQLのConsistent Hashingではなく、RDBMSのようなレンジパーティションです。
MongoDBが範囲検索に強いと言われているのはこの分散戦略のためです。
（逆に言えばシャードキーを範囲検索のクエリとして使わないケースでは別に強くない、ということになります）
