B树概括来说是一个节点可以拥有多于2个子节点的平衡多路查找树。与自平衡二叉查找树不同,B树为系统最优化大块数据的读和写操作,普遍运用在数据库和文件系统。
说明:
1、B树的阶:节点的最多子节点个数。比如2-3树的阶是3,2-3-4树的阶是4
2、B树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点。
3、关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据。
4、搜索有可能在非叶子结点结束。
5、其搜索性能等价于在关键字全集内做一次二分查找
B树又叫平衡多路查找树,一棵m阶的B 树 (m叉树)的特性如下:
1、每个结点最多m个子结点。
2、除了根结点和叶子结点外,每个结点最少有m/2(向上取整)个子结点。
3、如果根结点不是叶子结点,那根结点至少包含两个子结点。
4、所有的叶子结点都位于同一层。
5、每个结点都包含k个元素(关键字),这里m/2≤k
7、每个元素(关键字)字左结点的值,都小于或等于该元素(关键字)。右结点的值都大于或等于该元素(关键字)。
