补充资料：磁盘和B+树

为什么关系型数据库都选择了B+树，这个和磁盘的特性有着非常大的关系。

一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动。盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元也是最小读写单元。现在磁盘扇区一般是512个字节~4k个字节。
磁盘上数据必须用一个三维地址唯一标示：柱面号、盘面号、扇区号。读/写磁盘上某一指定数据需要下面步骤：
(1) 首先移动臂根据柱面号使磁头移动到所需要的柱面上，这一过程被称为定位或查找。
(2)所有磁头都定位到磁道上后，这时根据盘面号来确定指定盘面上的具体磁道。
(3) 盘面确定以后，盘片开始旋转，将指定块号的磁道段移动至磁头下。
经过上面步骤，指定数据的存储位置就被找到。这时就可以开始读/写操作了。

可以看见，磁盘读取依靠的是机械运动，分为寻道时间、旋转延迟、传输时间三个部分，这三个部分耗时相加就是一次磁盘IO的时间，一般大概9ms左右。寻道时间（seek）是将读写磁头移动至正确的磁道上所需要的时间，这部分时间代价最高；旋转延迟时间（rotation）是磁盘旋转将目标扇区移动到读写磁头下方所需的时间，取决于磁盘转速；数据传输时间（transfer）是完成传输数据所需要的时间，取决于接口的数据传输率，在纳秒级，远小于前两部分消耗时间。磁盘读取时间成本是访问内存的几百倍到几万倍之间。
为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存，这个称之为预读。这样做的理论依据是计算机科学中著名的局部性原理：
当一个数据被用到时，其附近的数据也通常会马上被使用。
程序运行期间所需要的数据通常比较集中。

大家可以试运行下面这段代码：

public static void main(String[] args) {
	int[][] arr = new int[10000][10000];
	int sum = 0;
	long startTime = System.currentTimeMillis();
	for (int i = 0; i < arr.length; i++) {
		for (int j = 0; j < arr[0].length; j++) {
			/*按行访问数组*/
			sum += arr[i][j];
		}
	}
	System.out.println("按行耗时：" + (System.currentTimeMillis() - startTime) + "ms");
	sum = 0;
	startTime = System.currentTimeMillis();
	for (int i = 0; i < arr.length; i++) {
		for (int j = 0; j < arr[0].length; j++) {
		/*按列访问数组*/
		sum += arr[j][i];
		}
	}
	System.out.println("按列耗时：" + (System.currentTimeMillis() - startTime) + "ms");
}

就能看到局部性原理对程序性能的影响。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），一般来说，磁盘的顺序读的效率是随机读的40到400倍都有可能，顺序写是随机写的10到100倍（SSD盘则差距要小的多，顺序读写的效率是随机读写的7到10倍，但是有评测表明机械硬盘的顺序写性能稍优于SSD。总的来说Mysql数据库如果由硬盘由机械的换成SSD的，性能会有很大的提升），因此对于具有局部性的程序来说，预读可以提高I/O效率。预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页，页大小通常为4k当然也有16K的，主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
按照磁盘的这种性质，如果是一个页存放一个B+树的节点，自然是可以存放很多的数据的，比如InnoDB里，默认定义的B+树的节点大小是16KB，这就是说，假如一个Key是8个字节，那么一个节点可以存放大约1000个Key，意味着B+数可以有1000个分叉。同时InnoDB每一次磁盘I/O，读取的都是 16KB的整数倍的数据。也就是说InnoDB在节点的读写上是可以充分利用磁盘顺序IO的高速读写特性。同时按照B+树逻辑结构来说，在叶子节点一层，所有记录的主键按照从小到大的顺序排列，并且形成了一个双向链表。同一层的非叶子节点也互相串联，形成了一个双向链表。那么在实际读写的时候，很大的概率相邻的节点会放在相邻的页上，又可以充分利用磁盘顺序IO的高速读写特性。所以我们对MySQL优化的一大方向就是尽可能的多让数据顺序读写，少让数据随机读写。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/94905.html

08-高性能表结构及索引设计最佳实践-05

补充资料：磁盘和B+树

相关推荐