数据结构之B+树插入详解
一、简介B+树是B树的一种变形形式,一颗B+树包含根节点、内部节点和叶子节点,B+树上的叶子节点存储关键字以及相应记录的地址,叶子节点以上各层作为索引使用。一棵m阶的B+树定义如下:1)根结点最少包含1个关键字个数,最多包含m-1个关键字;2)B+树内部结点不保存数据,只用于索引,所有数据(或者说记录)都保存在叶子结点中;3)内部结点最少有ceil(m / 2) - 1个关键字,最多有m-1个关键
目录
一、简介
B+树是B树的一种变形形式,一颗B+树包含根节点、内部节点和叶子节点,B+树上的叶子节点存储关键字以及相应记录的地址,叶子节点以上各层作为索引使用。
一棵m阶的B+树定义如下:
- 1)根结点最少包含1个关键字个数,最多包含m-1个关键字;
- 2)B+树内部结点不保存数据,只用于索引,所有数据(或者说记录)都保存在叶子结点中;
- 3)内部结点最少有ceil(m / 2) - 1个关键字,最多有m-1个关键字(或者说内部结点最多有m个子树);
- 4)内部结点中的key都按照从小到大的顺序排列,对于内部结点中的一个key,左树中的所有key都小于它,右子树中的key都大于等于它,叶子结点中的记录也按照key的大小排列;
- 5)每个叶子结点都存有相邻叶子结点的指针,叶子结点本身依关键字的大小自小而大顺序连接;
如下图是一颗标准的5阶B+树:
二、B+树的查找
B+树的查找与B树不同,当索引部分某个结点的关键字与所查的关键字相等时,并不停止查找,应继续沿着这个关键字左边的指针向下,一直查到该关键字所在的叶子结点为止。
三、B+树的插入
B+树插入的一些规则:
下面我们通过一个简单的示例说明B+树的详细构建过程:
我们以构建一个5阶B+树为例,根据B+树特性,最少包含2个关键字,最多可以包含4个关键字,当不满足上面条件的时候,可能就需要进行分裂操作了。
【a】插入5
因为当前是一颗空树,所以直接插入即可,结束本次插入操作。
【b】插入8,10,15
因为关键字数量都满足B+树特性,所以插入后不需要进行分裂操作。
【c】插入16
插入16后,发现已经超过最大关键字数量4了,这时候我们根据上面脑图中总结的规则,将【5 / 2】 + 1 = 3位置的节点10提取到父节点当做索引节点,然后将【5 / 2】= 2前面两条数据作为左子树,剩下的记录都作为右子树。分裂后如下图所示:
【d】插入17
因为关键字数量都满足B+树特性,所以插入后不需要进行分裂操作。
【e】插入18
插入18后,超过最大关键字数量,需要进行分裂。跟上面分裂一样,将16节点提取到父节点中当做索引节点,16左边的当做左子树,右边的当做右子树。分裂后如下图:
【f】插入6和9
因为关键字数量都满足B+树特性,所以插入后不需要进行分裂操作。
【g】插入19
因为关键字数量都满足B+树特性,所以插入后不需要进行分裂操作。
【h】插入20
跟上面分裂一样,将18节点提取到父节点中当做索引节点,18左边的当做左子树,右边的当做右子树。
插入后如下图所示:
【i】插入21
因为关键字数量都满足B+树特性,所以插入后不需要进行分裂操作。
【j】插入22
跟上面分裂一样,将20节点提取到父节点中当做索引节点,20左边的当做左子树,右边的当做右子树。插入后如下图所示:
【k】插入7
跟上面分裂一样,将7节点提取到父节点中当做索引节点,7左边的当做左子树,右边的当做右子树。插入后如下图所示:
我们发现,索引节点中的关键字个数超过4,需要继续分裂。左结点2个关键字,右结点2个关键字,关键字16进入到父结点中,将当前结点指向父结点,结果如下图所示:
至此,上面各个节点都满足B+树的特性,一颗5阶的B+树就构建完成,小伙伴们可以照着脑图中总结的判断流程进行判断,最好可以动手自己画一下加深印象。
四、总结
B+树插入总体流程图如下:
以上就是关于B+树插入新节点的详细构建过程总结,小伙伴们在学习的时候,不妨试试画一下,可以加深对B+树结构的理解,希望本文能对大家学习B+树有所帮助。由于笔者水平有限,文中可能存在不对之处,还望大家之处,一起学习,一起进步!下面推荐一个动态构建B+树结构的网站,可以观察B树具体是怎么查找、插入和删除节点的:
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)