多路查找树

1. 适用范围:

1. 减少相同结点数量下树的深度
2. 存储大量数据(内存已经储存不下了), 需要存储到硬盘中
3. 需要减少磁盘IO的访问时间

2. 梗概:

一个特殊的查找树:

1. 一个结点存储多个关键字
   1. 关键字从左往右升序
2. 每个关键字都有左右子树
   1. 左子树中的所有关键字<关键字<右子树的所有关键字
3. 除了首位两颗子树, 中间的子树都同时被相邻的两个关键字共用
   1. 即同时作为左边关键字的右子树
   2. 也同时作为右边关键字的左子树

3. 特殊的多路查找树

1. B-树
   1. child::B树 B-树