彻底搞懂MySql的B+Tree
官方定义：一种能为mysql提高查询效率的数据结构，索引是为了加速对表中数据行的检索而创建的一种分散存储的数据结构。好比如，一本书，你想找到自己想看的章节内容，直接查询目录就行。这里的目录就类似索引的意思。
如上图中，如果现在有一条sql语句 select * from user where id = 40，如果没有索引的条件下，我们要找到这条记录，我们就需要在数据中进行全表扫描，匹配id = 40的数据。
如果有了索引，我们就可以通过索引进行快速查找，如上图中，可以先在索引中通过id = 40进行二分查找，再根据定位到的地址取出对应的行数据。
现在看来，索引是不是也不过如此。咋们接着往下看。
那么有的同学可能会问，既然索引缺点这么多，那我为什么还要用索引啊？也就是提高了查询速度而已。
提高了查询速度呀，这个绝对是个大优势，在数据量庞大的情况下，我们通过命中索引，能大大的提高查询速度，增删改基本消耗忽略不计。摘抄阿里P3C开发规范。
我们先来看一个sql
执行完后：
奇怪？为什么数据和我插入的顺序不一致呢，竟然给我自动排序好了！！！我们接着看
其实mysql每条数据的存储是这样子的（图自己画的，—_—,将就下）
mysql给我们提供了页的概念，并且有页目录，页目录数据为叶族节点每页的第一条数据id，页目录和每页大小均默认为16KB，如下图：
举个例子：
那么有的小伙伴可能会问，你这样也存不了多少数据呀，那假如我数据量非常多呢，这颗数怎么存呢。
以上表而言，一个id占用8个字节（long类型），name 20个字节，p指针也要占用字节的（大概4~8个字节），我们以最大8来算，那么一条数据大概就是：8+20+8=36，36个字节，那么一页换算一下是 16x1024 = 16384 个字节，那么叶子节点一页可以存储数据量为：16384/36 = 455 条数据。那么页目录又存着id，一个id8个字节，能存储16x1024/8 =2048，2048x455 = 931,840 ...粗略的算了下3层数，能存储数据量为1,908,408,320个 很多了，可能表的字段很多的话，存储数据量稍微少点，但是也很多了。
B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。
这个时候有个问题思考下？为什么mysql推荐ID自增呢？这个时候是不是心里有了答案呢？或许自己可以先想想再看。
我们日常工作中，根据实际情况自行添加的索引都是辅助索引，辅助索引就是一个为了需找主键索引的二级索引，现在找到主键索引再通过主键索引找数据； （这就是所谓的回表查询）
聚簇索引就是按照每张表的主键构造一颗B+树，同时叶子节点中存放的就是整张表的行记录数据，也将聚集索引的叶子节点称为数据页。这个特性决定了索引组织表中数据也是索引的一部分，每张表只能拥有一个聚簇索引。
聚簇索引并不是一种单独的索引类型，而 是一种数据存储方式 。具体细节依赖于其实现方式。
聚簇索引的优缺点
优点：
1.数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快
2.聚簇索引对于主键的排序查找和范围查找速度非常快 缺点：
1.插入速度严重依赖于插入顺序，按照主键的 顺序插入 是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个 自增的ID列为主键 2. 更新主键的代价很高 ，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。 3.二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据。
在 聚簇索引之上创建的索引称之为辅助索引 ，辅助索引访问数据总是需要二次查找。辅助索引叶子节点存储的不再是行的物理位置，而是主键值。通过辅助索引首先找到的是主键值，再通过主键值找到数据行的数据页，再通过数据页中的Page Directory找到数据行。
--以上可能没有说完整，或者有遗漏的地方，欢迎补充！！！
