1. 文件存储结构

更多内容查看这里

2. 数据基本操操作

数据的基本操作包括：INSERT、UPDATE、DELETE、SELECT

SELECT

1. 定位数据
2. 读出数据所在的块，对数据加工
3. 返回数据给用户

UPDATE、DELETE

1. 定位数据
2. 读出数据所在的块，修改数据
3. 写回磁盘

INSERT

1. 定位数据要插入的页（如果数据需要排序）
2. 读出要插入的数据页，插入数据.
3. 写回磁盘

可以看到数据的基本操作都需要定位数据，那么我们改如何定位数据呢？

表扫描遍历：从磁盘中依次读出所有的数据块，一行一行的进行数据匹配,直到找到要匹配的数据。

可以看到上述定位数据的方式的时间复杂度是O(n)， 如果所有的数据占用了100个块。尽管只查询一行数据，也需要读出所有100个块的数据。这就需要大量的磁盘IO操作，极大的影响了性能

3. 局部性原理与磁盘预读

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

当一个数据被用到时，其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

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

4. 参考资料

《MySQL技术内幕 InnoDB存储引擎第二版》

http://blog.codinglabs.org/articles/theory-of-mysql-index.html

https://mp.weixin.qq.com/s/R1zhVWNFtrpCSzM6fPmbBg

https://mp.weixin.qq.com/s/aH87AiBmwCtSf6z9JBc4uQ