B TreeとB+ Treeの違い - Carpe Diem

概要 インデックスに対して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 Visualization B+ Tree B+ Tree Visualization 先程のB Treeと違って、データはリーフノードに持つの

[csouls]

“つまりシャードキーがクエリに入ってないケースでは別に強くない” この辺りもMongoDBが使いづらいと思うところ。

[HHR]

絵的。わかりやすい。

[murasuke]

B+Treeはリーフのみにデータを持つので、RangeScanが早い。なのでデータの保存に使われる。

[naga_sawa]

B+Treeは葉っぱ間のリンクがあるので範囲抽出に強いと

[tmatsuu]

良い

[atm_09_td]

知っているようで知らないから、しっかり覚えておこう。

[takatoshiono]

なるほどー

[ravelll]

ソース含めあとでよむ

[khtokage]

アルゴリズムってこうやって比較しないと優位性が分からないよね。

[masatomo-m]

簡潔で分かりやすい解説

[koudaiii]

わかりやすい比較👀