一般来说，索引本身也很大，不可能全部储存在内存中，因此索引往往以索引档案的形式储存的磁盘上。这样的话，索引查询过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查询过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查询过程中磁盘I/O的存取次数。
一个磁盘由大小相同且同轴的圆形碟片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。
磁盘结构
磁盘的操作：
寻道：读写头连线到一个传动臂的一端。通过沿着半径轴前后移动传动臂，驱动器可以将读写头定位到任何磁道上（碟片不动，磁头动）旋转：一旦定位到磁道后，碟片转动，磁道上的每个位经过磁头时，读写磁头就可以感知到位的值，也可以修改值（磁头不动，碟片动）磁盘的储存概念：
扇区：每个同心环叫做一个扇区，扇区是磁盘的最小储存单元。当需要从磁盘读取资料时，系统会将资料逻辑地址传给磁盘，磁盘的控制电路按照定址逻辑将逻辑地址翻译成实体地址，即确定要读的资料在哪个磁道，哪个扇区。为了读取这个扇区的资料，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间；然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。页：由于储存介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的资料放入内存。预读可以提高I/O效率。预读的长度一般为页（page：计算机管理储存器的逻辑块-通常为4k）的整倍数. 主存和磁盘以页为单位交换资料。当程式要读取的资料不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘讯号，磁盘会找到资料的起始位置并向后连续读取一页或几页载入内存中。区域性性原理
这样做的理论依据是电脑科学中著名的区域性性原理：当一个数据被用到时，其附近的资料也通常会马上被使用。
也就是说，程式执行期间所需要的资料通常比较集中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有区域性性的程式来说，预读可以提高I/O效率。
档案系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在B+Tree每次新建一个节点的同时，直接申请一个页的空间，这样就保证一个节点物理上也储存在一个页里，加之计算机储存分配都是按页对齐的，就实现了一个node只需一次I/O。
