EXERCISE 1
Construct a B+-tree for the following set of values
(2, 3, 5, 7, 11, 17, 19, 23, 29, 31)
Assume that the tree is initially empty and values are inserted in ascending order.
1) Construct B+-trees for the cases where the number m of pointers that will fit a node is as follows:
a. Four
b. Seven
2) Shows the form of the B+-tree after each operation of the sequence:
Insert 9; Insert 10; Insert 8; Insert 6; Insert 1; Insert 4
for the case m=4.
Solution
Point 1)
……………
……. m/2 <= p <= m
k k’ parent node
<k >=k and <k’
leaf node
(m–1)/2 <= k <= m–1
File
B+-tree:
Not a root or a leaf node: m/2 <= p <= m , where p is a pointer.
Leaf node: (m–1)/2 <= k <= m–1, where k is a key.
Root: p>= 2 if it is not a leaf
0<=k<= (m–1) if it is a leaf.
a) m=4 Internal node: 2<=p<=4 Root: p>= 2 if it is not a leaf;
Leaf node: 2<=k<=3 0<=k<= 3 if it is a leaf
B+tree: Insert 2, 3, 5
2| 3 | 5
B+tree: Insert 7 (leaf split)
5 | |
N N’
2 | 3 | 5 |7 |
Split a leaf node:
Let K1, …, K m be the set of keys in the ascending order (i.e. 2, 3, 5, 7)
Node N: K1, …, K m/2 -1, K m/2 (i.e. 2, 3)
Node N’: K m/2+1, …, K m (i.e. 5, 7)
Insert K m/2 +1 into the parent node (i.e. 5)
, B+tree: Insert 11, 17, 19, 23, 29
5 | 11 | 19
2 | 3 | 5 | 7 | 11 | 17 | 19 | 23 | 29
B+tree: Insert 31 (leaf node split + non leaf node split)
11 | |
N N’
5| | 19 | 29 |
2|3| 5|7| 11 | 17 | 19 | 23| 29 | 31 |
Split an internal node N:
Let K1, …, K m be the set of keys in the ascending order (i.e. 5, 11, 19, 29)
Node N: K1, …, K m/2-1 (i.e. 5)
Node N’: K m/2+1, …, K m (i.e. 19, 29)
Insert K m/2 into the parent node of N (i.e. 11)
Note that since values are inserted in ascending order, leaves have the minimum number
of keys except the last leaf.
b) Seven.
m=7 Intermediate node : 4<=p<=7 Leaf node: 3<=k<=6
Root: p>= 2 if it is not a leaf ;
0<=k<= 6 if it is a leaf
B+tree: Insert 2, 3, 5, 7, 11, 17
2 | 3 | 5 | 7 | 11 | 17
B+tree: Insert 19 (leaf split)
11 | | | | |
2| 3 | 5| 7| | 11 | 17 | 19 | | |
B+tree: Insert 23, 29, 31
11 | | | | |
2| 3 | 5| 7| | 11 | 17 | 19 | 23 | 29 | 31
Construct a B+-tree for the following set of values
(2, 3, 5, 7, 11, 17, 19, 23, 29, 31)
Assume that the tree is initially empty and values are inserted in ascending order.
1) Construct B+-trees for the cases where the number m of pointers that will fit a node is as follows:
a. Four
b. Seven
2) Shows the form of the B+-tree after each operation of the sequence:
Insert 9; Insert 10; Insert 8; Insert 6; Insert 1; Insert 4
for the case m=4.
Solution
Point 1)
……………
……. m/2 <= p <= m
k k’ parent node
<k >=k and <k’
leaf node
(m–1)/2 <= k <= m–1
File
B+-tree:
Not a root or a leaf node: m/2 <= p <= m , where p is a pointer.
Leaf node: (m–1)/2 <= k <= m–1, where k is a key.
Root: p>= 2 if it is not a leaf
0<=k<= (m–1) if it is a leaf.
a) m=4 Internal node: 2<=p<=4 Root: p>= 2 if it is not a leaf;
Leaf node: 2<=k<=3 0<=k<= 3 if it is a leaf
B+tree: Insert 2, 3, 5
2| 3 | 5
B+tree: Insert 7 (leaf split)
5 | |
N N’
2 | 3 | 5 |7 |
Split a leaf node:
Let K1, …, K m be the set of keys in the ascending order (i.e. 2, 3, 5, 7)
Node N: K1, …, K m/2 -1, K m/2 (i.e. 2, 3)
Node N’: K m/2+1, …, K m (i.e. 5, 7)
Insert K m/2 +1 into the parent node (i.e. 5)
, B+tree: Insert 11, 17, 19, 23, 29
5 | 11 | 19
2 | 3 | 5 | 7 | 11 | 17 | 19 | 23 | 29
B+tree: Insert 31 (leaf node split + non leaf node split)
11 | |
N N’
5| | 19 | 29 |
2|3| 5|7| 11 | 17 | 19 | 23| 29 | 31 |
Split an internal node N:
Let K1, …, K m be the set of keys in the ascending order (i.e. 5, 11, 19, 29)
Node N: K1, …, K m/2-1 (i.e. 5)
Node N’: K m/2+1, …, K m (i.e. 19, 29)
Insert K m/2 into the parent node of N (i.e. 11)
Note that since values are inserted in ascending order, leaves have the minimum number
of keys except the last leaf.
b) Seven.
m=7 Intermediate node : 4<=p<=7 Leaf node: 3<=k<=6
Root: p>= 2 if it is not a leaf ;
0<=k<= 6 if it is a leaf
B+tree: Insert 2, 3, 5, 7, 11, 17
2 | 3 | 5 | 7 | 11 | 17
B+tree: Insert 19 (leaf split)
11 | | | | |
2| 3 | 5| 7| | 11 | 17 | 19 | | |
B+tree: Insert 23, 29, 31
11 | | | | |
2| 3 | 5| 7| | 11 | 17 | 19 | 23 | 29 | 31
