开发者学堂课程【高校精品课-西安交通大学-数据库理论与技术：第八课】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/12/detail/15864
第八课（一）
内容介绍：
一、B+树插入数值过程
二、B+数之键值删除与结点合并过程
三、散列索引
一、B+树插入数值过程
这里有31、37、41，40，操作到这个阶段，节点已经满了。相当于房间里有三个床位，现在要来一个新人，住不下。就分裂，把四个节点拆成俩个节点，一边俩个。
分裂完之后，这一层的关键字只对这一层有反应，下一层需要重新增加。下一层有分裂之后，又需要进行重复操作。
接下来需要做几个步骤：
(1)寻找保存键值记录的叶子结点
(2)应插入结点已满，则申请新结点
(3)同时调整应插入但未插入结点中的键值记录，使其均衡存放于两个叶结点中（分裂）
(5)寻找指向新叶子结点的非叶结点
(6)应插入结点已满，则申请新结点
(7)同时调整应插入但未插入结点的键值记录，使其均衡存放于两个非叶结点中(分裂)
分裂过程当中，把节点拆分成新的分裂数值，这个指针要进行操作，指向新的叶子结点。
变化如下图所示：
新的40这个值还需要重新指向，新的40还要把它插入进去，插入进去之后，上面又要分裂，上面分成23,31,43，分列上去之后，40要放到上面去，导致上面一个关键值变成俩个关键值。调整完指向之后，指针还要统一调整，最后插入完成之后。
上述为操作过程，刚才讲的这些就是算法的具体过程，就是前面算法。有俩个能力，一个是看着算法，能根据算法进行操作，知道操作怎么做。还有一个就是想做一件事，先要进行画框架，根据框架进行编辑，把这件事编辑成算法，过程中不是纯数学的一个过程，一定是对数据进行处理之后，用程序的思想表达出来，涉及到算法设计。
插入节点的过程首先是沿着节点，找到插入位置，位置里面不满的话，依次进行插入。
满了之后，分类成俩个，就会给上面增加一个，增加以后又会分裂，再进行插入，以上是节点的分裂过程。有俩个关键点，一个是分裂时，当节点满了之后，第二个关键点是有叶结点向根结点逐层处理，叶结点分裂了，导致上节点分裂，上节点满了之后，又要进行分裂。分裂之后，就一次向下一层，直到根结点，根结点满了之后，根结点再进行分裂，根结点分裂就等于发生一个新的一层。
根结点满了之后，把根结点平均分成俩半，新的根结点只有一个分节点。分节点只能有一个关键值，这就是当根结点满了之后导致新的一层出现。
分裂的时候，不均匀的时候，会由多的向少的进入，算法当中细角的地方可改变，这就是一个很古老的算法，并没有加入新元素。
如果上面的方法要用算法来写的话，需要写很长一段，如下：
procedure insert(value K,poinmerFP)
if(树为空)创建一个空叶结点 L，同时它也是根结点
else 找到应该包含值K的叶结点L
f(L所含搜索码少于s-1个)
then insert_in_leaf (L. K. P)
else begin/•L已经含有n-1个搜索码了，分裂L=/
创建结点 L'
把LP、…、L K...复制到可以存储n个(指针，搜索码值)对的内存块T中insert_in_leaf(T.K, P)
令L.P.=LP.；令LP.=L
从中删除LP.…，LP..LK...LP.
把T.P.….T.K..从T复制到L中，L以LP作为开始
把T.K/ery 、…、T.K,从T复制到L'中，L'以L'.P, 作为开始
令 K"表示 L'中最小搜索码值
insert_in_parent(L.K'.L')
end
procedure inser_in_leaf (node L. valne K, pointer P)
if(K比LK.小)
then 把 P、K插入 L 中，紧接在 L P,前面
else begin
令 K,表示 L 中小于等于K的最大搜索码值
end”眼任 LK .前面
procedure insert_inparent (node N, rodue K', pointer N")
if(N是树的根结点)
then 在L中插入(V.P)
else begin
创建结点 R 包含 N、K"、N"/· N 和 N”都是指针·/
令 R 成为树的根结点
return
end
令 P=N 的父结点
if(P 包含的指针少于n个)
then 将(K',N")插到 N 后面
else begin/+分裂 P+/
将P复制到可以存放 P 以及(K".N")的内存块了中创建结点(K'.N')插入 T 中，紧跟在N后面删除所有 P中所有项；创建结点 P
把 T.P、….T.K.、y 复制到 P 中
令 K”= T.Kisa
把T.Psa,…，T.P..复制到 P"中
inaert_in_parent (P.A",P')
这个算法，并不是没有用，里面也涉及到一些东西。在做 hrd 索引问题的时候，关于一个查找的问题，有文章表示那个问题可以用比加数来解决这个 hrd 领域的问题，这并不是说这个算法没有用。可能这个算法在别的领域也可以解决问题。
