8706f075d5d2d503f0f6f2dd325de3b9
数据结构与算法——B+树

1 引言

B+树是在B树基础进一步优化得到的一种数据结构。B+树相比于B树具有更高的查询效率。

2 定义

B+树定义:

(1)B+树包含2种类型的结点:内部结点(也称索引结点)和叶子结点。
(2)根结点本身即可以是内部结点,也可以是叶子结点。根结点的关键字个数最少可以只有1个。
(3)B+树与B树最大的不同是内部结点不保存数据,只用于索引,所有数据(或者说记录)都保存在叶子结点中。
(4) m阶B+树表示了内部结点最多有m-1个关键字(或者说内部结点最多有m个子树),阶数m同时限制了叶子结点最多存储m-1个数据。
(5)内部结点中的key都按照从小到大的顺序排列,对于内部结点中的一个key,左树中的所有key都小于它,右子树中的key都大于等于它。叶子结点中的数据也按照key的大小排列。
(6)每个叶子结点都存有相邻叶子结点的指针,叶子结点本身依关键字的大小自小而大顺序链接。

B+树示意图:
  图2.1所示的B+树中,灰色节点代表索引节点,索引节点中只有key,而不含数据data。橙色节点代表叶子节点,叶子节点中既有key值又有数据data。叶子节点采用单链表的方式链接。
图2.1 B+树

图2.1 B+树

3 特点

(1)索引节点的key值均会出现在叶子节点中。
(2)索引节点中的key值在叶子节点中或者为最大值或者为最小值。
(3)叶子节点使用单链表的形式链接起来。

4 插入

4.1 插入流程

  B+树的插入流程与B树类似,对于m阶的B+树,插入数据情况如下:

(1) 若当前树为空树,则创建一个叶子结点,然后将记录插入其中,此时这个叶子结点也是根结点,插入操作结束。
(2)针对叶子类型结点:根据key值找到叶子结点,向这个叶子结点插入数据。插入后分两种情形:
  (2)- A:插入后,若当前结点中包含key的个数小于或者等于m-1,则插入结束。
  (2)- B:插入后,当前结点key的个数大于m-1,将这个叶子结点分裂成左右两个叶子结点,左叶子结点包含前m/2个数据,右结点包含剩下的数据,将第m/2+1个记录的key进位到父结点中(父结点一定是索引类型结点),进位到父结点的key左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点,然后执行第(3)步。
(3)针对索引类型结点,同样分为两种情形:
  (3)- A:若当前结点key的个数小于等于m-1,则插入结束。
  (3)- B:若当前节点key的个数大于m-1,将这个索引类型结点分裂成两个索引结点,左索引结点包含前(m-1)/2个key,右结点包含m-(m-1)/2个key,将第m/2个key进位到父结点中,进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点。将当前结点的指针指向父结点,然后重复第(3)步。

4.2 实例图解

  以5阶B+树为例,介绍B+树的数据插入过程。

图解过程:
1:首先,插入4,符合情形(1),将插入数据4作为根节点。

2:继续插入8,10,14,符合情形(2)- A。直接插入数据到根节点。

3:插入16,当前节点中key数目超过4,符合情形(2)- B,因此需要进行节点分裂。分裂后增加索引节点,插入索引节点符合情形(3)- A。

4:继续插入17,18,插入18后,符合情形2-b,节点16作为索引节点完成插入,符合情形(3)- A。将中间key值16作为索引节点上移至父节点中。

5:按照相同步骤继续插入6,9,19,20,21,22。

6:继续插入7,符合情形(2)- B,节点7作为索引节点插入时,符合情形(3)- B,进行索引节点分裂。

top Created with Sketch.