本文将探讨以下几个问题。

一、思考

问题一：B树和B+树的区别？

问题二：为什么InnoDB要采用B+树数据结构？

二、分析

• B树的结构

本文大量参考了其他比较优秀的博文，具体地址，请看文末。

B即balance，意为平衡，B树又称为多路平衡查找树，也称B-树。多路即允许每个节点有多个子节点，称为阶。当阶数为2时，又称为平衡二叉查找树。

M阶B树的定义：

1. 每个节点至多有M个子节点。
2. 根节点至少有两个子节点（根节点有子节点前提下）。
3. 除根节点之外的非叶子节点的子节点数至少为M/2。
4. 每个节点存放至少(M/2)-1个关键字，至多M-1个关键字（B树每个节点可以存储多个关键字，请看下文），最少2个。
5. 非叶子节点的关键字个数=指向子节点的指针数-1。
6. 非叶子节点的关键字升序排列。即K1,K2,....KM-1，且Ki
7. 非叶子节点指针：P1,P2....PM，P1指向关键字小于K1的节点，PM指向关键字大于KM-1的节点，其余指针指向关键字位于P1和PM之间的节点。
8. 所有叶子节点位于同一层。

通过定义，我们可以描绘出以下B树（3阶）结构：

• B+树的结构 

B+树的基本定义和B树相同。但是 B+树到叶子节点才会命中，且为每一个叶子节点增加了指针，将多有叶子结点相连。

B+树定义：

1. 非叶子节点的子节点个数与关键字个数相同。
2. 非叶子节点的指针指向关键字属于[Ki,Ki+1)（左闭右开）的子节点。
3. 所有关键字存在于叶子节点。
4. 所有叶子结点都有一个指向后继节点的指针。

通过定义，我们可以描绘出以下B+树（3阶）结构：

一颗3阶B+树大约能存储1千万数据，具体计算请看博文【MYSQL---索引---物理结构】文末的参考博文。

• 为什么MYSQL要用B+树

我们知道因为磁盘空间远大于内存，而且为了可以做到数据恢复需要将数据持久化到磁盘,MYSQL的数据最终将存储在磁盘上，而磁盘I/O很耗时，为了能够实现数据存储的同时最大程度减少磁盘I/O，无疑B+树是最好的数据结构。其相比于B树而言，主要在于：

1. B树的非叶子节点不仅存放键值和指针，同时存放数据，而一个页的数据大小为16k，这样一个页中所存储的键值就会减少，导致整颗B+树的高度增加，那么查找某个键值的I/O次数变多，耗时变长。而B+树非叶子节点只存储键值，无疑会降低整颗树的高度，即一颗1000W的数据查找最多也只需要3次磁盘I/O。
2. 同时B+树的叶子节点为循环链表数据结构，非常有利于范围查询。

参考博文：

https://plushunter.github.io/2017/07/20/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%886%EF%BC%89%EF%BC%9AB%E6%A0%91%E3%80%81B+%E6%A0%91/