B+ Tree定义

首先B+树是B树的一种扩展，在B+树里面，非叶子节点不再存储数据，仅仅存在索引，而叶子这点存储具体的数据，并且最底层的数据直接之间从左到右是按照从小到大的顺序分布，并且是一个双链表的结构。也就是说的所有的关键码均出现在叶节点上，各层节点中的关键码均是下一层相应节点中的最大或者最小的关键码的复写。

m阶B+树的结构定义如下：

• （0）m阶的意思是节点可以最多有多少个子节点
• （1）每个节点最多有m个子节点
• （2）除根节点外，每个节点至少有m/2个子节点，注意如果结果除不尽，就向上取整，比如5/2=3。
• （3）根节点要么是空，要么是独根，否则至少有2个子节点
• （4）特点 有k个子节点的节点必有k个关键字
• （5）叶节点的高度一致
• （6）特点 所有叶节点包含全部关键字及其指向相应记录的指针：叶节点按关键字大小顺序排列，并且相邻叶节点按大小顺序相互链接，支持顺序查找。
• （7）特点所有分支节点中只包含其子节点中的最大关键字及指向其子节点的指针：这使得B+树更倾向于“索引”。

MySql中的B+ Tree的一点小特点

• 看的文章大部分说Mysql的都是说的几层、以及节点占用页的大小（一般3层或者四层，没说M阶；页一般就是4页每个页是4k也就是16k）
• Mysql中的节点数平衡应该是有个阈值控制的，所以这里不用考虑阶的情况。但是这里也就有个要注意的问题频繁变动没规律的主键的时候这个B+ Tree维持平衡分裂操作可能就更频繁了。
• 限定层级的另一个原因就是减少对磁盘的数据读取和写数
• 另一个特点就是这里对数据的更新操作是对磁盘原始数据进行操作的这个和LMS Tree（追加后续合并）是不同的（这里就有个关键问题我还不太清楚的，那就是数据修改后可能当前数据块容量（一般4k）不够的情况）

MySql中的B+ Tree根据层预估数据

以三层为例

• 0.节点大小 按照网上给的例子正常情况。一个节的数据大小4个页=16KB
• 1.索引项大小 每个索引项的大小取决于主键和指针的大小，假设主键为 8 字节，指针为 6 字节，则每个索引项的大小约为 14 字节
• 2.节点存储的索引个数 16KB/14B≈ 1170个
• 3.层级节点个数第一层可以有1170个节点。第二层节点膨胀 1170*1170。第三层假设单条数据1k（512B数据则翻倍）每个节点可以存储16K/1k=16条
• 4.三层可以存储数据大小 1170 × 1170 × 16 = 18,974,400 行