我想了解如何创建一个B +树,其顺序(分支因子)为3,节点为3的最大条目数.我搜索了很多applet,但大多数都没有正常工作,而且这很好似乎不遵循我在维基百科上找到的这些步骤.
按照这些步骤
如果存储桶未满(插入后最多b-1个条目),请添加记录.
否则,拆分桶.
分配新叶子并将桶的一半元素移动到新桶.
将新叶的最小键和地址插入父级.
我相信新值的插入应该在第4步之前发生.是否有更好的描述版本的算法?
随着20,15,5,1,3,9,2,12
作为输入,我得到了下面的树:
|1|5| | |2|5| | |9| | | |1|2| | |3|5| | |9| | | |15|20| |
根据这些步骤是否正确?任何人都可以指出一个小程序来验证这个例子吗?
你的树不正确.节点(而不是叶子)中的每个值都应该是分支的断点.为了说明这一点,让我们考虑以下节点:
---------------------------------------- | 7 | 23 | ---------------------------------------- | pointer to | pointer to | pointer to | | branch with| branch with| branch with| | values | values | values | | < 7 | 7 <= x < 23| >= 23 | ----------------------------------------
该节点有2个值和3个分支.值7和23表示第二和第三分支中的最小值.第一个分支的最小值未表示在此级别.(除非它是整棵树中的最小值,否则它将处于更高的级别.)
与b = 4条,用于插入值的规则可以概括:
找到值所属的存储桶(第一个值小于,并且下一个存储桶的第一个值大于我们要插入的值)
如果插入后桶中的项目数为4,则必须拆分桶
当分割存储桶时,原始存储桶中剩余2个值,2个值移动到新存储桶
将新存储桶的第一个值(值较大的存储桶)插入父存储桶/节点
如果父节点变满(4个值),它将以相同的方式分割,但插入其父节点的值将从存储桶中删除
让我们考虑一个数字为1..9的树:
3,5,7 |----------------| 1,2 3,4 5,6 7,8,9
如果我们现在在树中插入数字10,最右边的叶子变得太满(7,8,9,10),因此它必须被分成两个叶子(1,8)和(9,10).根据规则,编号9(上部拆分桶的最低值)将发送给父级:
3,5,7,9 |---------------------| 1,2 3,4 5,6 7,8 9,10
这使父级完整,并且必须拆分:
3,5 7,9 |-------| |---| 1,2 3,4 5,6 7,8 9,10
拆分父节点时,新节点的第一个值将发送到其父节点.在此树中,新节点为(7,9),因此要删除并发送到父节点的值为7.由于没有这样的父节点,因此创建了新的根节点:
7 |---------| 3,5 9 |-------| |---| 1,2 3,4 5,6 7,8 9,10
让我们建立一个数字为20,15,5,1,3,9,2,12和b = 4 的树
前三个值适合一个叶子(同时是根节点):
5,15,20
插入数字1后,存储桶将拆分,并将新存储桶的第一个值发送给父(新根):
15 |-----| 1,5 15,20
应该注意的是,从叶节点中没有任何东西被删除.仅在拆分的父节点中进行删除.
值3可以毫无问题地插入其桶中(桶将变为1,3,5).但是,尝试插入数字9会使存储桶过满(1,3,5,9)并且会分裂.新存储桶(5)的第一个值将插入父级.
5,15 |----------| 1,3 5,9 15,20
值2和12适合它们的桶而不分裂,因此树是:
5,15 |--------------| 1,2,3 5,9,12 15,20
要查看中间节点拆分时会发生什么,让我们考虑以下树:
26 |-----------------------------| 8,14,20 30,34 |--------------------------| |-----------| 2,4,6 8,10,12 14,16,18 20,22,24 26,28 30,32 34,36
现在我们将在树中添加值13.这将触发将桶(8,10,12,13)拆分为两个:
26 |-----------------------------------| 8,12,14,20 30,34 |-------------------------------| |-------------| 2,4,6 8,10 12,13 14,16,18 20,22,24 26,28 30,32 34,36
中间左侧节点(8,12,14,20)有太多子节点,因此必须拆分:
26 |---------------------------------------| 8,12 14,20 30,34 |-------------| |---------| |-------------| 2,4,6 8,10 12,13 14,16,18 20,22,24 26,28 30,32 34,36
当我们拆分父节点时,我们必须应用添加的规则,即新存储桶的第一项必须插入父节点并从节点中删除,即14从(14,20)中取出:
14,26 |------------------------------------| 8,12 20 30,34 |-------------| |---------| |-------------| 2,4,6 8,10 12,13 14,16,18 20,22,24 26,28 30,32 34,36
该树还用于说明规则:每个父节点携带除第一个子树之外的每个子树的最低值.
应该得到问题中的例子(如果我没有犯过太多错误):
5 |----------| 3 15 |---| |-------| 1,2 3 5,9,12 15,20