基本知识
1、操作系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的
2、InnoDB存储引擎是按页来处理数据的，因此B-Tree/B+Tree的基础分配单位是页。InnoDB存储引擎中默认每个页的大小为16KB。
通过以下命令进行茶盘
mysql> show variables like 'innodb_page_size';3、磁盘块（block）实际上并没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。
平衡多路查找树（B-Tree）（所有节点存放data）
b-tree是平衡二叉树的优化，主要是为了排序数据，查找数据，减少磁盘IO。
B-Tree特点
1、每一个节点，包含指针（指向子节点的指针），主键值，data（主键值所在记录的一行数据）。
2、一个m阶的b-tree，每个节点最多有m个孩子。例如三阶，每个节点有三个孩子节点
如下图所示为一个3阶的B-Tree：
注意：图中磁盘块，应该为innodb的调度单位 页。使用页，方便理解
以主键28，展示搜索过程：
1、磁盘IO，读取根节点页（实际上根节点被载入内存，读取内存中的根节点）
2、内存比较，28大于17，小于35，读取对应页
3、磁盘IO，读取p2指针所指向的节点
4、内存比较，28大于26，小于30，读取对应节点
5、磁盘IO，读取对应节点页
6、内存比较，获取28主键值，和对应的记录数据
以上过程三次磁盘IO（实际上应该是两次），三次内存比较。每个节点都包含data（记录数据）
B-tree缺点
- innodb引擎对于页的处理是 16kb，节点中不仅包含键值，指针，还有占用空间较大的记录data。
- 而主键大小bigint占8byte，指针占8byte，data大小占用过大，导致一页（节点）实际上存放不了多少键值和指针。
- 一旦页存放不下，就会加深B-Tree的深度，而我们知道每加深一层，磁盘IO一层，磁盘IO效率低，导致整体性能降低。
B+Tree （叶子节点存放data）
B+Tree是堆B-tree的优化，主要是想每一页（每个节点）多存放键值和指针，减少tree深度，降低磁盘IO，提高查找效率。
B+Tree特点
1、非叶子节点只存储键值信息和指针。
2、所有叶子节点之间都有一个链指针。
3、数据记录都存放在叶子节点中。
假设每页能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：
1、InnoDB存储引擎中页的大小为16KB，
2、表的主键类型为BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值
3、假设data为1kb，一页中最多16kb/1kb=16条记录
3、一个深度为3的B+Tree索引可以维护10^3 10^3 16 = 16,777,216 条记录。大概是17百多万条，仅仅也才三层B+Tree。
