104.MongoDB 为什么选择 B-Tree 索引?

MySQL 面试题 中，我们已经看到 MySQL 使用的是 B+Tree 索引。

• B+Tree 内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log(n) 。
• B-Tree 查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1) 。

我们知道，尽可能少的磁盘 IO 是提高性能的有效手段。MongoDB 是聚合型数据库，而 B-Tree 恰好 key 和 data 域聚合在一起。

至于 MongoDB 为什么使用 B-Tree 而不是 B+Tree ，可以从它的设计角度来考虑，它并不是传统的关系性数据库，而是以 JSON 格式作为存储的 NoSQL ，目的就是高性能，高可用，易扩展。

• MySQL 由于使用 B+ 树，数据都在叶节点上，每次查询都需要访问到叶节点，而 MongoDB 使用 B-Tree ，所有节点都有 data 域，只要找到指定索引就可以进行访问，无疑单次查询平均快于 MySQL 。

具体的讨论，可以看看 《为什么有关 MongoDB 采用 B 树索引，以及 MySQL B+ 树做索引？》 上的讨论。当然，这个回答可能有点牵强。列出这个问题的目的在于，让我们知道 MongoDB 并不是使用 B+Tree 来实现索引。

? MongoDB 在 A:{B,C} 上建立索引，查询 A:{B,C} 和 A:{C,B} 都会使用索引吗？

因为 MongoDB 使用 B-Tree 索引，实际上查询和 MySQL 的 B+Tree 索引是基本一致的。

• A:{B,C} 上，可以完整使用索引。
• A:{C,B} 上，只能部分使用索引，只有 A 部分。