MySQL索引与MongoDB索引的区别
介绍了为什么MySQL使用B+TREE 而 MongoDB使用B-TREE
MySQL索引与MongoDB索引的区别
1. 背景
最近学习了MySQL的索引的相关内容，而目前生产系统上使用的使MongoDB，遂对这两个不同数据库的索引进行了下对比。这里的MySQL值得使Innodb存储引擎。2. 两个数据库之间的区别
MySQL中的Innodb采用的使B+Tree作为索引的结构，而MongoDB使用的使B-Tree作为索引结构，所以这两个数据库索引之间的区别也就是这两种数据结构之间的区别
2.1 B 树和 B + 树
B-数
B 树的两个明显特点
- 树内的每个节点都存储数据
- 叶子节点之间无指针相邻
B+数
B + 树的两个明显特点
- 数据只出现在叶子节点
- 所有叶子节点增加了一个链指针
针对上面的 B + 树和 B 树的特点，我们做一个总结
- B 树的树内存储数据，因此查询单条数据的时候，B 树的查询效率不固定，最好的情况是 O(1)。我们可以认为在做单一数据查询的时候，使用 B 树平均性能更好。但是，由于 B 树中各节点之间没有指针相邻，因此 B 树不适合做一些数据遍历操作。
- B + 树的数据只出现在叶子节点上，因此在查询单条数据的时候，查询速度非常稳定。因此，在做单一数据的查询上，其平均性能并不如 B 树。但是，B + 树的叶子节点上有指针进行相连，因此在做数据遍历的时候，只需要对叶子节点进行遍历即可，这个特性使得 B + 树非常适合做范围查询。
2.2 关系型 VS 非关系型
假设，我们此时有两个逻辑实体: 学生 (Student) 和班级(Class)，这两个逻辑实体之间是一对多的关系。毕竟一个班级有多个学生，一个学生只能属于一个班级。 关系型数据库
我们在关系型数据库中，考虑的是用几张表来表示这二者之间的实体关系。常见的无外乎是，一对一关系，用一张表就行。一对多关系，用两张表。多对多关系，用三张表。
那这里，我们需要用两张表表示二者之间逻辑关系，如下所示
此时如果需要查询cname为1班的班级，有多少学生，MySQL怎么执行（cname这列建了索引）？
SQL如下
SELECT *
FROM t_student t1, (
SELECT cid
FROM t_class
WHERE cname = '1班'
) t2
WHERE t1.cid = t2.cid但凡做这种关联查询，你躲不开 join 操作的，既然涉及到了 join 操作，无外乎从一个表中取一个数据，去另一个表中逐行匹配，如果索引结构是 B + 树，叶子节点上是有指针的，能够极大的提高这种一行一行的匹配速度
非关系型数据库
在MongoDB中，虽然也可以和在MySQL一样通过两张表来表达学生和班级的关系，但是这并不符合非关系型数据库的设计初衷。在 MongoDB 中，根本不推荐这么设计。虽然，Mongodb 中有一个 lookup操作，可以做join查询。但是理想情况下，这个lookup 操作应该不会经常使用，如果你需要经常使用它，那么你就使用了错误的数据存储了（数据库）。如果你有相关联的数据，应该使用关系型数据库（SQL）。
因此，正规的设计应该如下
假设name这列，我们建了索引
此时的执行语句
db.class.find( { name: '1班' } )这样就能查询出自己想要的结果。
而这，就是一种单一数据查询! 毕竟你不需要去逐行匹配，不涉及遍历操作, 幸运的情况下，有可能一次 IO 就能够得到你想要的结果。
3. 总结
可以看出由于关系型数据库和非关系型数据的设计方式上的不同。导致在关系型数据中，遍历操作比较常见，因此采用 B + 树作为索引，比较合适。而在非关系型数据库中，单一查询比较常见，因此采用 B 树作为索引，比较合适。
参考