B树、B+树与磁盘读取的关系

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。

提出预读的概念

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

　　当一个数据被用到时，其附近的数据也通常会被使用。【空间局部性】

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

       当一个数据被用到时，程序执行后期该数据也通常会被使用。【时间局部性】

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

局部性原理的代码：

比如sum变量，每次循环都会用到，这就是时间局部性。
比如array数组，数组底层的存储是连续的，每次循环都是访问附近的数据，附近的数据马上会被用到。

public int sum(int[] array) {
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum = sum + array[i];
        }
        return sum;
}

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

索引

       当使用B、B+树进行查询时，涉及到将数据从磁盘读取到内存中。因为索引本身可能会非常大，不可能全部一口气存储在内存中，因此一般的解决方案都是将其分割成多个页（4k）。当查询需要访问索引时，系统会读取包含所需索引信息的页到内存中。
       为了提升性能，会涉及到预读取或缓冲池的技术。比如预读取，B+树中，存储数据的叶子结点之间是通过指针相连的双向链表，有利于顺序访问（或预读取）。

B、B+树

        这两种数据结构其实就是我们要构造的索引所用到的数据类型。
        在实际设计中，我们把一个结点设为一个页，因为磁盘预读是以页为单位的，所以这样的话一页就代表访问一次磁盘，也就是代表一次I/O操作。

B+树相对B树的优点和预读取有关，一次预读取就是一次磁盘IO。对于B+树来说，它的查询性能更加稳定，并且它的IO次数比较少，尤其是在做范围查询的时候比较简便。

为什么查询性能更加稳定：

结合B树和B+树的结构特点，B树的非叶子结点也会存储value，因为我们一个结点设为一个页嘛，固定大小（4k）存放的结点个数比较有限，导致B树相对B+树而言是高瘦类型，这样导致有的数据可能在一开始就读取到了，有的数据要到很后面才能读取到，这样就很不稳定，而B+树的数据都是在叶子节点，相对而言要稳定的多。

为什么它的IO次数较少：

结合上面，因为B树是高瘦类型，而B+树是矮胖类型。B+树单一节点存储更多的元素，使得查询的IO次数更少。

为什么在做范围查询更简便：

因为B+树底层是双向链表，这样我们对首个数据进行自顶向下的以页为单位的查找之后，对于范围查询，我们直接通过叶子结点本身是双向链表的特点，这样后续的数据不需要都进行自顶向下的查找，相对B树而言大大减少了IO次数。（因为每次自顶向下都会经历几次磁盘IO）