0

嘿，我对我的作业有疑问，我能够解决它我只是希望有人看看我做对了还是错了......

A b-tree with minimum branching factor of t=3

               [D][G][K][N][V]
             /  /  /    |  \   \
            /  /  /     |   \   \
           /  /  /      |    \   \
          AC EF  HI    LM  OPRST  WX

Now when i insert J in above tree this is the output i am getting.... 
                     [K]
                   /      \
                  /        \
                 /          \     
               [D][G]    [N][V]
             /  /  /     /  \   \
            /  /  /     /    \   \
           /  /  /     /      \   \
          AC EF  HIJ  LM    OPRST  WX


After Inserting Q in above tree this is the Final tree i am getting.
                      [K]
                   /      \
                  /        \
                 /          \     
               [D][G]    [N][Q][V]
             /  /  /     /  / \  \
            /  /  /     /  /   \  \
           /  /  /     /  /     \  \
          AC EF  HIJ  LM  OP   RST  WX

  Is this the Final Tree Correct?
4

2 回答 2

0

不，最终的 B 树不正确。中间的虽然是。最后一个应该是这样的

                  [K]
               /      \
              /        \
             /          \     
           [D][G]    [N][R][V]
         /  /  /     /  / \  \
        /  /  /     /  /   \  \
       /  /  /     /  /     \  \
      AC EF  HIJ  LM  OPQ   ST  WX

你错过了一些非常重要的事情。在 B 树中，插入仅在叶节点中完成，并且沿途的每个完整节点都被拆分。您在最终树中插入Q了 2 级节点。

编辑：我认为您对插入算法感到困惑。插入只发生在叶节点中。在从根到叶的向下路径中，如果遇到任何完整节点，则首先将其拆分。如果叶子节点满了，会先分裂再插入key。在您的情况下，叶节点OPRST将在遇到时被拆分，因为它有 5 个节点并且已满。因此R将向上移动并ST创建一个包含键的新叶节点。较旧的叶节点现在将只有OP键。Q然后进行比较，R搜索向左移动到最终插入的OP节点。Q

于 2013-10-19T16:33:19.383 回答
0

如果分支因子为 3，这是否意味着非根节点中的最小键数？初始树怎么可能是正确的？

初始状态将是：

└── E, I, N, S
    ├── A, C, D
    ├── F, G, H
    ├── K, L, M
    ├── O, P, R
    └── T, V, W, X
于 2013-10-19T16:22:21.803 回答