1、数据结构分析

每个表都会有自己的主键，一般为id如果没有，存储引擎会自己维护一个唯一自增id,子所以会先说这个，是因为这个点对数据存储很重要，下面会讲

在说说mysql表的结构，这里引用到这篇文章https://www.cnblogs.com/bdsir/p/8745553.html

mysql数据都是按行存储的（数据存储：分位按行【数据所有字段都在一行】、列【即每个字段数据存在一列】），而行数据存储在每个InnoDB数据页中，每个数据页16kb,存储一定行数的数据,数据也之间通过指针上下关联;

数据页

页（Page）是 Innodb 存储引擎用于管理数据的最小磁盘单位。常见的页类型有数据页、Undo 页、系统页、事务数据页等，我在这里说的都是数据页。默认的页大小为 16KB，每个页中至少存储有 2 条或以上的行记录，

每行数据维护在表中不仅仅是我们看到的字段，其实还有一些其他信息，这些信息辅助我们去查询数据，从物理空间获取数据如下：

InnoDB数据页由以下7个部分组成，

File Header（文件头）38个字节：

其中比较重要的是 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 字段让页之前形成双向链表

行溢出

我们知道数据页的大小是 16KB，Innodb 存储引擎保证了每一页至少有两条记录，如果一页当中的记录过大，会截取前 768 个字节存入页中，其余的放入 BLOB Page。

Page Header （页头）56个字节（辅助我们理解查询的重点）

这部分保存了该页中行记录的大量细节信息可以查阅文章：https://blog.csdn.net/Poisx/article/details/98109497

User Record（用户记录，即行记录）

读取数据时会先内存先加载页所在空间，然后在获取行记录

Free Space（空闲空间）

Page Directory（页目录）：这就相当于书签

File Trailer （文件结尾信息）8个字节

B+树索引本身并不能找到具体的一条记录，B+树索引能找到指数该记录所在的页。数据库把页载入内存，然后通过Page Directory在进行二叉查找。只不过二叉查找的时间复杂度很低，同时内存中的查找很快，因此通常我们忽略了这部分查找所用的时间。

磁盘读取

摘自https://www.cnblogs.com/xll1025/p/11405130.html

为了加快Col2的查找，可以维护一个右边所示的二叉查找树（实际不仅仅如此，右边的二叉树先查到页所在信息，在去找业内行数据），每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在O(log2n)O(log2n)的复杂度内获取到相应数据。

索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

为什么要B树

磁盘中有两个机械运动的部分，分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟，而磁盘移动则是在盘片旋转到指定位置以后，移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程，而定位是磁盘的存取中花费时间比较大的一块，毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候，显然定位是一个非常花费时间的过程，但是我们可以通过B树进行优化，提高磁盘读取时定位的效率。

为什么B类树可以进行优化呢？我们可以根据B类树的特点，构造一个多阶的B类树，然后在尽量多的在结点上存储相关的信息，保证层数尽量的少，以便后面我们可以更快的找到信息，磁盘的I/O操作也少一些，而且B类树是平衡树，每个结点到叶子结点的高度都是相同，这也保证了每个查询是稳定的。

局部性原理与磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。