多路查找树（B树、B+树）
我们前面讨论的红黑树，处理数据都是在内存中，因此考虑的都是内存中的运算时间复杂度。但若我们要操作的数据集非常大，大到内存已经没办法处理了怎么办呢？
如数据库中的上千万条记录的数据表、硬盘中的上万个文件等。
这种情况下，对数据的处理需要不断从硬盘等存储设备中调入或调出内存页面，一旦涉及到这样的外部存储设备，关于时间复杂度的计算就会发生变化，访问元素的时间已经不仅仅是寻找该元素所需比较次数的函数，我们必须考虑对硬盘等外部存储设备的访问时间以及将会对该设备做出多少次单独访问。
试想一下，为了要在一个拥有几十万个文件的磁盘中查找一个文本文件，你设计的算法需要读取磁盘上万次还是读取几十次，这是有本质差异的，此时为了降低对外存设备的访问次数，我们就需要新的数据结构来处理这样的问题，B树B+树（n叉树）
B树的本质是通过降低树的层高，减少对磁盘访问次数，来提升查询速度。
B树
B树（B-tree）是⼀种平衡的多路查找树，结点最⼤的孩⼦数⽬称为B树的阶
B树所有节点即存储key也存储value
⼀个M阶的B树T，满足以下条件：
- 每个结点至多拥有M棵子树
- 根结点至少拥有两棵子树
- 除了根结点以外，其余每个分支结点至少拥有M/2棵子树
- 所有的叶结点都在同一层上
- 有K棵子树的分支结点存在k-1个关键字，关键字按照递增顺序进行排序
- 关键字数量满足ceil(M/2)-1 <= n <= M-1
B+树
B+树只有在叶子节点存储数据value（叶子节点放在磁盘中），非叶子节点用来做索引key（非叶子结点在内存中），相比于B树，B+树更适合做磁盘索引，在大数据的存储和查找中使用较多。
标签：结点,多路,查找,内存,磁盘,节点 From： https://www.cnblogs.com/go-ahead-wsg/p/16771856.html