【MySQL技术内幕】25-B+树的操作

扫码关注公众号:Java 技术驿站

发送:vip
将链接复制到本浏览器,永久解锁本站全部文章

【公众号:Java 技术驿站】 【加作者微信交流技术,拉技术群】

B+树中,所有记录节点都按照键值的大小顺序放在同一层叶子节点,各个叶子节点指针进行连接。

图中指针是单向的,但是书上的图是双向的,而且旋转应该也是双向才能完成)

2020011020012\_1.png

B+树插入处理

LeafPage满 IndexPage满 操作
No No 直接插入到叶子节点
Yes No 1.拆分LeafPage 2.将中间的节点值加入到IndexPage中 3.中间节点左边的记录放拆分后的左页 4.其余(包括中间节点)放右页
Yes Yes 1.拆分LeafPage,步骤与上条一致(当作IndexPage还未满) 2.拆分IndexPage,将其与普通LeafPage看待

页拆分意味着层次增加,因此B+树也会进行旋转。当Leaf Page满了的时候,会去查看其左右兄弟页是否已满,若未满则会移动记录到兄弟页上,通常顺序是先左后右。

参考https://blog.csdn.net/shenchaohao12321/article/details/83243314

B+树删除操作
删除合并叶子的标准是填充因子(fill factor),50%是可以设置的最小值。

LeafPage小于填充因子 IndexPage小于填充因子 操作
No No 直接在叶子节点中删除该记录,若该记录是IndexPage中的值则将该记录的右边记录代替
Yes No 合并叶子节点和它的兄弟节点,更新IndexPage
Yes Yes 1.合并叶子节点和其兄弟节点 2.更新IndexPage 3.合并IndexPage和其兄弟节点

参考 https://blog.csdn.net/shenchaohao12321/article/details/83243314


来源:https://blog.csdn.net/shenchaohao12321/category_8075653.html

赞(0) 打赏
版权归原创作者所有,任何形式的转载请联系博主:daming_90:Java 技术驿站 » 【MySQL技术内幕】25-B+树的操作

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏