代码之家  ›  专栏  ›  技术社区  ›  dicroce

btree插入的一个特殊问题

  •  5
  • dicroce  · 技术社区  · 15 年前

    我一直在玩非常酷的btree applet slady.net . 我很难理解一种特殊的行为。看看这个起始状态:

    alt text http://www.freeimagehosting.net/uploads/db2931c7da.jpg

    这个特定的状态是通过插入以下序列来实现的:10、15、30、16、70、1、9、27、45、50、55。

    我的问题是当我在序列中插入下一个值65时,[45,]节点会发生什么。

    alt text http://www.freeimagehosting.net/uploads/3b70c1d302.jpg

    [55,70]节点将被65拆分,作为中间值,65将返回,然后拆分[30,50]节点。我的问题是,[45,]节点为什么会变成[30,]节点的子节点?它的父节点最初有3个子节点,最左侧和最右侧成为新的分离节点。45在这两个值之间,看起来它也可能在[65,]节点下结束。。。为什么?

    3 回复  |  直到 5 年前
        1
  •  4
  •   Joey Adams    15 年前

    一幅画胜过千言万语;一部动画价值百万:

    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

    这个 xr x 是你拿出来的中心物品,还有新的 xr公司 是你的孩子吗

        2
  •  1
  •   Will A    15 年前

    在第二个图中,45节点是65节点的子节点是没有意义的,因为最右边的分支用于值>50(基于根节点最右边的值)-所以45必须进入中间分支的某个位置。

        3
  •  1
  •   Steve314    15 年前

    在拆分之前,[30,50]节点有两个键和三个子节点。当你把它分开时,你会得到一个[30,-]节点和一个[65,-]节点(然后把50向上推一层)。

    您有两个父节点和四个子节点。每个父级必须有两个子级,因为它只有一个键。因此,根据排序规则,[45,-] 做[30,-]的孩子,否则(1)[30,-]就没有足够的孩子,(2)[65,-]就会有太多的孩子[ -对于一个节点来说不是太多,但是分割应该是平衡的]。