MySQL B+树

1. B-树（Balance Tree）

1.1 概念

B-树是一类树，包括B树、B+树等，相比传统的二叉搜索树（AVL、RB Tree），每一节点可以拥有更多子节点。B-树是专门为外部存储器设计的，如磁盘，它对于读取和写入大块数据有良好的性能，所以一般被用在文件系统及数据库中，具有以下特点：

• 所有键值分布在整颗树中
• 任何一个关键字出现且只出现在一个结点中
• 搜索有可能在非叶子结点结束
• 在关键字全集内做一次查找,性能逼近二分查找

普通的AVL或者红黑树的效率已经很高了，但当数据量较大时，如果数据无法全部加载到内存中，也就无法完成树的平衡。

1.2 原理

B-树为了减少磁盘的IO次数，将整个数据分割为多个区间，在新建节点时，直接申请页大小的空间（磁盘存储单位是按 block 分的，一般为 512 Byte。磁盘 IO 一次读取若干个 block，我们称为一页，具体大小和操作系统有关，一般为 4k，8k或 16k），计算机内存分配是按页对齐的，这样就实现了一个节点只需要一次 IO

同时，B-树的多节点设计也降低了树的高度，提升了效率

B树

2. B+树

2.1 概念

B+树是B-树的变体，也是一种多路搜索树, 它与 B- 树的不同之处在于：

• 有关键字存储在叶子节点出现,内部节点(非叶子节点）并不存储真正的数据
• 所有叶子结点增加了一个链指针

B+树

2.2 索引

MySQL中的B+索引会对主键进行构建，每个主索引的叶子节点记录着完整的数据记录，这种方式被成为聚簇索引。因为不能把数据放在两个地方，所以一个表只有一个聚簇索引。

辅助索引的叶子结点记录主索引的值。