B TreeとB+ Treeの違い

概要

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

主な違い

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

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

具体例

言葉だけだと分かりにくいので、Visualizeするツールを使って具体例を表示します。

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

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

ソース

投稿日:May 17th 2017

元記事:http://christina04.hatenablog.com/entry/2017/05/17/190000

– PR –
– PR –