磁盘的读写原理

系统将文件存储到磁盘上时，按柱面、磁头、扇区的方式进行，即最先是第 1 磁道的第一磁头下的所有扇区，然后是同一柱面的下一个磁头……

一个柱面存储满后就推进到下一个柱面，直到把文件内容全部写入磁盘。

系统也以相同的顺序读出数据，读出数据时通过告诉磁盘控制器要读出扇区所在柱面号、磁头号和扇区号（物理地址的三个组成部分）进行。

减少I/O的预读原理

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费的时间，磁盘的存取速度往往是主存的几百分之一。

因此，为了提高效率，要尽量减少磁盘的 I/O。

磁盘往往不是严格地按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。

计算机科学中著名的局部性原理：

1、当一个数据被用到时，其附近的数据一般来说也会被马上使用。

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

3、磁盘顺序读取的效率很高（不需要寻道时间，只需要很少的旋转时间），因此对于具有局部性

的程序来说，预读可以提高 I/O 效率。

预读的长度一般为页（Page）的整数倍。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储分割为连续的大小相等的块。

每个存储块称为一页（在许多操作系统中，页的大小通常为 4k），主存和磁盘以页为单位交换数据，当程序要读取的数据不在主存中时，会触发一个缺页异常。

此时系统会向磁盘发出读盘信息，磁盘会找到数据的起始位置并向后连续读取一页或几页的数据载入内存中，然后异常返回，程序继续运行。

MySQL的索引

索引是一种用来实现 MySQL 高效获取数据的数据结构。

我们通常所说的在某个字段上建索引，意思就是让 MySQL 对该字段以索引这种数据结构来存储，然后查找的时候就有对应的查找算法。

建索引的根本目的是为了查找的优化，特别是当数据很庞大的时候，一般的查找算法有顺序查找、折半查找、快速查找等。

但是每种查找算法都只能应用于特定的数据结构之上，例如顺序查找依赖于顺序结构，折半查找通过二叉查找树或红黑树实现二分搜索。因此在数据之外，数据库系统还维护着满足特定查找算法的数据结构。

这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。

MySQL的B+Tree

目前大多数数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构。

B+ 树索引是 B+ 树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+ 树中的 B 代表平衡，而不是二叉。

因为 B+ 树是从最早的平衡二叉树演化而来的。B+ 树是由二叉查找树、平衡二叉树（AVLTree）和平衡多路查找树（B-Tree）逐步优化而来。

二叉查找树：左子树的键值小于根的键值，右子树的键值大于根的键值。

AVL 树：平衡二叉树（AVL 树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为 1。

平衡多路查找树（B-Tree）：为磁盘等外存储设备设计的一种平衡查找树。

系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一磁盘块中的数据会被一次性读取出来，而不是按需读取。

InnoDB 存储引擎使用页作为数据读取单位，页是其磁盘管理的最小单位，默认 page 大小是 16k。

系统的一个磁盘块的存储空间往往没有这么大，因此 InnoDB 每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小 16KB。

InnoDB 在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能助于定位数据记录的位置，这将会减少磁盘 I/O 的次数，提高查询效率。

MySQL 的 InnoDB 存储引擎在设计时是将根节点常驻内存的，因此力求达到树的深度不超过 3，也就是说 I/O 不需要超过 3 次。

分析上面过程，发现需要 3 次磁盘 I/O 操作，和 3 次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。

而 3 次磁盘 I/O 操作是影响整个 B-Tree 查找效率的决定因素。

B-Tree 相对于 AVLTree 缩减了节点个数，使每次磁盘 I/O 取到内存的数据都发挥了作用，从而提高了查询效率。

B+Tree 是在 B-Tree 基础上的一种优化，使其更适合实现外存储索引结构，InnoDB 存储引擎就是用 B+Tree 实现其索引结构。

在 B-Tree 中，每个节点中有 key，也有 data，而每一个页的存储空间是有限的，如果 data 数据较大时将会导致每个节点（即一个页）能存储的 key 的数量很小。

当存储数据量很大同样会导致 B-Tree 的深度较大，增大查询时的磁盘 I/O 次数，进而影响查询效率。

在 B+Tree 中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样可以大大加大每个节点存储的 key 值数量，降低 B+Tree 的高度。

B+Tree 在 B-Tree 的基础上有两点变化：

1、数据是存在叶子节点中的；

2、数据节点之间是有指针指向的。

由于 B+Tree 的非叶子节点只存储键值信息，假设每个磁盘块能存储 4 个键值及指针信息，则变成 B+Tree 后其结构如下图所示：

通常在 B+Tree 上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。

因此可以对 B+Tree 进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

InnoDB中的B+Tree

InnoDB 是以 ID 为索引的数据存储。

采用 InnoDB 引擎的数据存储文件有两个，一个定义文件（.frm格式的文件），一个是数据文件（.idb格式的文件）。（Myisam 的存储文件有三个，后缀名分别是 .frm、.MYD、MYI，其中 .frm 是表的定义文件，.MYD 是数据文件，.MYI 是索引文件。）

InnoDB 通过 B+Tree 结构对 ID 建索引，然后在叶子节点中存储记录。



若建索引的字段不是主键 ID，则对该字段建索引，然后在叶子节点中存储的是该记录的主键，然后通过主键索引找到对应的记录。

引用

深入理解mysql的底层实现