概要
インデックスに対して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は1ノードから出る枝の数のことです。
B Tree
続きを読む