MySQL索引的数据结构
为什么MySQL使用的是B+Tree结构
1. 为什么不使用二叉树？
如果遇到以下单边增长的极端情况，则搜索节点4与顺序搜索没有什么不同. (在这种特殊情况下，二叉树等效于链表，时间复杂度为O(n))。
2. 为什么不使用红色和黑色的树？
红黑树是平衡的二叉树. 当数据量很大时，树的深度也很深. 如果树的深度为20层，并且搜索的数据在叶节点中，则需要20个IO操作性能低下。
3. 为什么不使用B树？
实际上，B树是水平方向上的商品. 一个节点可以存储更多数据(大节点包含许多小节点)，因此深度会相对变浅。
为什么不能无限增加B树的水平度
通过IO操作将大型节点加载到内存中. 如果大节点的数据量太大，则无法通过内存和硬盘之间的一次交互来交换这么多的数据，假设一次只能交换一页(8k)数据，这意味着CPU只能取一页数据用于硬盘上的IO操作。然后，当大节点的数据量太大时，仍然会有多个IO操作。因此，度数有上限，MySQL会根据计算机硬件自动优化度数，大节点通常为1页空间。
为什么要使用B +树？
非叶节点仅存储索引的一个值并且不存储数据(B树将存储数据)，并且确定了大节点的大小，所以大节点可以存储更多数据，这可以变得更大. 这不仅保证了最大程度，而且还确保可以通过IO操作将大型节点加载到内存中. (非叶节点的度数较大且深度较浅. 只有非叶节点会影响搜索次数，叶节点是最后一次搜索，对搜索总数没有影响. 因此，所有数据都移至叶子节点)。
为什么我们在叶节点之间需要指针？
方便的范围查询例如，在上图中搜索key> 18非常麻烦. 如果没有指针，则必须从头开始搜索. 如果有指针，则可以使用键> 18直接遍历叶节点(链接列表)。
4.MySQL的底层如何使用B +树存储数据？
MySQL有两个常见的存储引擎: InnoDB(默认)，MyISAM索引数据结构，存储引擎范围是表级。
1.MyISAM(非聚集索)
.frm是表结构文件，.MYD是数据文件(MyISAM数据)，. MYI是索引文件(MyISAM索引).
MyISAM主键索引搜索过程: 首先通过.MYI文件找到对应索引的文件指针，然后根据文件指针在.MYD文件中找到对应的数据行。
2. InnoDB索引的实现(聚合)
.frm是表结构文件，.ibd是数据和索引文件(InnoDB数据)，InnoDB主键索引搜索过程: 通过.ibd文件查找对应的索引，并且索引的值是与该行相对应的完整数据。
InnoDB通用索引搜索过程: 通过.ibd文件查找对应的索引，索引的值为该行对应的主键的值，然后根据主键索引树查找对应的行数据到主键的值。