MySQL B+树相对于B树的区别及优势：_mysql b+树的优点,和b树的区别

部分参考：B树和B+树的区别

MySQL为什么使用树结构？

1. 文件很大，不可能全部存储在内存中，故要存储到磁盘上
2. 索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数（为什么使用B-/+Tree，还跟磁盘存取原理有关）
3. 局部性原理与磁盘预读，预读的长度一般为页（page）的整倍数（操作系统内存页的大小通常为4k）。其中MySQL B+树中的 叶/非叶节点 都是以MySQL的页为单位（大小通常也为16k），存放完整行记录。
4. 数据库系统巧妙利用了磁盘预读原理，将一个节点大小设为操作系统内存页的整数倍，这样每个节点只需要一次I/O就可以完全载入。而红黑树这种结构，高度明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性。

参考：磁盘读取

        计算机系统是分页读取和存储的，一般一页为4KB（8个扇区，每个扇区512B，8*512B=4KB），每次读取和存取的最小单元为一页，而磁盘预读时通常会读取页的整倍数。

        根据文章上述的【局部性原理】①当一个数据被用到时，其附近的数据也通常会马上被使用。②程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），所以即使只需要读取一个字节，磁盘也会读取一页的数据。

        MySQL InnoDB默认的页大小为16k（可通常 innodb_page_size 参数设置），而操作系统中的磁盘页大小通常为4k，所以这里可以认为MySQL InnoDB中的1页（1个磁盘块）相当于操作系统中的4页。

        这也就符合MySQL InnoDB所利用到的磁盘预读通常会预读操作系统页的整数倍（4倍）。具体如下图：

       最外层浅蓝色磁盘块1里有数据17、35（深蓝色）和指针P1、P2、P3（黄色）。P1指针表示小于17的磁盘块，P2是在17-35之间，P3指向大于35的磁盘块。真实数据存在于叶子节点也就是最底下的一层3、5、9、10、13......非叶子节点不存储真实的数据，只存储指引搜索方向的数据项，如17、35。

      查找过程：例如搜索28数据项，首先加载磁盘块1到内存中，发生一次I/O，用二分查找确定在P2指针。接着发现28在26和30之间，通过P2指针的地址加载磁盘块3到内存，发生第二次I/O。用同样的方式找到磁盘块8，发生第三次I/O。

      真实的情况是，上面3层的B+Tree可以表示2k万的数据，这种量级的数据只发生了三次I/O，时间提升是巨大的。

B树和B+树的区别：

1. B树的每个节点都存储了key和data，而B+树的data存储在叶子节点上。
   B+树非叶子节点仅存储key不存储data，这样一个节点就可以存储更多的key。可以使得B+树相对B树来说更矮（IO次数就是树的高度），所以与磁盘交换的IO操作次数更少。
2. B+树所有叶子节点构成一个有序链表，按主键排序来遍历全部记录，能更好支持范围查找。
   由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历，相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
3. B+树所有的查询都要从根节点查找到叶子节点，查询性能更稳定；而B树，每个节点都可能查找到数据，需要在叶子节点和内部节点不停的往返移动，所以不稳定。