开发者学堂课程【高校精品课-西安交通大学-数据库理论与技术：第八课】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/12/detail/15864
第八课（二）
内容介绍：
一、B+树插入数值过程
二、B+数之键值删除与结点合并过程
三、散列索引
二、B+数之键值删除与结点合并过程
接下来讲解删除结点，删除结点的过程就是与插入结点的过程相反。如果进行删除键值为7的记录，第一步是要找到他，大于等于7，定位到下图位置，将相关关键值删除删除之后，抹掉之后调整结构，里面是镂空的，上面的也不满足，从左侧或右侧要进行调整，比如当前房间有三个床位，现在走了一个床位还剩一个人，规定住俩人，就需要进行调整，把三个人的挪一个过来，调整后关键值7调整为5,7删除。以上就是删除的过程。
具体画面如下图:
删除的过程中，会发现如果要删除11，删除掉之后，会发现又要进行调整，那么后面的结构也会有问题，无法进行合适调整。那么这时就直接删除一个房间，房间多了，直接删除掉。删除掉后关键值调为13，总之调整完之后节点的值一定要对应相等，一定需要满足这个条件。调整一个数值，其他的数值也要跟着进行调整。删除之后，可能很多房间连锁反应，都要进行调整。
如下：
以上是节点合并的过程，合并的就基本原则就是当一个节点的指针数目少于规定数目时，要进行合并，第二是由叶结点向根结点逐层处理，叶结点合并以后，上层可能要合并，一层层向根结点处理，跟插入过程正好相反。也能自动保持与主文件大小相适宜的树的层次，每个索引块指针利用率在50%-100%之间。你的主文件记录关键值多了就自动增加层数，少了就自动收缩。是一个相对动态可调整的数据结构。下图是用算法表示出来：
precedure delete (value K, pointer P)
抄则位含( K，P)的叶结点 L
delete_entry( L.K. P)
procedure delete_entry(node N. value K, pointer P)
从 N 中删除(K，P)
if(N 是根结点 and N 只剩下一个子结点)
then 使 N 的子结点成为该树的新的根结点并删除 N
else if（N 中值/指针太少）then begin
令 N'为pareni(N)的前一子女或后一子女
令 K"为 parent(N)中指针 N 和 N'之间的值
if(N和 N中的项能放在一个结点中)
then begin/·合并结点·/
if(N 是 N 的前一个结点) then swap_variables( N. N”)
if(N 不是叶结点)
then 将 K"以及 N 中所有指针和值附加到 N'中
else将 N 中所有(K.，P.)对附加到N中；令N'.P.=N.P.delete_entry(parenr(N).K'. N)；删除结点 N
end
else begin/·重新分布：从N'借一个索引项 */
if(N’是 N 的前一个结点) then begin
if(N 是非叶结点) then begin
令 m 满足：N.P_是 N'的最后一个指针
从 N 中去除(N”.K_， N”.P_)
插入(N'.P_.K')并通过将其他指针和值右移使之成为
N 中的第一个指针和值
用 N'.K_-，替换parent(N)中的K°
end
else begin
令 m 满足：(N.P_、N.K_)是 N"中的最后一个指针/值对从N”中去除(N'.P_.N”.K_)
插入( N'.P_.N.K_)并通过将其他指针和值右移使之成为
N中的第一个指针和值
用N'.K-替换 parenz(N)中的
else …与 then 的情况对称…
想要把这个算法读懂，会比较困难，必须要搞清楚这个方法的原理，根据原理去理解这个代码。从最早的结点开始，由一个结点开始，往里面放，当里面放满之后，假设里面只能放100个，那当放101个的时候，就需要进行分裂，分裂成俩个节点，左边50，右边50。中间由一个指针值放入，指向对应的方向。再插入之后，会分裂成俩个。上面就变成俩个关键值，这边插入完之后，当已经插入完100个之后，再进行分裂，上面放不下，又进行分裂，变3层。
关键字值提取的时候，你可以先建一个线性代表，放一个线性代码。缺一个放一个，依次往下层放倒回来做，这叫批量性建。一种方法是一个个往里面插入。而批量性就是插入一个节点之后，批量进行操作。
还有一种是数据文件，在上面建一个比参数，就可以批量建，依次扫描关键值，效率更高，这就是批量性操作，有俩种算法，这个是 B+数键值方法。
下面是一个例子：
这是一个初始的B+树，有4个关键值，5个分叉。所以要过半至少要2个，叶子结点最开始只有2个，一左一右，这是叶子结点。叶子结点是所有关键字值，不同的数值对应不同的地方，对号入座。如下图：
图中也进行了适当的省略，这是主文件记录，如果是非文件记录的话，指向相应记录的指针桶。
那么要插入一个19的数值，首先要进行定位，定位为比20小，插入对应位置，因为存在空位。也就是第三排第一个房间可以住四个人，现在住了三个人，现在可以将19放入。也不分裂。再插入25，进行定位，比20大，比60小，比80小。找到图中对应位置，需要注意的是插入25之后，由四个变成五个了，五个放不下，满了之后溢出，分裂成俩个节点，进行放置。
这个时候造成上面要增加一个。分裂之后，增加一个新的结点，25需要进行新增，副结点满了之后继续分裂。删除30的记录，首先定位30所在位置进行删除，原来俩个进行合并，底下的都过半无需合并，再删除25，有地方过少，过少之后要进行合并，20和40合并，合并原则是把前面过满的给搬过来，19搬过来之后，指针要调整。40删除之后，有结构镂空，进行合并，和前面进行合并，那么后面相应的结构会进行连锁处理。
以上是了解具体操作过程，下图是展示过程：
细节不过多赘述，可以去看总结部分。以上是 B+数的内容。
前面涉及到一个 B 数，B 数和B+数结构上类似，差别是 B 数所有关键字值，B+数是只有到叶子结点才有记录的指针，存储的数字节点。而 B 数在所有的节点都包含有到相应记录值的指针，B数在所有关键字值上只出现一次，无重复。B+数有重复出现，只有叶子结点出现一次，中间会重复出现。B 数结点结构不一样，关键字值旁边包含有指向关键字值的指针，后面又有一个比他大的指针。
所以指针数目要多一倍，在分裂结点的前后各有一个指针。所以 B数查找的时候，不一定要到叶子结点，可能在中间就找到了。B 数分布在树上，里面指针多，不能有更多分叉，而 B+数可以有更多分叉，所以会发现B+数用的多一些，同样的大小的数目，B+数包含的更多。因为包含指针直接在叶子结点和分裂结点都可以包含数据，以上是俩者区别。下面是 B 数构造过程的一个例子，用的是B树的生长过程，下面来进行演示：
B 树和 B+树结构上类似，生长过程是关键字序列，首先会插入结点 a，插入结点 a，f，b，k，这时关键值字数不能超过四个，进行左右分裂f在中间，不会重复，查找的时候就直接找到，不需要再到下面去找，因为不重复。
如果是找 e，会直接显示找不到，s 也同理。然后再插入 d，插入 h，插入 m，再插入 j，插入过程都会进行排序。插入之后会发现满了五个的时候，就进行分裂，上面增加一个关键字，先跟顺序遍历一遍，用算法遍历完之后，得到所有关键值。在内节点、外节点寻找，只要找到了就没有问题。插入x之后，又会进行分裂，因为这时有5个，最多只能有4个，分裂之后上面又要增加一个。把c分裂上去，再插入p的时候，会超出5个关键值，又要进行分裂到上面，会发现上面也满了，那么上面又要进行分裂，
这时就变成了三层：
这个实际上在数据库系统当中，大部分的时间就在做这个事，做数的分裂，这个算法的贡献是非常大的，现在大量数据就是用这个 B+树做起来的，索引引擎就是干这个事情。这个是它的生长过程，那么收缩过程就是与之相反，放在了课程网站上。上述过程是 B 树。那么 B+树的话，也可以进行操作。
不一样的地方在于，分裂的时候，如下图中的f会再重复一次，而B数不会重复，也可以用B+数再重新画一次。
