表数据文件本身就是按B+Tree组织的一个索引结构文件
聚集索引：叶子节点包含了完整的数据记录（而不是存放数据的磁盘地址），innodb的主键索引就是一个聚集索引（聚集：索引跟数据不是分开存储的，而是放在一个文件一起存储的，所以肯定比非聚集索引的效率高）。

InnoDB

底层应用b+tree结构

image.png

Frm文件：存储表结构
Ibd文件：存储索引和数据

image.png

B+Tree

问：为什么innodb必须有主键？
答：innodb设计就是按b+tree树设计的（设计表的时候没有显示声明主键，那么mysql会自动选一个字段（唯一的）作为主键；如果没有唯一键，那么会自动生成row_id作为主键（不可见））

问：为什么推荐使用整型的主键？
答：因为要比较大小，而用整型比较大小比较快，所以不推荐用uuid；另一方面，因为整型短，占用空间小

问：为什么主键要自增？
答：索引元素从左到右依次递增，保持主键自增，永远都是在最后面追加元素，而如果是插入一个中间元素，索引结构会做分裂和树平衡，而这些操作都是会影响性能的。

问：非主键索引是怎么建的？
答：非主键上建立索引，会同样建立一个b+tree，但是在叶子节点中，存的不是数据，而是主键，再通过主键去查找数据

问：联合索引的底层数据结构？
答：

问：什么是页分裂/页合并？
答：操作系统每次从磁盘里读数据都是按照4k的整数倍读取数据的，当某一页数据满了，而刚好要往这页插入一个中间数据，就会在要插入数据的地方进行页分裂，当数据插入后，再将页合并；再然后会将最后一条数据分裂出来，并合并到下一页。

MyIsam

底层应用b+tree结构，非主键上建立索引，也是最后存的主键，再通过主键找磁盘地址，再通过磁盘地址找对应数据。

image.png

一个表对应三个文件
Frm文件：存储表结构
MYD文件：存储数据
MYI文件：存储索引

image.png

B+Tree

Hash map