对于B+树而言,有一个重要的指标是B+树的阶数(order)。设B+树的阶数为M,则对于B+树而言,要满足以下条件:
这些条件可以不用都记住,在接下来的过程中会有更深入的理解。其实关键点在于,要理解在插入数据的过程中,如果溢出了要怎么处理。如果没有溢出,办法很简单,可以类比二叉树的插入方式,找到合适的位置,把数据加进去就可以了。对于溢出的情况,处理方式是对当前结点进行分裂。
要将当前叶子结点一分为二。第一个分裂出来的结点要储存ceil((m-1)/2)个键。第二个结点储存剩余的所有键。
依旧要将当前非叶子结点一分为二。第一个结点储存ceil(m/2)-1个键。将剩余键中的最小的键储存到父结点,其余键储存到第二个结点中去。由于涉及到对于父结点的数据插入操作,因为可能导致父结点数据溢出,该操作是要递归地进行处理的。