+ B -Trees

Same structure as B-trees. Dictionary pairs are in leaves only. Leaves form a doubly-linked list. Remaining nodes have following structure:

j a 0 k1 a1 k2 a 2 kj aj j = number of keys in node. ai is a pointer to a subtree. ki <= smallest key in subtree ai and > largest in ai-1.

Example B+-tree
9 5

16 30
5 6 9 16 17 30 40

1 3

index node leaf/data node

B+-treeSearch
9 5

16 30
5 6 9 16 17 30 40

1 3

key = 5 6 <= key <= 20

B+-treeInsert
9 5

16 30
5 6 9 16 17 30 40

Insert 10

Insert
9

16 30
5 6 9 16 17 30 40

1 3

Insert a pair with key = 2. New pair goes into a 3-node.

Insert Into A 3-node

Split into two nodes.

Insert smallest key in new node and pointer to this new node into parent.
2 1 23

Insert
9 5 2 2 3

16 30

5 6

16 17 30 40

Insert an index entry 2 plus a pointer into parent.

Insert
9

2 5

16 30

2 3

5 6

16 17 30 40

Now, insert a pair with key = 18.

Insert
9 17 2 5 16 30 17 18

2 3

5 6

16

30 40

Now, insert a pair with key = 18.

Insert an index entry17 plus a pointer into parent.

Insert
9 17

2 5

16

30

2 3

5 6

16

17 18

30 40

Now, insert a pair with key = 18.

Insert an index entry17 plus a pointer into parent.

Insert
9 17

2 5

16

30

2 3

5 6

16

17 18

30 40

Now, insert a pair with key = 7.

Delete
9

2 5

16 30

2 3

5 6

16 17 30 40

Delete pair with key = 16. Note: delete pair is always in a leaf.

Delete
9

2 5

16 30

2 3

5 6

17

30 40

Delete pair with key = 16. Note: delete pair is always in a leaf.

Delete
9

2 5

16 30

2 3

5 6

17

30 40

Delete pair with key = 1. Get >= 1 from sibling and update parent key.

Delete
9

3 5

16 30

5 6

17

30 40

Delete pair with key = 1. Get >= 1 from sibling and update parent key.

Delete
9

3 5

16 30

5 6

17

30 40

Delete pair with key = 2. Merge with sibling, delete in-between key in parent.

Delete
9

16 30

5 6

17

30 40

Delete pair with key = 3.

Get >= 1 from sibling and update parent key.

Delete
9

16 30

17

30 40

Delete pair with key = 9.

Merge with sibling, delete in-between key in parent.

Delete
9

30

17

30 40

Delete
9

16 30

17

30 40

Delete pair with key = 6.

Merge with sibling, delete in-between key in parent.

Delete
9

16 30 5

17

30 40

Index node becomes deficient.

Get >= 1 from sibling, move last one to parent, get parent key.

Delete
16

30

17

30 40

Delete 9.

Merge with sibling, delete in-between key in parent.

Delete
16

30 5

17

30 40

Index node becomes deficient. Merge with sibling and in-between key in parent.

Delete

16 30

17

30 40

Index node becomes deficient. Its the root; discard.

B*-Trees
Root has between 2 and 2 * floor((2m 2)/3) + 1 children. Remaining nodes have between ceil((2m 1)/3) and m children. All external/failure nodes are on the same level.

Insert
When insert node is overfull, check adjacent sibling. If adjacent sibling is not full, move a dictionary pair from overfull node, via parent, to nonfull adjacent sibling. If adjacent sibling is full, split overfull node, adjacent full node, and in-between pair from parent to get three nodes with floor((2m 2)/3), floor((2m 1)/3), floor(2m/3) pairs plus two additional pairs for insertion into parent.

Delete
When combining, must combine 3 adjacent nodes and 2 in-between pairs from parent.
Total # pairs involved = 2 * floor((2m-2)/3) + [floor((2m-2)/3) 1] + 2. Equals 3 * floor((2m-2)/3) + 1.

Combining yields 2 nodes and a pair that is to be inserted into the parent.
m mod 3 = 1 => nodes have m 1 pairs each. m mod 3 = 0 => one node has m 1 pairs and the other has m 2. m mod 3 = 2 => nodes have m 2 pairs each.