B树插入:
假如是m阶B树,插入关键字时都要满足每个节点上的关键字个数最少为m/2向上取整-1关键字,最多有m-1个关键字,且每次插入的新元素一定是放在最底层的终端节点(因为如果不是放在终端节点,会导致该节点上可能有叶子节点,则就不满足B树的叶子节点一定在最下层的特性了)
如下例子是5阶B树即m=5,则每个节点的关键字个数满足2<=n<=4
先插入25关键字,然后插入38,38>25,则插入在25的后边,插入49关键字,49>38,49放在38的后边,插入60,60>49,60放在49的后面,以上插入元素节点上的关键字个数都满足>=2且<=4
插入关键字80,80>60,则80放在60的后边,此时该节点上关键字的个数为5>4,则开始节点分裂调整。调整时使用m/2向上取整即5/2向上取整为3,从第3个位置将关键字分为2部分,左部分关键字放在原节点中,右部分关键字放到新节点中,中间位置m/2向上取整位置即第3个位置的节点插入原节点的父节点,因为原节点没有父节点,所以要向上新建个节点作为父节点。即从第3个位置即从49开始分成2部分,49左部分的25、38还在原节点,49右部分的60、80放到新节点,49关键字放到新节点且作为原节点的父亲,即49变成(25、38)节点和(60、80)节点父亲。
插入关键字90,从根节点49开始,90一定插入在最底层的终端节点,49旁边已经没有其他关键字了且90>49,90则要插入49右边的指针指向的节点上,然后开始比较关键字大小来确定具体放的位置,90>60,放在60后边,90>80,则90放在80后边,继续插入关键字99
插入关键字88,从根节点49开始,88一定插入在最底层的终端节点,49旁边已经没有其他关键字了且88>49,88则要插入49右边的指针指向的节点上,然后开始比较关键字大小来确定具体放的位置,88>60,放在60后边,88>80,则88放在80后边,88<90,则88放在90前边,即88放在80后边,此时该节点上关键字的个数为5>4,则开始节点分裂调整。调整时使用m/2向上取整即5/2向上取整为3,即从第3个位置即从88开始分成2部分,88左部分的60、80还在原节点,88右部分的90、99放到新节点,88关键字向上提到原节点的父节点中,即把88放到49关键字所在节点中,具体88放在指向该节点的分叉所属的指针黑点右边的位置,即88放在49后边的位置,且让88关键字右边的指针指向新节点(90,99),留在原节点的(60,80)指向啥的不变,还是让以前的指针指向该节点。这样能保证B树特性,即该关键字左边指针指向的节点上的关键字都<该关键字,该关键字右边指针指向节点上的关键字都>该关键字