为什么Mongodb索引用B树，而Mysql用B+树?

引言

好久没写文章了，今天回来重操旧业。

今天讲的这个主题，是 《面试官:谈谈你对mysql索引的认识》 ，里头提到的一个坑。

也就是说，如果面试官问的是，为什么Mysql中Innodb的索引结构采取B+树？这个问题时，给自己留一条后路，不要把B树喷的一文不值。因为网上有些答案是说，B树不适合做文件存储系统的索引结构。如果按照那种答法，自己就给自己挖了一个坑，很难收场。因此，就有了这篇文章的诞生~

文末附面试指南！

正文

这里的Mysql指的是Innodb的存储引擎下的索引结构，其他存储引擎我们暂时不讨论。

B树和B+树

开头，我们先回忆一下，B树和B+树的结构以及特点，如下所示:

B树

注意一下B树的两个明显特点

• 树内的每个节点都存储数据

• 叶子节点之间无指针相邻

B+树

注意一下B树的两个明显特点

• 数据只出现在叶子节点

• 所有叶子节点增加了一个链指针

针对上面的B+树和B树的特点，我们做一个总结

(1)

B树的树内存储数据，因此查询单条数据的时候，B树的查询效率不固定，最好的情况是O(1)。我们可以认为在做单一数据查询的时候，使用B树平均性能更好。但是，由于B树中各节点之间没有指针相邻，因此B树不适合做一些数据遍历操作。

(2) B+树的数据只出现在叶子节点上，因此在查询单条数据的时候，查询速度非常稳定。因此，在做单一数据的查询上，其平均性能并不如B树。但是，B+树的叶子节点上有指针进行相连，因此在做数据遍历的时候，只需要对叶子节点进行遍历即可，这个特性使得B+树非常适合做范围查询。

因此，我们可以做一个推论:没准是Mysql中数据遍历操作比较多，所以用B+树作为索引结构。而Mongodb是做单一查询比较多，数据遍历操作比较少，所以用B树作为索引结构。

那么为什么Mysql做数据遍历操作多？而Mongodb做数据遍历操作少呢？

因为Mysql是关系型数据库，而Mongodb是非关系型数据。

那为什么关系型数据库，做数据遍历操作多？

而非关系型数据库，做数据遍历操作少呢？

我们继续往下看

关系型VS非关系型

假设，我们此时有两个逻辑实体:学生(Student)和班级(Class)，这两个逻辑实体之间是一对多的关系。毕竟一个班级有多个学生，一个学生只能属于一个班级。

关系型数据库

我们在关系型数据库中，考虑的是用几张表来表示这二者之间的实体关系。常见的无外乎是，一对一关系，用一张表就行。一对多关系，用两张表。多对多关系，用三张表。

那这里，我们需要用两张表表示二者之间逻辑关系，如下所示

那我们，此时要查 cname 为 1班 的班级，有多少学生怎么办？

假设 cname 这列，我们建了索引！

执行SQL，如下所示！

SELECT *
FROM t_student t1, (
        SELECT cid
        FROM t_class
        WHERE cname = '1班'
    ) t2
WHERE t1.cid = t2.cid

而这，就涉及到了数据遍历操作！

因为但凡做这种关联查询，你躲不开join操作的！既然涉及到了join操作，无外乎从一个表中取一个数据，去另一个表中逐行匹配，如果索引结构是B+树，叶子节点上是有指针的，能够极大的提高这种一行一行的匹配速度！

SELECT cid
FROM t_class
WHERE cname = '1班'

SELECT *
FROM t_student
WHERE cid = ...

那在非关系型数据库中，我们如何查询 cname 为 1班 的班级，有多少学生？

非关系型数据库

有人说，你可以这么设计？也就是弄两个集合如下所示