目次
概要
インデックスに対してMongoDBはB Treeを採用し、MySQLのInnoDBはB+ Treeを採用しています。
どうして採用しているアルゴリズムが違うのだろう？と思って調べてみました。
主な違い
B+ TreeはほとんどB Treeと同じですが、以下の点が異なります。
・リーフノードとリーフノードを結ぶポインタがある
・データはリーフノードのみに保持する
具体例
言葉だけだと分かりにくいので、Visualizeするツールを使って具体例を表示します。
B Tree
B+ Tree
先程のB Treeと違って、データはリーフノードに持つので、途中の子ノードとリーフノードで同じキーがあることが分かります（2、5、15など）
それぞれの優位性
この画像が非常に分かりやすいです。
ref: database – Differences between B trees and B+ trees – Stack Overflow
B Tree
- 子ノードもデータを持つので、探索途中でヒットすればレスポンスが早い
B+ Tree
- リーフノードがポインタでつながっているので、範囲検索に強い（リーフノードのみ見ればいい）
- 子ノードがキーしか持たないため、ページ（ブロック）に載せられるキーが多い。つまりOrderが高くなるため、Treeの階層が少なくなり計算量が減る。
- ロジック上無理やりOrderを高くすることは出来るが、その場合複数のブロックにキーが分散して存在することになる。つまり各ブロックにアクセスするためI/Oが増え、結果的に処理が遅くなる。
MongoDBは範囲検索に強いって聞いたけど？
MongoDBはB Treeの方を採用しています。しかし先程の話だとB+ Treeの方が範囲検索に向いています。
ではなぜ範囲検索に強いと言われるのでしょうか？
シャーディングのパーティショニングが他のNoSQLと違って、RDBMSのようなレンジパーティションです。
MongoDBが範囲検索に強いと言われているのはこの分散戦略のためです。
（つまりシャードキーがクエリに入ってないケースでは別に強くない）
ソース
- database – Differences between B trees and B+ trees – Stack Overflow
- MongoDB – Tech Note
- なぜBTreeがIndexに使われているのか – maru source
- MySQL with InnoDB のインデックスの基礎知識とありがちな間違い – クックパッド開発者ブログ
- データ構造とアルゴリズム: 平衡木
投稿日：May 17th 2017
元記事：http://christina04.hatenablog.com/entry/2017/05/17/190000