java - How to create a B+ Tree data-structure -

java - How to create a B+ Tree data-structure -

i understand how create b+ tree order(branching factor) of 3 , maximum number of entries in node of 3. searched lot applets, of them don't work properly, , 1 that's great seems not follow these steps found on wikipedia.

following these steps

if bucket not total (at b - 1 entries after insertion), add together record. otherwise, split bucket. allocate new leaf , move half bucket's elements new bucket. insert new leaf's smallest key , address parent.

i believe insertion of new value should happen before step 4. there improve described version of algorithm?

with 20,15,5,1,3,9,2,12 input, obtain next tree:

|1|5| | |2|5| | |9| | | |1|2| | |3|5| | |9| | | |15|20| |

is right according steps? point out applet verify example?

your tree not correct. each value in node (not leaf) should break-point branches. illustrate allow consider next node:

---------------------------------------- | 7 | 23 | ---------------------------------------- | pointer | pointer | pointer | | branch with| branch with| branch with| | values | values | values | | < 7 | 7 <= x < 23| >= 23 | ----------------------------------------

this node has 2 values , 3 branches. values 7 , 23 represent smallest values in sec , 3rd branch. smallest value of first branch not represented @ level. (unless smallest value in whole tree, on higher level.)

with b=4 rules inserting value can summarized:

find bucket value belongs (first value smaller , first value of next bucket larger value want insert) if number of items in bucket after insertion 4, bucket has split when bucket split, 2 values left in original bucket, 2 values moved new bucket the first value of new bucket (the 1 larger values) inserted parent bucket/node if parent node becomes total (4 values), splits same way, value inserted parent removed bucket

let consider tree numbers 1..9:

3,5,7 |----------------| 1,2 3,4 5,6 7,8,9

if insert number 10 tree, rightmost leaf becomes total (7,8,9,10) has split 2 leaves (1,8) , (9,10). per rule, number 9 (lowest value of upper split bucket) sent parent:

3,5,7,9 |---------------------| 1,2 3,4 5,6 7,8 9,10

this makes parent full, , has split:

3,5 7,9 |-------| |---| 1,2 3,4 5,6 7,8 9,10

when parent node split, first value of new node sent parent. in tree new node (7,9) , value removed , sent parent 7. there no such parent, new root node created:

7 |---------| 3,5 9 |-------| |---| 1,2 3,4 5,6 7,8 9,10

let build tree numbers 20,15,5,1,3,9,2,12 , b = 4

first 3 values fit in 1 leaf (which @ same time root node):

5,15,20

when number 1 inserted, bucket splits , first value of new bucket sent parent (new root):

15 |-----| 1,5 15,20

it should noted nil ever removed leaf nodes. removal occurs in parent nodes split.

the value 3 can inserted bucket no problems (the bucket become 1,3,5). however, trying insert number 9 makes bucket overfull (1,3,5,9) , split. first value of new bucket (5) inserted parent.

5,15 |----------| 1,3 5,9 15,20

values 2 , 12 fit in buckets without splitting tree is:

5,15 |--------------| 1,2,3 5,9,12 15,20

to see happens when middle node splits, allow consider next tree:

26 |-----------------------------| 8,14,20 30,34 |--------------------------| |-----------| 2,4,6 8,10,12 14,16,18 20,22,24 26,28 30,32 34,36

now add together value 13 tree. trigger splitting bucket (8,10,12,13) two:

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

there many children middle left node (8,12,14,20), has split:

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

as split parent node, have apply added rule first item of new bucket has inserted parent , removed node, i.e. 14 taken away (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

the tree serves illustrate rule: each parent node carries lowest value of each subtree except first subtree.

the illustration in question should result (if have not made many mistakes):

5 |----------| 3 15 |---| |-------| 1,2 3 5,9,12 15,20

java algorithm data-structures tree applet