数据结构——B树

    技术2022-07-17  85

    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, 非叶子节点可以有四个子节点
    Processed: 0.008, SQL: 9