数据结构-B树

    技术2022-07-13  68

    文章目录

    一、概念二、查找三、插入

    平衡二叉树不会退化为线性结构,所以查找效率高,在此基础上设计出了B树

    一、概念

    B树又称多路平衡查找树,B树中所有结点的孩子结点数的最大值称为B树的阶。

    一棵m阶B树或为空树,或为满足如下特性的m叉树:

    树中每个结点至多有m棵子树(即至多含有m-1个关键字)

    若根结点不是终端结点,则至少有两棵子树

    除根结点外的所有非叶结点至少有⌈m/2T⌉棵子树(即⌈m/2⌉-1 个关键字)

    非叶子节点结构:

    所有叶子节点(失败节点)都出现在同一层次上,并不带任何信息

    举例如下:

    3阶B树


    二、查找


    三、插入

    如果插入造成关键字数量大于m-1,则向上分裂:

    Processed: 0.022, SQL: 9