mysql B+Tree

1、B-Tree
叫B树，记得不是B减，像iphone12-pro，不会是减pro

2、B+Tree（B+-Tree）
B加树

有数据冗余，叶子节点存储所有的数据

3、官方对Innodb的部分说明

4、提出疑问
创建一个表

然后无规律的插入数据并查询

结果会变成 好像是根据a字段升序排序了

为什么会这样？稍后说明

5、page？
我们先假设查询select * from t1 where a=7;，就会先从磁盘读取第一条数据放到内存中，然后cpu判断该条数据a是否等于7，不等于就要继续读取下一条，这样会发生7次磁盘IO。
mysql为了提升速度，使用了page，通过show global status like 'Innodb_page_size';查看一页的大小为16KB

所以存储引擎每次取都会至少取一页的数据，也就一次磁盘IO就把数据读取到内存中，然后CPU取第一条进行判断，再取第二条进行判断。

在数据插入的时候就已经进行了排序

6、为什么插入的时候要排序
加快读取。当查询a=3的时候，第二条4已经比3大了，证明数据不存在，不会再遍历该页的数据

所以建议主键是自增id。
上面这个只是一个小优势，当查询a=300000的话，那还是需要遍历这页所有数据的一个长链表，性能差，需要用到页目录。

7、页目录
类似新华字典，要查某个汉字，根据他的拼音，得到在那一页开始，然后再查询。

页目录存的是主键，这样查找速度就快很多了。
但如果页目录太多的时候，还是需要先判断30000是否小于1，是否小于4，是否小于10....最后才得出它应该在最后一页

还可以用二分查找法提升查找在那一页的速度。

8、
假设一页存四条数据就满了，后续数据就会存到下一页。
（其实是双向链表）

在非自增id的时候，例如第一页存的是1，2，4，8，这时要插入5，就需要把5挤进第一页，8退到第二页，这样速度就会很慢。所以主键自增是很有必要的

9、
当存了8条数据，第一页1234，第二页5678，这时要查a=6，就会先读第一页到内存中，然后查找a=6没有数据，再根据next指针在磁盘找到第二页读到内存，再找a=6的数据。两次磁盘IO，更多页就会更多的IO（a=600000，变成了页的长链表）效率会很低

10、
同样的思想，为页目录再做一个管理目录，存每页的最小主键值

这样就能更快定位到那一页了。现在这个图就和B+Tree相同了

11、
现在为了方便查看，假设一页两条数据

B+Tree最主要的是主键，主键索引。
如果这时查b=7，就无法用主键索引了