読者です 読者をやめる 読者になる 読者になる

Carpe Diem

備忘録。https://github.com/jun06t

B TreeとB+ Treeの違い

概要

インデックスに対してMongoDBはB Treeを採用し、MySQLInnoDBはB+ Treeを採用しています。
どうして採用しているアルゴリズムが違うのだろう?と思って調べてみました。

主な違い

B+ TreeはほとんどB Treeと同じですが、以下の点が異なります。

  • リーフノードとリーフノードを結ぶポインタがある
  • データはリーフノードのみに保持する

具体例

言葉だけだと分かりにくいので、Visualizeするツールを使って具体例を表示します。
[1, 2, 3, 4, 5, 6, 8, 10, 15, 18]という数列に対し、Order: 3で作ってみます。

B Tree

f:id:quoll00:20170517165955p:plain

B-Tree Visualization

B+ Tree

f:id:quoll00:20170517170010p:plain

B+ Tree Visualization

先程のB Treeと違って、データはリーフノードに持つので、途中の子ノードとリーフノードで同じキーがあることが分かります(2、5、15など)
また、末端のリーフノードたちはポインタで結ばれています。

それぞれの優位性

この画像が非常に分かりやすいです。

f:id:quoll00:20170517173307p:plain

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の方が範囲検索に向いています。
ではなぜ範囲検索に強いと言われるのでしょうか?

MongoDBのシャーディングのパーティショニングは他のNoSQLのConsistent Hashingではなく、RDBMSのようなレンジパーティションです。
MongoDBが範囲検索に強いと言われているのはこの分散戦略のためです。
(逆に言えばシャードキーを範囲検索のクエリとして使わないケースでは別に強くない、ということになります)

ソース