BTree又叫多路平衡搜索树,一颗m叉的BTree特性如下:

    • 树中每个节点最多包含m个孩子。
    • 除根节点与叶子节点外,每个节点至少有[ceil(m/2)]个孩子
    • 若根节点不是叶子节点,则至少有两个孩子。
    • 所有的叶子节点都在同一层。
    • 每个非叶子节点由n个key与n+1个指针组成,其中[ceil(m/2)-1]<=n<=m-1

    image.png
    image.png
    image.png

    image.png