B树

B树是为磁盘或其他直接存储的辅存设备而设计的一种平衡搜索树。

B树类似于红黑树，但在降低磁盘I/O操作数方面要更好一些。许多数据库系统使用B树或者B树的变种来存储信息。

B树与红黑树的不同之处在于B树的结点可以有很多孩子，从数个到数千个。也就是说，一个B树的“分支因子”可以相当大，尽管它通常依赖于所使用的磁盘单元的特性。

每棵含有n个结点的B树的高度为O(lgn)。然而一棵B树的严格高度可能比一棵红黑树的高度要小许多，这是因为它的分支因子，也就是表示高度的对数的底数可以非常大。

因此我们也可以使用B树在时间O(lgn)内完成一些动态集合的操作。

B树以一种自然的方式推广了二叉搜索树。