【C/C++】MySQL 为什么选择 B+ 树作为底层数据结构

为什么MySQL底层数据结构选择B+树？（而不是B树等其他数据结构）

B+树非叶子节点，不存放数据记录，仅存放指针与关键字，所以一个B+树非叶子节点可以存放更多子节点信息，有利于降低树高度，从而减少搜索IO次数。
相反，B树的叶子节点与非叶子节点数据结构一致（存放 数据记录+子节点指针 + 关键字），导致，B树非叶子节点可存放子节点指针空间减少，树高度增高，IO次数增多，性能降低。故，不选择。

为什么树越高，磁盘IO次数越多？

InnoDB 存储引擎存在自身文件管理机制，其最小存储单位为页（Page）, 大小为 16KB。页，即为B+树中节点存储结构。所以，B+ 树越高，层级节点搜索次数越多，对应的磁盘IO次数随之增多，引擎性能随之降低。

扩展：
计算机中磁盘存储数据最小单元是扇区，一个扇区的大小是 512字节 。文件系统（如XFS/EXT4）最小单元是块，一个块的大小是 4KB。

【经典问题】

一颗B+树一般可以存放多少条数据记录？

1. InnoDB 页的默认大小 16KB；
2. InnoDB 主键ID bigint 类型大小为 8 Bytes；
3. InnoDB 中指针大小为 6 Bytes；
4. 互联网业务数据记录大小通常为 1KB;
5. 叶子节点只放置数据记录数量：16KB / 1KB = 16;

开始计算：
假设 Mysql B+ 树高为 3 层。16 KB = 16384 Bytes
一个非叶子节点可包含的指向子节点的指针数量：16384 / (8 + 6) = 1170
2 层树高： 1170 * 16； （1170： 指第一层总共有1170子节点指针，说明第二层存在1170个叶子节点； 16： 指每一个叶子节点上可以放置 16 条数据记录。所以，2层树高的B+树，可以存放 1170 * 16 条数据记录）。
3 层树高：1170 * 1170 * 16; （与上同理。新增了一层非叶子节点，则需要多乘以一层的子节点数量，这里就已经满足千万级别数据量的数据库）。