1、B树和B+树的区别

B Tree

B+Tree

B+ Tree Visualization B-Tree Visualization

节点之间排序

B+树叶子节点之间会有指针，B树没有

B+树非叶子节点的元素都冗余了一份在叶子节点上

Innodb中的B+树如何生成的呢

以Mysql版本5.7.16展示

InnoDB引擎下，一页默认大小为16384/1024 = 16KB

执行命令 SQL语句 show global status like 'Innodb_page_size';

每次从Innodb中取数据的时候，最小单位是 一页 每次读取16KB

写数据时，最少要在内存开辟16KB空间

Mysql创建表时，底层仍然会认为是BTree，会认为B+Tree是BTree的一个升级版

插入的时候，我的insert into语句是乱排，仍可以根据主键索引 排列

insert into t1 values(4,3,1,1,'d');
insert into t1 values(1,1,1,1,'a');
insert into t1 values(8,8,8,8,'h');
insert into t1 values(2,2,2,2,'b');
insert into t1 values(5,2,3,5,'e');
insert into t1 values(3,3,2,2,'c');
insert into t1 values(7,4,5,5,'g');
insert into t1 values(6,6,4,4,'f');

插入完成之后，会自动根据 主键索引排序

而Mysql从这张表往内存中读数据，也不是一行一行读取，而是一页一页读取

那这一行数据有多大呢？

CREATE TABLE t1(
  `a` int primary key,
  `b` int,
  `c` int,
  `d` int,
  `e` VARCHAR(20)
) ENGINE=InnoDB;

创建表时，a,b,c,d,e,五个字段，其中四个int类型，一个int类型占4个字节，一个varchar类型，就默认字符集是utf8mb4，一个varchar类型占4个字节，那么一行数据的大小就是 (4*4)+4 = 20b. 1KB = 1024b

一页 = 16KB

取数据时，一页一页取，那么插入的这8条数据都包含在这一页当中.只需要取一次，进行一次磁盘IO就可以放入内存中

假设，这一页中，架构如下

a为1，2 为一组 4，5是一组，数据与数据之间指针相连，那么页目录的值就是这一组第一条数据的主键索引的值

假设，此时执行一条sql语句 select * from t1 where a = 8，会把这一页的数据从磁盘中放入内存，首先判断这个值为8的a会在哪一组

会直接从页目录为4遍历查找，因为这个组下就2条数据，只会遍历两次，如果没有找到，那就说明这张表中没有a=8，不会在去页目录为1的数据组下循环查询。 这里运用的就是 空间换时间的设计

假设我一页只能存这4条数据，再往里面插入第五条数据时，会新开一页 ,执行 insert into values(3,3,2,2,'c');

会把插入的数据放入新开辟的一页吗？ 会先判断，主键a = 3 , 由于插入时会自动排序，则会把这条数据插入页目录4的组下，会把a=5这条数据放入新的一页，期间断开指针重新插入指针，会有一定的性能影响，所以推荐 主键策略会自增

现在有两页 执行SQL select * from t1 where a = 6

innodb执行时，会把第一页加载查询，发现第一页没有会根据指针去第二页查询

假设此时 海量数据新增 不停地新建页 链表也会不断地增大，查询时也需要不断地从磁盘中一页一页的读取数据。效率低下

优化思路

现在有两页，新建一个页目录 存放 每一页中 页目录最小的值，上图中 最小值是 1、3

那么新增的页目录就 记载1、3，并指向对应的页(不想再画图了)

此时在执行select * from t1 where a = 6 首先会判断存放页目录值的这一页，通过判断结果去对应的页目录查找

那这一页又能存放多少页目录的值呢 ，假设主键a类型是int，占4字节，指针占6字节， 而一页大小又是16KB

16*1024/10=1638,也就是说，存放主键+指针这样一对一对的数据，可以存放1638组

高度为3的B+Tree能存多少数据呢？

上图显示，叶子节点主要存放的就是数据，根节点存放的则是主键值

假设在一张表中，每一条记录大小1KB，主键是int类型，那么就是1638*(16/1) = 26208，一个2层B+Tree可以存放的数据26208条数据

那三层B+Tree呢

在顶层节点中，假设有两个组，其中一组记录最小的页的主键值，另一组记录另一页的主键值，那么就是 1638*1638*16

达到这么大的值，就不建议继续通过索引来优化，需要进行分库分表了，因此尽量把B+Tree维护在两层

Innodb是如何支持范围查找能走索引的？

这种把数据存放在叶子节点，非叶子节点存放数据索引的三层B+Tree，称之为主键索引或者 聚集索引/聚簇索引

此时执行一条SQL select * from t1 where a = 6 ,就会根据顶层的索引页往下查找

这是根据主键a建立的主键索引 ，执行select * from t1 where b = 6，则走不了这个索引，只能一条条遍历

那执行select * from t1 where a > 6 或者 select * from t1 where a < 6呢？

可以看到，两条SQL语句走的都是主键索引.

为什么要遵循左前缀法则才能利用到索引？

先执行SQL select * from t1;

表中有8条数据并按照主键排序

执行SQL create index idx_t1_bcd on t1(b,c,d); 为BCD字段创建一个联合索引

在执行SQL explain select * from t1 WHERE b= 1 and c = 1 and d = 1;

发现是可以走这个创建的联合索引。

它的底层会生成一个B+Tree，并按照升序排列，可以看到表中B字段的值有重复出现，这时会比较C字段排序，以此类推，生成的B+Tree如下图

执行SQL select * from t1 where b = 1 and c = 1 and d = 1 传入的条件就是 111 这样，取出对应的索引页依次查找，但是因为是select * 即使找到了对应的页中的数据，也只有bcd三个字段。所以需要再下方挂主键a索引的值

之后根据a的值去主键索引找，拼接后返回。这个过程就称之为 回表查询 这就是innodb里的回表

那为什么要遵循最左前缀法则呢？

执行 select * from t1 where b = 1 and c = 1 and d = 1 传入的bcd是111可以走聚合索引.

那select * from t1 where d = 1 and c = 1 and b = 1 把这几个字段调换位置

照样可以走聚合索引

依次执行

explain select * from t1 WHERE b= 1;    #传入 1**  可以走索引
explain select * from t1 WHERE d= 1;    #传入 **1  不行
explain select * from t1 WHERE c= 1;    #传入 *1*  不行
explain select * from t1 WHERE b= 1 and d = 1; #传入 1*1  可以
explain select * from t1 WHERE b= 1 and c = 1; #传入 11*  可以
explain select * from t1 WHERE c= 1 and d = 1; #传入 *1*  不行

如上图B+Tree可以发现，从索引最左开始匹配， 如果不匹配，就停止后面的比对。

运行结果如下