多路查找树的背景

  　　数组、堆、栈，链表、队列、二叉树，它们适用于较小的文件，是应用在内存中的数据结构。而对于较大的、存放在外存储器上的文件就不合适了，对于此类大规模的文件，即使是采用了平衡二叉树，在查找效率上仍然较低。

　　如果要操作的数据集非常大，大到内存已经没办法处理了，这种情况下，对数据的处理需要不断从硬盘等存储设备中调入或调出内存页面。一旦涉及到这样的外部设备，关于时间复杂度的计算就会发生变化，访问该集合元素的时间已经不仅仅是寻找该元素所需比较次数的函数，必须考虑对硬盘等外部存储设备的访问时间以及将会对该设备做出多少次的单独访问。

应用

B 树处于会用在少部分的文件索引（数据库索引）外，应用的最多的就是文件系统了。据库索引大部分用 B+ 树 。

1、由于 B 树的每一个节点，可以存放多个元素（23树是个B数特例，实际用的B数一般都是一个结点几十上百个元素的），所以磁盘寻址加载的次数会比较少，所以二叉树更时候外部存储，外部存储需要算上读取的时间开销（100个时钟周期）和读取方式（按页读取4K）。

实际上磁盘的加载次数，基本上是和树的高度相关联的，高度越高，加载次数越多，越矮，加载次数越少。所以对于这种文件索引的存储，我们一般会选择矮胖的树形结构。例如有 1000 个元素，如果是二叉查找树的话，高度可能高达 10 层,而如果用 10 阶 B 树的话，只需要三四层即可。

2、由于采用二叉链表存储所有，不同的的结点存放的位置可能会在不同的硬盘上，所有二叉树用在外存储效率更低。

{

1. 一次内存访问、SSD 硬盘访问和SATA 硬盘随机访问的时间分别约是几十纳秒，几十微秒，几十毫秒。

2. 访问内存一次是100个时钟周期以上，

}

问题

会导致不平衡，让多叉树的叉树的查找效率低下。类属于二叉树极端情况下退化成链表。

处理方式

引入平衡规则，于是就有B树和B+树