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树特性，即该关键字左边指针指向的节点上的关键字都<该关键字，该关键字右边指针指向节点上的关键字都>该关键字

 

插入关键字70，根节点49开始，77一定插入在最底层的终端节点，77>49且77<88，则77要插入49右边的指针88关键字左边指针指向的节点上，即60、70关键字所在的节点，然后开始比较关键字大小来确定具体放的位置，70>60，放在60后边，77<80，则77放在80前边，即77放在60后边80前边，此时该节点上关键字的个数为5>4，则开始节点分裂调整。调整时使用m/2向上取整即5/2向上取整为3,即从第3个位置即从80开始分成2部分，80左部分的(60,70)还在原节点，80右部分的(83,87)放到新节点，80关键字向上提到父节点中，即把80放到49关键字所在节点中，具体80放在指向该节点的分叉所属的指针黑点右边的位置，即80放在49后边的位置，且让80关键字右边的指针指向新节点(83,87)，留在原节点的(60,70)指针指向啥的不变，还是让以前的指针指向该节点。即当一个节点要分裂，要把该节点上的中间的关键字放到这个节点的父节点中，具体放的位置为指向该节点的分叉所属的指针黑点右边的位置，这样才能保证B树的特性。继续插入关键字93、94。

 

插入关键字99，如下所示插入到94后边的位置，此时99所在节点的关键字个数为5>4,开始调整，节点要分裂。调整时使用m/2向上取整即5/2向上取整为3,即从第3个位置即从93开始分成2部分，93左部分的(90,92)还在原节点，93右部分的(94,99)放到新节点，93关键字向上提到父节点中，即把93放到49关键字所在节点中，具体放的位置为指向该节点的分叉所属的指针黑点右边的位置，这样才能保证B树的特性。即把93放在88旁边的黑点的右边的位置即88的后边，再让93关键字右边的指针黑点指向(94,99)，留在原节点(90,92)的指针指向不变，还是让原指针指向(90,92)。继续插入关键字73,74

 

插入关键字75，如下所示插入到74后边的位置，此时74所在节点的关键字个数为5>4,开始节点分裂调整。调整时使用m/2向上取整即5/2向上取整为3,即从第3个位置即从73开始分成2部分，73左部分的(60,70)还在原节点，73右部分的(74,75)放到新节点，73关键字向上提到父节点中，即把73放到49关键字所在节点中，具体放的位置为指向该节点的分叉所属的指针黑点右边的位置，这样才能保证B树的特性。即把73放在原来指向该节点的黑点右边即88前边黑点后边位置，再让73关键字右边的指针黑点指向新节点(74,75)，留在原节点(60,70)黑点的指针指向啥的不变，此时父节点73所在位置关键字个数为5>4还要开始节点分裂调整。调整时使用m/2向上取整即5/2向上取整为3,即从第3个位置即从80开始分成2部分，80左部分的(49,73)还在原节点，80右部分的(88,93)放到新节点，80关键字向上提到父节点中，没有父节点就新建一个节点作为父节点再把80放进去。即把80放到新节点中，即新的父节点中只有80一个关键字，即此时根节点就只有一个关键字，但是也满足5阶B树的特性(详情可去看B树特性)。让80关键字右边的指针黑点指向新节点(88,93)，留在原节点(49,73)黑点的指针指向啥的不变。

B树删除：

所有非终端节点的关键字的删除都可转为终端节点的关键字删除，所以重点在于终端节点关键字的删除。

删除关键字60(删除终端节点关键字)：因为是终端节点关键字，则直接删除就行，删除后确定是否当前节点的关键字个数是否满足节点关键字下限，为5阶B树，则下限为2，此时删除60后，当前节点还有3个关键字，3>=2则依然满足下限

 

 删除关键字80(删除关键字在非终端节点)：

删除关键字为非终端节点关键字，则可用该节点的直接前驱或直接后继来代替被删除的关键字。

直接前驱：当前关键字左侧指针所指子树中最右下元素

如图2中80直接前驱为，80的左侧指针指向的是49关键字所在的节点，即该子树中最右下(最下一层的最右边)元素为77，即用77把80替换了，此时对非终端节点关键字删除的操作转成了对终端节点关键字删除的操作，因为原77所在节点上的77后边没有其他关键字了，所以不用再移动关键字了？？？

用直接后继代替删除的元素，假如删除左图3中的77关键字，即删除非终端节点上的关键字：

直接后继：当前关键字右侧指针所指子树中最左下元素

如图4中77的直接后继为，77右侧指针所指子树即为(88,93)所在节点，即该子树中的最左下(最下一层的最左边)元素为82，即用82把77替换了，此时对非终端节点关键字删除的操作转成了对终端节点关键字删除的操作，直接把82所在节点的关键字往前移动即可

删除38关键字(删除终端节点关键字，删除后当前节点关键字个数<下限，借右兄弟)：

当前节点缺关键字时，借当前节点的右兄弟节点的关键字。看缺关键字的节点的右兄弟节点的关键字个数是不是 很宽裕，宽裕的话用当前节点的后继(即指向当前节点的父节点的黑点后的第一个关键字)、后继的后继(即上边后继关键字右边的第一个黑点指向的节点的第一个关键字)来填补空缺，把当前节点的后继即指向当前节点的父节点的黑点后的第一个关键字填补到当前节点的所有关键字后边(因为填补的关键字是后继肯定比该待填补节点上的关键字值都大)，再把后继的后继即(即上边后继关键字右边的第一个黑点指向的节点的从左到右的第一个关键字)代替上述父节点被用来填补关键字的位置，再把后继的后继(即上边后继关键字右边的第一个黑点指向的节点的从左到右的第一个关键字)的所在节点上的关键字向前移动(因为少了一个关键字)

如下图删除关键字38了之后，38原本所在的节点的关键字个数==1<下限2，则要开始补充当前节点的关键字个数。删除关键字38了之后，38原本节点的关键字只剩25,25的右兄弟节点(70,71,72)关键字个数宽裕，可以从右兄弟借。找25的后继关键字即要从指向该节点的父节点查找即25的直接后继是25的父节点的第一个关键字49,49的后继要从49后边的指针指向的节点找，即49后边的指针指向的节点的第一个关键字70即为49的后继，让49的后继70代替49的位置，49补充到缺关键字的节点即25关键字的后边，然后再把原70所在节点的关键字依次往前移动。(这样补充是为了满足节点内部的关键字有序特性，不能直接把70放到25后边，那70>49了还在49的左边就不对了)

 

删除90关键字(删除终端节点关键字，删除后当前节点关键字个数<下限，借左兄弟)：

当前节点缺关键字时，借当前节点的左兄弟节点的关键字。看缺关键字的节点的左兄弟节点的关键字个数是不是很宽裕，宽裕的话用当前节点的前驱(即指向当前节点的父节点的黑点前的第一个关键字)、前驱的前驱(即上边的前驱关键字的左边第一个黑点指向的子节点上的最后一个关键字)来填补空缺，把当前节点的前驱(即指向当前节点的父节点的黑点前的第一个关键字)填补到缺关键字的节点的最前边，再把缺关键字的节点上的关键字都后移，后继的后继(即上边的前驱关键字的左边第一个黑点指向的子节点上的最后一个关键字)代替上述父节点的刚填补完空缺的关键字位置

如下图删除关键字90了之后，90原本所在的节点的关键字个数==1<下限2，则要开始补充当前节点的关键字个数。删除关键字90了之后，90原本节点的关键字只剩92,且此时90所在节点的右兄弟节点(94,99)关键字个数也不宽裕(借它一个，它又不满足下限了)，而当前节点的左兄弟节点(83,86,87)关键字个数宽裕，所以可以朝左兄弟借。92的前驱关键字要从指向该节点的父节点的黑点前的第一个关键字查找，即92的直接前驱是88,88的前驱要从88关键字前边的第一个黑点指针指向的子节点的最右的关键字找，即88前边的指针指向的子节点的最后一个关键字87即为88的前驱，让88填补到缺关键字92所在的节点中，然后92关键字向后移动，再让87补充到88的位置。

 

删除节点49(删除终端节点关键字，删除后当前节点关键字个数<下限，合体)：

当兄弟不够借时，把当前节点和兄弟节点以及当前节点和兄弟节点中间的那个父节点的关键字合并成一个节点，因为从父节点借了一个关键字，导致父节点的关键字个数-1，如果父节点是根节点且-1之后关键字个数为0，则删除根节点，如果不是根节点且导致父节点的关键字个数<下限，则需要调整父节点的关键字个数，继续把父节点+父节点的兄弟节点+2个节点中间的爷节点的一个关键字合并成一个节点，然后再判断借了一个关键字的爷节点是不是根节点+不是根节点的话，爷节点的关键字个数是否<下限，<下限的话要再次合并，直到满足要求。B树中的它的左子树所有关键字的值<当前关键字的值<它的右子树的所有关键字的值

如下图删除关键字49了之后，49原本所在的节点的关键字个数==1<下限2，则要开始补充当前节点的关键字个数。删除关键字49了之后，49原本节点的关键字只剩25,右兄弟节点(71,72)关键字个数也不宽裕，不够借。此时让当前缺关键字节点和右兄弟节点合体，并把这两个节点中间的关键字合并到一起，即(25)和(71,72)节点的中间的关键字的是70，把70放到25后边，把(71,72)放到70后边合成一个节点，此时因为从节点(70,73)扣了一个节点70，导致当前节点也不满足下限，则此时73所在节点也要分裂调整。即(73)的右兄弟节点(87,93)也不够借，也需要把这俩节点合并，并把这俩节点夹住的中间的关键字一起合并进来，才能满足节点内的关键字有顺序的大小特性，即中间的关键字为82，把中间的关键字放到当前缺关键字节点的关键字后边，即82放在73后边，右兄弟节点上的关键字跟在中间关键字后边，此时根节点上没有任何关键字了，可以把根节点删除。

 

知识回顾：

 

。。。。。。。。。。。。。。。。。。。。。。。。。