为什么mysql的innodb存储引擎选择了B+树，这个和磁盘的特性有着非常大的关系。

我们先来看下磁盘上的物理结构。

 

如果我们简化一下，可以这么看

再看几张模型图

 

 

一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动，各个磁盘必须同步转动，不然你转你的，我转我的，不就乱套了吗？

在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，能读取到磁盘的内容，是依靠于磁盘的转动。

这样说可能不太好理解，可以试着想象一下唱片机放歌时的场景，感觉差不多的道理。

盘片被划分成一系列同心环，主轴就是盘片中心，每个同心环都是一个磁道。每个磁道的外围都形成一个柱面。

磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元也是最小读写单元。现在磁盘扇区一般是512个字节~4k个字节。

磁盘上每个数据都必须用一个三维地址来标示，就是上面提到的：柱面号、盘面号、扇区号。

类似于我们使用的地图软件上的三维坐标，磁盘也有自己的坐标，这三个元素确定了，位置就确定了。

读/写磁盘上某一指定数据需要下面步骤：

(1)  首先根据柱面号，移动磁头支架，使磁头移动到相应的柱面上，这一过程被称为定位或查找。

(2)所有磁头都定位到柱面号对应的磁道上后，这时根据盘面号来确定指定盘面号上的具体磁道。

(3) 盘面确定以后，盘片开始旋转，将指定扇区号的磁道段移动至磁头下。

经过上面步骤，指定数据的存储位置就被找到了。这时就可以开始读/写操作了。

可以看见，磁盘读取依靠的是机械运动，分为寻道时间、旋转延迟、传输时间三个部分，这三个部分耗时相加就是一次磁盘IO的时间，一般大概9ms左右。

寻道时间（seek）是将读写磁头移动至正确的磁道上所需要的时间，这部分时间代价最高；

旋转延迟时间（rotation）是磁盘旋转将目标扇区移动到读写磁头下方所需的时间，取决于磁盘转速；

数据传输时间（transfer）是完成传输数据所需要的时间，取决于接口的数据传输率，在纳秒级，远小于前两部分消耗时间。

磁盘读取时间成本是访问内存的几百倍到几万倍之间。

既然这么慢，为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存，这个称之为预读。

这样做的理论依据是计算机科学中著名的局部性原理：

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

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

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），一般来说，磁盘的顺序读的效率是随机读的40到400倍都有可能，顺序写是随机写的10到100倍 。因此对于具有局部性的程序来说，预读可以提高I/O效率。因为程序接下来可能用到的数据已经提前预读进来了。

预读的长度一般为页（page）的整倍数。

页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页，页大小通常为4k当然也有16K的，主存和磁盘以页为单位交换数据。

当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后程序继续运行。

按照磁盘的这种性质，如果是一个页存放一个B+树的节点，自然是可以存放很多数据的，比如InnoDB里，默认定义的B+树的节点大小是16KB，这就是说，假如一个Key是8个字节，那么一个节点可以存放大约1000个Key。

同时InnoDB每一次磁盘I/O，读取的都是 16KB的整数倍的数据。也就是说InnoDB在节点的读写上是可以充分利用磁盘顺序IO的高速读写特性。

同时按照B+树数据结构来说，在叶子节点这一层，所有记录的主键按照从小到大的顺序排列，并且形成了一个双向链表。

同一层的非叶子节点也互相串联，形成了一个双向链表。

那么在实际读写的时候，很大的概率相邻的节点会放在相邻的页上，又可以充分利用磁盘顺序IO的高速读写特性。

所以我们对MySQL优化的一大方向就是尽可能的多让数据顺序读写，少让数据随机读写。