2021-06-05 11:28  阅读(2609)
文章分类:MySQL 技术内幕 文章标签:MySQLMySQL 技术内幕MySQL 高级
©  原文作者:一直不懂 原文地址:https://blog.csdn.net/shenchaohao12321/category_8075653.html

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

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

202106051128004351.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

版权归原创作者所有,任何形式转载请联系作者; Java 技术驿站 >> 【MySQL技术内幕】25-B+树的操作
上一篇
【MySQL技术内幕】24-InnoDB存储引擎索引概述
下一篇
【MySQL技术内幕】26-聚集索引与辅助索引