搜索树

B-tree

B 树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。在降低磁盘I/0操作方面要好一些。许多数据库系统都一般使用B树或者B树的各种变形结构，如B+树。

B树与红黑树最大的不同在于，B树的结点可以有许多子女，从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样，一棵含n个结点的B树的高度也为O（lgn），但可能比一棵红黑树的高度小许多，应为它的分支因子比较大。所以，B树可以在O（logn）时间内，实现各种如插入（insert），删除（delete）等动态集合操作。