SEEM3550
Fundamentals of Information
Systems
Tutorial 3:
(1) Assignment 2 Q1&Q2 about B+ tree
(2) Insertion and Deletion of B+ tree
(3) Assignment 2 Q3 about hash index
(4) dynamic hash index and static hash index
Assignment 2
Assignment 2
B+-Tree Index Files
n All paths from root node to leaf node are of the same length
n A leaf node has between é(n–1)/2ù and n–1 values
n A non-leaf node (root or an internal node) has between én/2ù and n
children (pointers).
n Special cases:
q If the root is not a leaf node, it has at least 2 children.
q If the root is a leaf node (that is, there are no other nodes in the tree), it can have
between 0 and (n–1) values.
Brandt CrickCalifieri Einstein El Said Gold Katz Kim Mozart Singh Srinivasan Wu
El Said Mozart n = 6:
leaf node: [3, 5]
non-leaf node: [3, 6]
Recap: B+ Tree Node Split (n =3)
K1 K2 K3 K1 K2 K3
K3
Newnode
For leaf node (ch11 Page30) Insert toparent
temporarymemory
Split leaf node
• Splitting a leaf node:
• take the n (search-key value, pointer) pairs (including the one being
inserted) in sorted order. Place the first én/2ù entries, i.e., P1, K1, …,
P én/2ù, K én/2ù in the original node, and the rest entries, i.e., P én/2ù +1, K
én/2ù +1, …, Pn, Kn in a new node.
• let the new node be p, and let k be the least key value in p. Insert
(k,p) in the parent of the node being split.
• If the parent is full, split it and propagate the split further up.
P1 P2 P3
Recap: B+ Tree Node Split (n =3)
Split non-leaf node
• Splitting a non-leaf node: when inserting new entry into an already full non-
leaf node N
• Copy N to an temporary memory area M with space for n+1 pointers and
n keys
• Insert (k,p) into M
• Copy P1, K1, …, K é(n+1)/2ù-1, P é(n+1)/2ù from M back into the original node N
• Copy Pé(n+1)/2ù+1, K é(n+1)/2ù+1,…, Kn, Pn+1 from M into newly allocated node
N’
• Insert the middle entry (K é(n+1)/2ù,N’) into parent node
P1 K1 P2 K2 P3 K3 P4 P1 K1 P2 P3 K3 P4
Newnode N`
For non-leaf node (ch11Page 33) K2 Insert toparent
temporarymemory area M
Original node
Recap: B+ Tree Node Split (n =3)
P1 K1 P2 K2 P3 K3 P4 P1 K1 P2 P3 K3 P4
Newnode
For non-leaf node (ch11Page 33)
K1 K2 K3 K1 K2 K3
K3
Newnode
For leaf node (ch11 Page30)
K2
Insert toparent
Insert toparent
temporarymemory
temporarymemory
Q1. (1)
An example of B+-Tree
How to draw B+tree ?
K1 K2
K3 K4 … …
K1,K2
K3,K4 … K1,K2
Wrong!values & pointers
88 89
90
88 89 90
90
88 89 90 107
1) Insert 89 & 88
2) Insert 90
Split leaf node
3) Insert 107
Q1. (1)
89 90
86 88 89 90 107
88
53 86 88 89 90 107
90
89
Q1 (1)
4 )Insert 86
Split leaf node
5) Insert 53
Split leaf node and
non-leaf node
90
88 89 90 107
6) Insert 52
Split leaf node
Q1 (1)
86
86 88 89 90 107
90
89
52 53
88
7) Insert 87
86
86 87 88 89 90 107
90
89
52 53
88
88
53 86 88 89 90 107
90
89
8) Insert 34
Split leaf node
and non-leaf node
Q1 (1)
88
86 87 88 89 90 107
90
86
5334 52
53
89
9) Insert 17
Split leaf node
88
86 87 88 89 90 107
90
86
5352
52 53
89
17 34
86
86 87 88 89 90 107
90
89
52 53
88
Q1 (1)
10) Insert 35
Split leaf node
and non-leaf node
88
86 87 88 89 90 107
90
89
5352
53
35
17 34
35
52
86
88
86 87 88 89 90 107
90
86
5352
52 53
89
17 34
Q1 (1)
11) Insert 16
Split leaf node
88
86 87 88 89 90 107
90
89
5352
53
3534
34 35
52
86
16 17
88
86 87 88 89 90 107
90
89
5352
53
35
17 34
35
52
86
slides page 37
Delete 52
(1) (2) (3)
53
53
52
53
5252
Q1.2
88
86 87 88 89 90 107
90
89
53
53
3534
34 35
86
16 17
redistribute
delete 52
88
86 87 88 89 90 107
90
89
5352
53
3534
34 35
86
16 17
52
Q1.2 delete 52
redistribute
88
86 87 88 89 90 107
90
89
53
53
3534
34
35
86
16 17
88
86 87 88 89 90 107
90
89
53
53
3534
34 35
86
16 17
redistribute
Assignment 2
Assignment 2
Example-Dynamic hash index
Slides ch11b.ppt page 17 - 24
Q & A
Example- Static hash index