![]() |
1
4
一幅画胜过千言万语;一部动画价值百万: http://constellationmedia.com/~funsite/static/btree-insert-animation.gif 这里要注意的关键点是,当中心节点50被拉起时,它必须扔掉它的右子节点,因为它太低了。然而,65岁需要一个新的左撇子,所以50岁的人把45岁交给65岁。50现在需要一个新的右子节点,并且包含65的节点需要被子节点化,因此它使用新形成的65来代替它。 下面是B树插入规则(其中最大节点大小为4个项目,5个子节点): http://constellationmedia.com/~funsite/static/btree-insertion-rules.png
这个
|
![]() |
2
1
在第二个图中,45节点是65节点的子节点是没有意义的,因为最右边的分支用于值>50(基于根节点最右边的值)-所以45必须进入中间分支的某个位置。 |
![]() |
3
1
在拆分之前,[30,50]节点有两个键和三个子节点。当你把它分开时,你会得到一个[30,-]节点和一个[65,-]节点(然后把50向上推一层)。
您有两个父节点和四个子节点。每个父级必须有两个子级,因为它只有一个键。因此,根据排序规则,[45,-] 做[30,-]的孩子,否则(1)[30,-]就没有足够的孩子,(2)[65,-]就会有太多的孩子[ -对于一个节点来说不是太多,但是分割应该是平衡的]。
|