解决方法
存在B-tree的主要原因是更好地利用读取和写入大块数据的设备的行为.当数据必须存储在磁盘上时,两个属性对于使B-Tree比二叉树更好：
>访问磁盘真的很慢(与内存或缓存相比,对磁盘上的数据的随机访问数量级更慢);和
>每次读取都会导致整个扇区从驱动器加载 – 假设扇区大小为4K,这意味着1000个整数,或者您正在存储的数十个较大的对象.
因此,我们可以利用第二个事实的优点,同时最大限度地减少磁盘访问的次数.
所以,我们可以创建一个更大的索引来告诉我们,如果我们应该继续到第一个1/100,再到第二个或第99页(想象图书馆按照他们的第一个字母排序,然后是第二个,依此类推).只要所有这些数据都适合单个部门,它将被加载,所以我们可以完全使用它.
这导致大致logB N查找,其中N是记录数.这个数字虽然与log2 N相同,但实际上与N和b足够小几倍,而且由于我们正在谈论将数据存储到磁盘中以用于数据库等,数据量通常很大足以证明这一点.
设计决策的其余部分主要是为了使这个工作有效地工作,因为修改N元树比二进制树更棘手.
