MySQL-B+Tree索引
- 总结的很好
- 结构图
性质（m叉B+树）：
- 树中每个结点至多有m个孩子。
- 除根结点和叶子结点外，其它每个结点至少有[m/2]个孩子。
- 若根结点不是叶子结点，则至少有2个孩子。
- 所有叶子结点都出现在同一层。
- 每个非终端节点中包含n个关键字信息：(A0，K1，A1，K2，A2，......，Kn，An)。其中，Ki (i=1...n)为关键字，且关键字按顺序排序Ki < K(i-1)。Ai为指向子树根的接点，且指针A(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。关键字的个数n必须满足： [m/2]-1 <= n <= m-1
优势：
- 只有叶子节点才记录数据，非叶子节点只包含索引；所有的非终端节点（内部节点）并不存储数据信息，而是保存其叶子节点的最小值作为索引。 这样，一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
- 能够提供稳定高效的范围扫描（range-query）功能；这也是为什么数据库和操作系统中的文件系统通常会采用b+树作为数据索引的原因，这个特点主要因为所有叶子节点相互连接，并且叶子节点本身依关键字的大小自小而大顺序链接。
- MySQL为什么使用 B+Tree
- mysql的数据是放在外部存储的，也就是说磁盘IO才是性能瓶颈的关键，所以我们需要的是减少树的深度，所以我们需要更多分叉的树 ,还需要更适合磁盘操作特性的数据结构。
- B+树是为磁盘或其他直接存取的辅助存储设备而设计的一种数据结构。
- MySQL为什么选取B+树，本质上是因为MySQL数据是存放在外部存储的。
参考：