1-3 B+树索引(2)在线视频

首先我们看一下列一，具有这样一棵状态的B+树中

我们插入一个键值以C为开头的这样一个键值

那么我们看到，要插入这样一个键值

我们必须要从根节点向叶子结点遍历，找到它所要插入的位置

那么我们一看，它应该插在第一个叶子节点之上

但是呢，第一个叶子节点目前现在已经满了

那么满了之后也就没有地方去插入，那怎么办呢

我们就需要对第一个叶节点进行分裂

那么进行分裂呢，我们需要把新插入的键值和

第一个叶节点所有的键值进行排序

然后呢，按照这个充满度的要求对它进行分裂

比如说我们就可以把它分裂成第一个

就是把这个Downtown这个键值拿出来形成第二个叶子节点

那么这样的话呢，当我的这个叶节点分裂成两个节点的时候

我们指向父节点的指针却不够，所以这个时候我们还需要向上追溯

对父节点进行修改，那么怎么修改呢

当然是我们要看父节点的情况，比如说现在父节点还没有满

那就说明我们还可以插入一个新的键值

然后引出一个新的指针来，那么插入谁呢

我们就要插入一个Downtown，是吧

我们把Downtown插入进去，那么这样的话呢

就是我父节点只要插入一个新的键值

那我就可以把整棵树保持它的标准定义

那么这个树的结构呢，我们就定义好了

这就是插入一个键值的这样的一种情况

下面我们来说一个稍微复杂一点的情况

那么我们用数字来表示键值，比如说

在目前这样一个状态的这样的一棵B+树的情况

我们插入一个键值40，那么这个40我们从根节点遍历到叶子节点

它需要插入到叶子节点的从前向后数第五个

但是第五个叶节点已经满了，所以这个时候

我们需要对这个叶节点也一样进行分裂

分裂把它分解成两个节点，分裂成两个节点之后

我们同样从父节点引下来的指针呢，已经不够使用了

那么怎么办呢，我们需要向上追溯修改它的父节点

但是此时它的父节点也已经满了，那么怎么办

我们的父节点一样需要分裂，那么父节点需要进行分裂的话

也就是把原来的23，37和43这样的一个节点要分解成两个兄弟节点

那么它的父节点分裂成两个之后，我们从根节点引下来的指针

也产生了这样一种情况，也就是指针的数量不够用

那怎么办呢，那就说明我们还要看根节点怎么样进行修改

那么现在我们发现根节点目前没有满，所以不需要分裂

我们需要向根节点上插入一个新的值

那么插入哪一个值呢，显然它应该插入是指针引出的子树的最小值

也就是40，所以这个时候我们在根结点上插入40这个一个键值

我们这个树就结束了维护过程

那么这就是一个我们通过两个例子来说明

B+树插入值的这样的一个维护过程

实际上一棵B+树的建立过程，就是键值不断插入的这样一个过程

下面我们来说一下B+树在键值删除的时候，它的节点合并过程

比如说我们现在仍然是前面那样一棵用数字表达的这样一个B+树

现在我需要修改一下她的节点

比如说我把这个某一个键值给它删除掉

下面我们以例子来说明一下删除键的时候B+树节点的合并过程

我们以这样一棵B+树为例，我们首先来看一下从节点当中删除

键值为7的这样一个节点，那么将键值7删除之后

我们发现，因为键值7除了是在叶子节点出现

它也在他的上一级父节点出现，那么删除了7之后

它的父结点变成了空的，那么这个时候我们该如何来维护这棵B+树呢

我们需要把这个父节点给删除吗，显然是不行

因为它下面还有几个叶子结点，所以这个时候我们需要

从这个叶子节点上，从它的兄弟节点里面去借一棵键

借一个键，借过来，满足每个叶节点的半满情况

同时我们要把这个叶节点里面第二个节点的最小值

作为它父节点的一个键值，也就是把5放上去

那么这样的话呢，我的这个删除键值7之后

我的B+树就变成这样的一个状态

这个时候如果我再删除键值11的话

那么我们的叶节点就会产生一种情况

也就是说，它达不到半满的状态

那么此时我们这个节点就要向兄弟节点去求助

如果它的兄弟节点能够借给它一个键

它仍然能达到半满状态这样比较好

但是目前它的兄弟节点也达不到半满的状态了，不能借给它键

所以这个时候我们就要把它和它的兄弟节点进行合并

把5,2和3再合并成一个兄弟节点

那么这个时候,我们将叶子节点合并之后

我们发现它的父节点键值还是5，但是这个时候已经不满足B+树的定义

这个ki一定是比pi指向的所有的键码都要大

所以这个时候我们需要对整棵树进行调整

那么调整怎么去调整呢，我们需要

把这棵树的另外一个子树的最小值调上来

所以我们需要把5变成13，另外一棵树的最小值是13

所以我们把它放在这个里面，然后整棵树进行一下调整

这样的话，也就是说我把5删除之后，B+树就变成这样的一种状态

那么这就是整个B+树在键值删除时候的一个节点合并过程

从上面的例子可以看出呢，B+树的维护代价还是比较高的

这时，可能有同学就问了

既然是这样，为什么B+树还被广泛的应用呢

许多的商用数据库管理系统为什么还要使用它

那么这就是B+树的魅力所在，在实际应用中呢

我们可以让节点足够大，比如说

我们可以让一个节点占一个磁盘块，这个时候，n就是足够大的

也就说这个B+树节点键值的数量就会足够大

比如说，我可以假设一个磁盘块大小为4k

那么键值对的大小为20个字节

那么这个时候这个节点的大小n就可以约等于200

如果每一个节点处于半满状态

这个时候一棵三层的B+树它包含的键值总数约为100万个

也就说我们可以为一个100万条记录建立索引了

如果要是稀疏索引的话，索引的记录会更多

那么这对一个普通的数据库来说呢，已经足够了

但是从查询代价上来讲，那么三层的B+树它的查询代价

只是树的高度3加上一次读取记录的代价

所以它的查询代价并不高

而且如果n足够大的话，我们在插入和合并的这种操作实际上并不多

因为什么，很多情况下，n足够大

我要是能够向这一个磁盘块能插入很多条记录

我们的树结构都不需要进行变化

所以这就是人们为什么喜欢使用B+树的原因

这样的话呢， B+树就介绍这么多

有兴趣的同学可以看SQL Server的一些相关资料

ORACLE的一些相关资料也可以

那么在他们的系统当中，都使用B+树作为索引