一、二叉树到多叉树

1.二叉树的劣势

• 二叉树每个节点至多只有两个子节点，如果整个数据比较大，那么我们的树的深度(高度)将非常大，无论对于插入或者删除，速度将会变得比较缓慢

2.多叉树(多路搜索树)

注：多叉树并不是专业的叫法，这里只是为了更好的理解

M阶多路搜索树

• 每个节点至多M个子节点

二、B树和B+树

1.B树即B-tree

注：这里的B是Balance

(1)B树的性质

B树又叫多路平衡查找树，其主要有以下几个性质：对于一个M阶的B树

• 如果根节点不是叶子节点，那么它至少有2个子节点
• 每个节点至多有M个子节点
• 除了根节点和叶子节点外，其他节点至少有ceil(M/2)个节点
• 非叶子节点如果有K个子节点，则有K-1个关键字(关键字就是每个节点有多个数据)
• 所有叶子节点处于同一层

(2)B树的结构

B树本质上是一个多路搜索树，只不过，它的每个子节点，不是只有一项数据，而是有一批数据

注：这是一个3阶的B树

• 至多有3个子节点
• 比如包含[12, 14]这组数据的节点，有3个子节点，那它至多只能有2个关键字，即它至多只有有两个数据点
• 3阶的B树的叶子节点，都在第3层中

(3)B树节点的插入

• 节点的的插入为了满足B树的性质，需要做一些节点拆分

• 要向树中插入一个元素15，从根节点开始比较，插入的节点比根节点大，则应该插入到根节点的右子树上，依次比较，插入到叶子节点中，此时叶子节点为[9,10, 11, 15]个数据
• 因为这是一个3阶的B树，所以，叶子节点最多只能3个数据，此时需要进行节点拆分

(4)B树节点的删除

• 当删除非叶子节点时，为了满足B树的性质，也需要将节点做一些移动

(5)B树节点的查找

• 从根节点开始，判断节点是在左子树还是右子树
• 子节点的数值集合中通过二分法查找，如果在当前集合中查找到，则查找结束，如果没查找到，再在对应的子树中继续通过二分法查找

(6)B树节点内部结构

• 节点的key,相当于索引
• 节点的data,具体存储的数据
• 节点的前指针，指向比当前key小的子节点
• 节点的后指针，指向比当前key大的子节点

(7)B树的存储结构

2.B+树

相对于B树，B+树又增加了以下特征：

• 叶子节点增加了指向下一个节点的指针　
• 每个节点的指针上限为2d，则不是2d+1
• 非叶子节点不存储具体数据，只存储key;叶子节点不存储指针

三、在MySQL中通过B-Tree实现索引的解读

1.InnoDB存储引擎

InnoDB存储引擎，索引文件和数据文件在同一个文件

• 叶子节点存储的是具体的数据

(1)主索引(主键索引)

(2)辅助索引

• 叶子节点存储的是主索引的key，需要通过主索引key来查找具体数据

2.MyISAM存储引擎

• 主索引和辅助索引的叶子节点都是存储指向记录数据的指针，而不是数据
• 辅助索引的叶子节点也是存储指向记录数据的指针，而不是指向主索引的指针