面试题：为什么MySQL使用B+树？

MySQL的索引结构使用的是B+树，因而B+树是大厂面试的高频题。 B树

B树的概念 B树又称为B-树，是一种平衡多路查找树，描述B树，一般需要指定其阶数M，阶数指的是一个节点包含的子节点最大数量。当M取2时，即为常见的二叉树。 其有如下性质： 每个节点最多有 M - 1 个关键字 除根节点外，其余的节点至少有ceil（M/2）-1个关键字（ceil为向上取整函数） 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同 B树的插入操作 1.找到关键字的插入位置，一定时叶节点位置，进行插入操作 2.插入后，如果当前节点的关键字数量小于等于M - 1，则结束，否则执行步骤3 3.进行分裂操作，当前节点按中间关键字分裂成三部分，中间关键字插入到父节点中，左边部分，称为中间关键字的左节点，右边部分称为中间关键字的右节点，然后当前节点指向父节点，转到2，递归执行操作。 B树的构建过程 下面以构建一个5阶树为例，介绍B树构建过程 依次插入关键字3， 5， 2， 6 插入4，由于当前节点关键字数量等于M（5），需要进行分裂操作 依次插入关键字1，8，7，9, 9插入时又进行了分裂 依次插入关键字10, 11, 12, 12插入时又进行了分裂 插入关键字13,14,15,16,17，中间插入15的时候进行了分裂操作 最后插入18，进行了两次分裂操作 B树的优缺点 B树主要的优点是相对于二叉树，每个节点包括更多的关键字，所以其树高相对较低，查找效率很高

B+树

B+树的概念 B+树包含两种节点，一种是非叶子节点（索引节点），一种是叶子节点 B+树与B树，最大的不同是B+树的非叶子节点不保存数据，只用于索引，所有数据都保存在叶子节点 非叶子节点最多有M - 1 个关键字，阶数M同时限制了叶子节点最多存储 M - 1 个记录 索引节点中的key都按照从小到大的顺序排列，对于内部节点中的一个key，左子树中的所有key都小于它，右子树中的key都大于等于它。叶子节点中的记录也按照key的大小排列 每个叶子节点都存有相邻叶子节点的指针，叶子节点本身依关键字的大小从小到大顺序连接（范围查找特性） B+树的构建过程 如下为一个5阶B+树的构建过程 依次插入1， 5， 9， 13 插入17，发生分裂 依次插入2， 3， 4，插入4的时候，发生分裂过程 依次插入10， 11，插入11的时候，发生分裂过程 插入12,14，插入14的时候，发生分裂 插入15， 16，插入16的时候发生两次分裂过程，依次在叶节点和索引节点

B+树的优点 1.B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快 2.B+树查询速度更稳定：B+所有关键字数据地址都存储在叶子节点上，所以每次查找的次数都相同，所以查询速度要比B树更稳定 3.B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时更方便，数据紧密型很高，缓存的命中率也会比B树高。 4.B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描