①介绍一下 B tree, 多路平衡查找树(balance tree)

通过名称多路平衡就知道这个树的特点，是平衡二叉树的基础上改进的多路（支持多个分叉）。

所有的叶子节点在同一高度，非叶子节点也会存放数据。

假设要从上图中查找id = X的数据，B TREE 搜索过程如下：

取出根磁盘块，加载40和60两个关键字。
如果X等于40，则命中；如果X小于40走P1；如果40 < X < 60走P2；如果X = 60，则命中；如果X > 60走P3。
根据以上规则命中后，接下来加载对应的数据， 数据区中存储的是具体的数据或者是指向数据的指针。

② B+树

如果上图中是用ID做的索引，如果是搜索X = 1的数据，搜索规则如下：

取出根磁盘块，加载1，28，66三个关键字。
X <= 1 走P1，取出磁盘块，加载1，10，20三个关键字。
X <= 1 走P1，取出磁盘块，加载1，8，9三个关键字。
已经到达叶子节点，命中1，接下来加载对应的数据，图中数据区中存储的是具体的数据。

③ B+树对应B树升级了什么？也就是那些不同？

A)  最直观的是 B+树的非叶子节点不储存数据，而是存索引数据。这样存储的索引数据多，树的层数更低，对于查询利用率更高。

B) B树的每个节点都是直接存储数据，而B+树只有是在叶子节点存储数据或者数据的指针。

C) C树的每个叶子节点都是排序存储的，相邻的节点具有顺序引用关系。这里顺序引用都是只的是逻辑的，而不是物理的。

④ 为什么说B+树比B树更适合数据库索引？

A) B+树 更便于范围查询

因为B+树只需要去遍历叶子节点就可以实现整棵树的遍历，而B树则需要通过从根节点从上往下的遍历。

B) B+树的读写磁盘代价更低

因为B+树的每个非叶子节点存储都是数据索引，而不是数据本身，那么每块数据(也就是和每个节点)存储的索引更多，加载到内存，查询也更多，也就是说IO读写次数也就降低了。

C) B+树查询效率更加稳定

由于B+树的数据或者数据引用都是存储到叶子节点的，每次的查询都是从根节点到叶子节点的路程，查询的路径长度相同，导致每一个数据的查询效率相当；

感谢下面的参考博主，感谢

https://blog.csdn.net/b_x_p/article/details/86434387

 Mysql B+树的存储结构

B+树中每个节点不是我们单纯的理解为一个数字或者链表节点，而是用块表示的，也可以理解为页，mysql默认的页的大小是16K。

看上面的图，假如我们现在需要找到30的这条记录，

1） 先根据根节点找到 25~50之间的索引指针,定位到第二层第二个块

2)    找到第二层的第二块后，把当前页的数据加载到内存，因为叶子节点里面的数据都是逻辑排序的，所以通过二分法能快速的找到30这条记录

注意：mysql每次查找数据，不是直接找数据，而是找到对应的页，然后在到页中取出数据。

①  索引组织表（聚簇索引）也可以理解主键索引

索引组织表也可以理解为主键索引，也是一个B+ tree的数据结构，非叶子节点放的是主键值和指针，这里的指针在mysql中是占用6个字节。 叶子节点放的是一条一条的记录。根据上面我们记录的，每个节点是以块的形式存在，每个块也是16KB的大小。

那么现在问题来了，这个B+ tree不同层的时候，这个表可以存储多少记录了？也就是现在比较流行的面试题目，当2000w数据时，你的mysql B+tree 有多少层？

我们假设：我们的主键采用的是BIGINT类型，这个类型是8个字节，一行的数据是800字节。

当B+ tree高度=1时：一个节点，也就是一个块(16KB)直接存放的是数据(一条记录是800字节)，那么可以存放 16k / 800字节 = 16 * 1024 / 800 = 20条记录 

当B+ tree高度=2时：需要计算非叶子节点可以放多少指针（6个字节）和 多个主键值（BIGINT类型是8个字节），那么我们的非叶子节点可以指向多少个叶子节点了？ 16KB / (6 + 8) = 16 * 1024 / 16 = 1170 个叶子节点。 一个叶子节点我们可以存放20条记录， 那边总记录就是 1170 * 20 = 23400

当B+ tree高度 = 3时，是不是就是 1170 * 1170 * 20 = 14040 * 1170 = 16426800

B+树的高度（层数）	记录的行数（可以记录数据多少条）
1	20 条记录
2	1170 * 20= 23400 条记录
3	1170 *  1170 * 20  = 2737800 条记录
4	1170 * 1170 *  1170 * 20

上面就是怎么大概的算出B+每个高度，可以存储多少条记录。

②  普通索引 可以理解普通列添加的索引

这里需要介绍的是普通索引怎么查询到数据的？

因为主键索引的叶子节点存储是每行的记录，所以主键索引查询到 id = 20的这条记录可以直接返回数据。

普通索引的叶子节点存储的都是（列值，主键），假如有一个goods_id列添加了普通索引，那么这个普通索引的叶子节点存储的就是 (goods_id, id), 存储的都是每个goods_id和id的值。 当需要查询goods_id=20的这条记录时， 首先会找到goods_id=20的块(数据页)，然后找到goods_id=20和他对应的主键id，然后再通过类似where id = id ，在重新去主键索引去找到对应的数据，这个过程就是回表，也称书签查询。 不是很好理解，表述的也不是很好。

这里就是为什么说，主键查询会比普通索引返回的数据要快，因为普通索引查询到索引列后，还需要到主键索引去查询。