由于机械磁盘的特性,磁盘的存取速度比主存慢很多,往往是其的 几百分分之一,因此为了提高效率及减少磁盘 I/O,往往每次读取都会预读,即使读取一个字节,也需要从此往后读取一定长度的数据放入内存,预读的长度一般为页(page)的整数倍。而 B Tree 之所以高效,根据 B-Tree 的定义,可知检索一次最多需要访问 h 个节点,一次检索最多需要 h-1 次 I/O,渐进复杂度为 O(h) = O(logdN)。一般实际应用中,出度 d 是非常大的数字,通常超过 100, 因此 h 非常小(通常不超过3),所以 B-Tree 作为索引结构效率非常高