多路查找树(B树) 多路查找树每一个结点的孩子数可以多于两个,且每一个结点处可以存储多个元素。 有几种特殊形式: 2-3树 2-3-4树 类似2-3树。 B树 B树是一种平衡的多路查找树。2-3树和2-3-4树都是B树的特例。 结点最大的孩子数目称为B树的阶(order)。 在一个典型的B树应用中,要处理的硬盘数据量很大,因此无法一次全部装入内存。我们可以将B树的阶数或结点的元素与硬盘存储的页面大小相匹配。 B树的数据结构就是为内外存的数据交互准备的。 缺点:往返于每个结点之间意味着得在硬盘的页面之间进行多次访问。 B+树 http://www.bluerwhite.org/btree/