当前课程知识点：数据结构（Data Structures） > 5. Index > 5.6 Insertion Operation on B+ Tree > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
各位同学 大家好
下面我们将学习
在B+树上的插入操作的实现
我们首先来总结一下
B+树的主要特性
m阶B+树具有下面的性质
首先是树根结点
要么是一个叶子结点
要么至少有两个孩子
除了树根和叶子之外
每一个中间结点
至少有m/2的向上取整数
这么多个孩子
那么最多会有n个孩子
这个特性和B树是一样的
对于每个叶子结点来说
如果叶子最多可以
存放n个数据记录
那么最少应该存放的数据记录的数目
是n/2的向上取整数
所有的数据记录的信息
都是存放在叶子结点中
而中间结点
只存放关键字
这一点和B树是不一样的
在这里这幅图中
我们给出的是一个
4阶B+树的例子
假如它的每个叶子结点
最多存放5个记录
那么叶子结点
至少应该存放3个记录
除了树根之外
每个中间结点
最多会有4个孩子
那么最少应该至少有2个孩子
下面我们来看一下
在B+树上的一些
主要操作的实现
首先我们学习到的是插入操作
接下来这个例子中
我们看到的都是4阶B+树
每个叶子结点
假设最多可以存放5个记录
我们来看一个
简单的插入例子
在这棵树上面
我们要插入关键字45
这个数据记录
我们首先要在树上查找一个
合适插入的位置
因为我们前面讲过
在B+树所有的数据记录
都是记录在叶子结点上面
所以我们首先要找到一个
合适插入45的叶子结点
我们首先要将45跟树根进行比较
因为45要大于第二个关键字
所以我们再在第三棵子树下面进行查找
最终我们确认是要将45
插入到第三个叶子结点中去
这个叶子结点
原来有三个记录
在插入45之后
应该会有四个记录
记录的数目
没有超过五
所以我们可以很放心地
把45插入到这个叶子的
合适位置上面去
我们再来看复杂一点的例子
如果我们在这棵B+树上面插入26
我们同样也是从树根开始
查找一个合适插入26的
叶子结点的位置
然而这个叶子结点上的
记录的数目
已经达到了上限五个
所以无法将26插入进去
那怎么办呢
类似地我们要将这个叶子结点
进行分裂
分成等大的两个部分
左边的这个结点
存放比较小的三个记录
右边的这个新分裂出来的结点
存放比较大的另外三个记录
然而我们需要在父亲结点
和新分裂的结点之间
建立一些联边
这样一来
父亲结点的孩子数目
将会由原来的3个
变成现在的4个
还没有超出阶树的约定
属于一个合理的范围
在增加了一个孩子之后
也需要在父亲结点中
增加相应的关键字
这个关键字的大小
要大于左边这个结点的关键字
同时它要小于等于
右边这个结点的关键字
所以我们可以选择
右边这个结点中
最小的关键字
来存放在父亲结点中
这样我们就完成了
这个结点分裂的过程
下面我们再来看一个例子
这里的B+树
原来只有一个根结点
已经存放了五个记录
达到了上限
当我们继续要往里面
添加关键字50的时候
将会导致这个根结点的分裂
和前面的例子一样
将会分裂出两个节点
这样树根就由原来的一个
变成现在的两个
这个是不符合B+树的定义的
所以我们需要新建一个树根结点
并且建立树根结点
到这二个分裂结点的联边
树根中存放的关键字
要介于它的两个子树的
关键字之间就可以了
这里我们选择的是
右边的叶子结点中
最小的关键字
在整个过程中
随着不断的插入数据
B+树从原来的只有一个叶子结点
现在分裂成为高度为二的一棵树
整一棵树长高了
最后我们来看一个复杂一点的
连续分裂的例子
在这个例子中
我们要插入关键字为30的记录
首先我们通过查找
来确定插入的叶子结点的位置
因为这个叶子结点中
已经有五个记录了
达到了上限
所以在插入之后
我们需要对它进行分裂
分裂会产生两个结点
然后我们要建立父亲结点
和分裂结点之间的联边
这样会导致
父亲结点的孩子数目
增加了一个
变成了五个孩子
这就超出了B+树的阶数的要求
因为它是4阶的B+树
所以我们需要进一步的
对父亲结点进行分裂
这里父亲结点
被分裂成为二个结点
其中一个结点又有三个孩子
另外一个有两个孩子
这个时候树根就变成了两个
所以类似于前面的例子
我们需要建立新的树根节点
并且要建立根结点
和这两个分裂结点之间的联边
在这个过程中
插入最终会导致树上的结点的连续分裂
最终使整棵树长高了
我们将B+树的生长方式
和BST进行对比
我们会发现在BST中
插入数据的时候
会导致新的结点
作为老的叶子结点的孩子结点
整一棵树是向末梢方向来生长的
这种生长方式
最终导致整一棵树失去了平衡
而在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
