B树 和 B+树 与磁盘读写之间的联系

Question

在前面的文章中我们分别介绍了 B-树和 B+树的应用原理，B 树实际上就是一颗多路查找树，每一个结点都保存多个元素。保存多个元素是为了尽可能降低树的高度，以降低查询时磁盘 IO 次数。但是有人就会问了，我们将所有元素放在一个节点中那不就最大限度的降低树的高度吗？

说到这里我们就需要来讲解一下局部性原理与磁盘预读。

局部性原理与磁盘预读

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

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

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

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

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

B 树与 B+树与磁盘读写之间的联系

内存和磁盘既然是以页为单位交换数据，那么 B 树的节点大小保持页的大小是最优选择，既尽量的降低了节点读取后的内存占用，又尽可能利用了磁盘一次 IO 所读取的数据。

B 树： 我们假设如果是 4 阶的，那么每个结点最多 3 个关键字，最少两个（根节点最少 1 个），也就是说，我们最多也就要访问 3 次磁盘就可以完成访存，而传统的访存需要每一个关键字都进行访存，可以看出 B 树的优势。注意：B 树的非叶结点不单单只有 key 值，还有 key 对应数据在磁盘的具体地址。

B+树： 相对与 B 树而言，B+树的非叶结点值只存有 key 值，不含有卫星数据，比较而言就会有更大的空间，就可以存更多的 key 值，就会显得更加 矮胖，矮了磁盘 IO 次数就相对会更少一些。同时由于 B+树增加了一个最小关键字的根结点，所以顺序访问更加便捷。