B树
B树的概念
B树是一种平衡的多路搜索树,多用于文件系统、数据库实现
B树的特点
一个节点可以存储超过两个元素,可以拥有超过2个子节点;而二叉树的每个节点最多可以存储1个元素,并且一个父节点不能拥有超过2个子节点拥有二叉搜索树的一些性质平衡,每个节点的所有子树高度一致树的高度相比二叉树不会更高
m阶B树的性质(m>=2)
假设一个节点存储的元素个数为X根节点:1 <= x <= x-1非根节点:clie(m/2) - 1 <= x <= x-1如果有子节点,子节点个数 y = x + 1根节点:2 <= y <= m非根节点:clie(m/2) <= y <= m例如
m=3, 2<=y<=3,称为(2,3)树,2-3树,3阶树m=4, 2<=y<=4,称为(2,4)树,2-4树,4阶树m=5, 3<=y<=5,称为(3,5)树,3-5树,5阶树
红黑树 ~~ 4阶B树(2-3-4树)
所有节点能存储的元素个数x: 1<=x<=3,一个节点可以存储三个元素所有非叶子节点的子节点个数y: 2<=y<=4, 非叶子节点可以有四个子节点