mysql-B-Tree和B+Tree、回表

B-Tree和B+Tree

前面是 B-Tree，后面是 B+Tree，两者的区别在于：
1.B-Tree所有节点都可以带指针，B+Tree只有叶子结点才可以带指针(叶子结点就是末尾的节点)
2.B-Tree中叶子结点没有指针连在一起，B+Tree中所有叶子结点通过指针连在一起
3.B-Tree可能在非叶子节点就拿到指向记录的指针，B+Tree需要在叶子节点才能拿到指向记录的指针
在 InnoDB 存储引擎中，B+Tree 的高度一般为 2-4 层，这就可以满足千万级的数据的存储

索引的分类

索引的分类有两个大类：主键索引和非主键索引
主键索引也就是聚簇索引，非主键索引包括普通索引、唯一索引、联合索引
主键索引和非主键索引使用的数据结构都是B+Tree，唯一的区别在于B+Tree存储的数据不同：
主键索引的叶子结点存储的是一行完整的数据，非主键索引的叶子结点存储的是主键值

所以当我们查询的时候：
如果我们是通过主键索引查找数据：select * from User where id = 100，此时只需要搜素主键索引的B+Tree，即可拿到数据
如果我们通过非主键字段查找数据：select * from User where name = 'max'，那么需要先搜索非主键索引的B+Tree，拿到索引，然后再搜索主键索引的B+Tree，就可以获得数据

当我们用第二种方式查数据，一共查找了两次B+Tree，第一次是通过非主键索引找到主键，第二次是通过主键索引拿到数据，这个过程叫回表

从上面的分析中我们也能看出，通过非主键索引查询要扫描两棵 B+Tree，而通过主键索引查询只需要扫描一棵 B+Tree，所以如果条件允许，还是建议在查询中优先选择通过主键索引进行搜索。