当前课程知识点：数据结构（Data Structures） > 5. Index > 5.7 Deletion Operation on B+ Tree > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
各位同学大家好
下面我们将学习
在B+树上的删除操作的实现
我们首先来看一个
简单的删除数据的例子
这里我们操作的是4阶B+树
每个叶子结点
假设最多可以存放五个记录
那么最少
当然就是三个记录
在这个例子中
我们要删除的关键字是18
首先我们要查找
关键字为18的记录
在什么地方
查找的过程
也是从树根开始
通过关键字的比较
来去确定从哪个分支
继续地查找下去
直到我们找到
某个叶子结点
如果在叶子结点中找到了
我们就直接把它对应的记录
从中删除掉
因为在这个叶子结点中
原来是有五个记录的
删除掉一个之后
还剩下四个
依然处于一个合理的范围
所以删除操作成功之后
不需要再做任何的调整
我们再来看复杂一点的例子
在这棵B+树上面
我们要删除关键字为12的记录
首先我们要找到12所在的叶子结点
然后将12进行删除
但是我们可以看到
这个叶子结点的记录数
它本来比较少
做了删除操作之后
就只剩下两个记录
因为在这棵B+树上面
每个叶子结点
最多可以存放五个记录
所以最少应该要存放三个记录
因此这个叶子结点
它是不符合B+树的要求的
这个时候
我们就可以去找临近的
兄弟结点进行帮忙
如果临近的兄弟结点的关键字比较多
我们就可以从兄弟结点那里
移动一个关键字过来
比如在这个例子中
我们可以将关键字18移动过来
这样子右边叶子结点的
关键字的数目就变成了四个
还是属于一个合理的范围的
我们再来看另外一个例子
在这里
我们要删除的是关键字33
同样的我们也要
先找到33所在的叶子
这个叶子
在删除掉33这个关键字之后
将会变成两个关键字
低于下限
所以我们需要
去找兄弟结点的帮忙
可是我们发现
兄弟结点它也比较穷
只有三个关键字
如果它把一个关键字迁移过来
那么将会导致
它的关键字的数目也会过少
我们可以选择
将这两个兄弟结点进行合并
合并成为一个结点
这个合并的过程
将会导致父亲结点的孩子数目
变成了一个
这也是不符合
孩子数目的下限要求的
对于这样的一棵4阶B+树来说
至少要有两个孩子
所以这个父亲结点
同样也需要向它的兄弟结点
发起援助的请求
由于父亲结点的兄弟
孩子数比较多
所以可以将兄弟结点的
一个孩子迁移过来
这样这两个结点
都能够满足孩子数目的要求
然后我们再调整对应的关键字
就这样就完成了这个删除操作
我们最后再来看一个
持续合并的例子
在这个例子中
我们要删除的关键字是47
首先我们也是要找到47所在的叶子
在删除了47之后
这个叶子结点的关键字
它的数目低于下限
所以可以寻求兄弟的帮忙
由于它的兄弟结点的关键字也比较少
所以两个结点进行了合并
合并导致了父亲结点
的孩子数目减少为一个
这是低于4阶B+树的结点的
孩子数目的下限的
所以在这个时候
需要再次地去寻找
兄弟结点的帮忙
但是这个兄弟结点的
孩子数目比较少
因此这两个结点
再次进行了合并
合并的结果将会导致
树根结点只剩下一个孩子
根据B+树的定义
树根如果不是叶子结点
则至少要有两个孩子
所以这个树根
它是不满足要求的
我们可以裁减掉多余的树根结点
我们看到经过这一系列的结点合并之后
最终导致树的高度降低了
B+树发生了塌缩
这个过程
和插入所导致的树的增高过程
是相反的
最后我们来分析一下
删除算法的效率
整个删除的过程中
我们首先从树根开始
从上往下
查找到删除的关键字
所处在的位置
这个过程访问结点的数目
等于树的高度
然后我们删除了叶子结点
可能会导致结点的持续合并
而合并的次数
也不会超过整个树的高度
所以我们说整个算法的复杂度
和树的高度是同一个量级的
也就是说等于⊙（log n）
好的 我们这节课就讲到这里
下节课我们再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video
