CSCI 4380 Database Systems
2025 spring
Instructor: Lei Yu
Assistant Prof, Department of Computer Science
Outline:
• Test 2 grades released.
• Makeup test grades will be available soon.
• Lecture 21 Exercise after class: 48 hours
• Conventional indexes
• B-Trees
The Main Purpose of Index Structures
Speedup the search process
3
indexσa=6(R)
blocks
containing
the desired
tuples
quickly
figure out
disks
otherwise have to
scan the entire R
also need to handle dynamic changes of R
Root
B+Tree Example n=3
10
0
12
0
15
0
18
0
30
3 5 11 30 35 10
0
10
1
11
0
12
0
13
0
15
0
15
6
17
9
18
0
20
0
Sample non-leaf
to keys to keys to keys to keys
< 57 57£ k<81 81£k<95 ³95
57 81 95
Sample leaf node:
From non-leaf node
to next leaf
in sequence
57 81 95
To
re
co
rd

w
ith
k
ey
5
7
To
re
co
rd

w
ith
k
ey
8
1
To
re
co
rd

w
ith
k
ey
8
5
In textbook’s notation n=3
Leaf:
Non-leaf:
30 35
30
30 35
30
B+tree rules
q Rule 1. All leaves are at same lowest level (balanced
tree)
q Rule 2. Pointers in leaves point to records except for
“sequence pointer”
q Rule 3. Number of keys/pointers in nodes:
8
Max. #
pointers
Max. #
keys
Min. #
pointers
Min. #
keys
Non-leaf n+1 n é(n+1)/2ù é(n+1)/2ù-1
Leaf n+1 n ë(n+1)/2û+1 ë(n+1)/2û
Root n+1 n 2 1
A B+tree node of order n
pn+1knk2p2k1p1 p3 ……
k1 k2 ‧‧‧‧‧‧ kn
p1 p2 p3 pn+1pn
pn
k1 k2 …
p1 p2 p3
Minimum Occupancy Rule (or Minimum Fill
Factor Rule)
• Balance and Predictable Height: To keep the tree from
becoming lopsided or sparse, we enforce a rule that each node
(except the root) must be at least half full.
• Space Efficiency: Nodes map directly to disk blocks, and
Accessing a half-empty block is a waste of I/O.
Max. #
pointers
Max. #
keys
Min. #
pointers
Min. #
keys
Non-leaf n+1 n é(n+1)/2ù é(n+1)/2ù-1
Leaf n+1 n ë(n+1)/2û+1 ë(n+1)/2û
Root n+1 n 2 1
Full node min. node
Non-leaf
Leaf
n=3
12
0
15
0
18
0
30
3 5 11 30 35
co
un
ts
e
ve
n
if
nu
ll
Search in a B+tree
1. Start from the root
2. Search in a leaf block
3. May not have to go to the data file
11
Search(ptr, k);
\\ search a record of key value k in the subtree rooted at ptr
\\ assume the B+tree is a dense index of order n
Case 1. ptr is a leaf \\ pn+1 is the sequence pointer
IF (k = ki) for a key ki in *ptr THEN return(pi);
ELSE return(Null);
Case 2. ptr is not a leaf
find a key ki in *ptr such that ki-1 ≤ k < ki;
return(Search(pi, k));
Search in B+tree
12
A tree node
Search(ptr, k);
\\ search a record of key value k in the subtree rooted at ptr
\\ assume the B+tree is a dense index of order n
Case 1. ptr is a leaf \\ pn+1 is the sequence pointer
IF (k = ki) for a key ki in *ptr THEN return(pi);
ELSE return(Null);
Case 2. ptr is not a leaf
find a key ki in *ptr such that ki-1 ≤ k < ki;
return(Search(pi, k));
k1 k2 ‧‧‧‧‧‧ kn
p1 p2 p3 pn+1pn
Search in B+tree
13
100
30 120 150 180
3 5 11 30 35 100 101 110 120 130 150 156 179 180 200
root
Search(ptr, k);
\\ search a record of key value k in the subtree rooted at ptr
\\ assume the B+tree is a dense index of order n
Case 1. ptr is a leaf \\ pn+1 is the sequence pointer
IF (k = ki) for a key ki in *ptr THEN return(pi);
ELSE return(Null);
Case 2. ptr is not a leaf
find a key ki in *ptr such that ki-1 ≤ k < ki;
return(Search(pi, k));
A tree node
k1 k2 ‧‧‧‧‧‧ kn
p1 p2 p3 pn+1pn
Search in B+tree
14
100
30 120 150 180
3 5 11 30 35 100 101 110 120 130 150 156 179 180 200
root
Search(*prt, 130)
Search(ptr, k);
\\ search a record of key value k in the subtree rooted at ptr
\\ assume the B+tree is a dense index of order n
Case 1. ptr is a leaf \\ pn+1 is the sequence pointer
IF (k = ki) for a key ki in *ptr THEN return(pi);
ELSE return(Null);
Case 2. ptr is not a leaf
find a key ki in *ptr such that ki-1 ≤ k < ki;
return(Search(pi, k));
A tree node
k1 k2 ‧‧‧‧‧‧ kn
p1 p2 p3 pn+1pn
Search in B+tree
15
100
30 120 150 180
3 5 11 30 35 100 101 110 120 130 150 156 179 180 200
root
Search(*prt, 130)
Search(ptr, k);
\\ search a record of key value k in the subtree rooted at ptr
\\ assume the B+tree is a dense index of order n
Case 1. ptr is a leaf \\ pn+1 is the sequence pointer
IF (k = ki) for a key ki in *ptr THEN return(pi);
ELSE return(Null);
Case 2. ptr is not a leaf
find a key ki in *ptr such that ki-1 ≤ k < ki;
return(Search(pi, k));
A tree node
k1 k2 ‧‧‧‧‧‧ kn
p1 p2 p3 pn+1pn
Search in B+tree
16
100
30 120 150 180
3 5 11 30 35 100 101 110 120 130 150 156 179 180 200
root
Search(*prt, 130)
100 £ 130
Search(ptr, k);
\\ search a record of key value k in the subtree rooted at ptr
\\ assume the B+tree is a dense index of order n
Case 1. ptr is a leaf \\ pn+1 is the sequence pointer
IF (k = ki) for a key ki in *ptr THEN return(pi);
ELSE return(Null);
Case 2. ptr is not a leaf
find a key ki in *ptr such that ki-1 ≤ k < ki;
return(Search(pi, k));
A tree node
k1 k2 ‧‧‧‧‧‧ kn
p1 p2 p3 pn+1pn
Search in B+tree
17
100
30 120 150 180
3 5 11 30 35 100 101 110 120 130 150 156 179 180 200
root
Search(*prt, 130)
100 £ 130
12
0 £
13
0 <
15
0
Search(ptr, k);
\\ search a record of key value k in the subtree rooted at ptr
\\ assume the B+tree is a dense index of order n
Case 1. ptr is a leaf \\ pn+1 is the sequence pointer
IF (k = ki) for a key ki in *ptr THEN return(pi);
ELSE return(Null);
Case 2. ptr is not a leaf
find a key ki in *ptr such that ki-1 ≤ k < ki;
return(Search(pi, k));
A tree node
k1 k2 ‧‧‧‧‧‧ kn
p1 p2 p3 pn+1pn
Search in B+tree
18
100
30 120 150 180
3 5 11 30 35 100 101 110 120 130 150 156 179 180 200
root
Search(*prt, 130)
12
0 £
13
0 <
15
0
130 =130
return
100 £ 130
Search(ptr, k);
\\ search a record of key value k in the subtree rooted at ptr
\\ assume the B+tree is a dense index of order n
Case 1. ptr is a leaf \\ pn+1 is the sequence pointer
IF (k = ki) for a key ki in *ptr THEN return(pi);
ELSE return(Null);
Case 2. ptr is not a leaf
find a key ki in *ptr such that ki-1 ≤ k < ki;
return(Search(pi, k));
A tree node
k1 k2 ‧‧‧‧‧‧ kn
p1 p2 p3 pn+1pn
Range Search in B+tree
19
To research all records whose key values are
between k1 and k2:
Range Search in B+tree
20
To research all records whose key values are
between k1 and k2:
Range-Search(ptr, k1, k2)
1. Call Search(ptr, k1);
2. Follow the sequence pointers until the
search key value is larger than k2.
Range Search in
B+tree
21
Range-Search(ptr, k1, k2)
1. Call Search(ptr, k1);
2. Follow the sequence pointers until the
search key value is larger than k2.
100
30 120 150 180
3 5 11 30 35 100 101 110 120 130 150 156 179 180 200
root
Search(ptr, k);
\\ search a record of key value k in the subtree rooted at ptr
\\ assume the B+tree is a dense index of order n
Case 1. ptr is a leaf \\ pn+1 is the sequence pointer
IF (k = ki) for a key ki in *ptr THEN return(pi);
ELSE return(Null);
Case 2. ptr is not a leaf
find a key ki in *ptr such that ki-1 ≤ k < ki;
return(Search(pi, k));
A tree node
k1 k2 ‧‧‧‧‧‧ kn
p1 p2 p3 pn+1pn
Range Search in
B+tree
22
Range-Search(ptr, k1, k2)
1. Call Search(ptr, k1);
2. Follow the sequence pointers until the
search key value is larger than k2.
100
30 120 150 180
3 5 11 30 35 100 101 110 120 130 150 156 179 180 200
root
Range-Search(*prt, 50, 125)
Search(ptr, k);
\\ search a record of key value k in the subtree rooted at ptr
\\ assume the B+tree is a dense index of order n
Case 1. ptr is a leaf \\ pn+1 is the sequence pointer
IF (k = ki) for a key ki in *ptr THEN return(pi);
ELSE return(Null);
Case 2. ptr is not a leaf
find a key ki in *ptr such that ki-1 ≤ k < ki;
return(Search(pi, k));
A tree node
k1 k2 ‧‧‧‧‧‧ kn
p1 p2 p3 pn+1pn
Range Search in
B+tree
23
Range-Search(ptr, k1, k2)
1. Call Search(ptr, k1);
2. Follow the sequence pointers until the
search key value is larger than k2.
100
30 120 150 180
3 5 11 30 35 100 101 110 120 130 150 156 179 180 200
root
Range-Search(*prt, 50, 125)
Search(*prt, 50)
Search(ptr, k);
\\ search a record of key value k in the subtree rooted at ptr
\\ assume the B+tree is a dense index of order n
Case 1. ptr is a leaf \\ pn+1 is the sequence pointer
IF (k = ki) for a key ki in *ptr THEN return(pi);
ELSE return(Null);
Case 2. ptr is not a leaf
find a key ki in *ptr such that ki-1 ≤ k < ki;
return(Search(pi, k));
A tree node
k1 k2 ‧‧‧‧‧‧ kn
p1 p2 p3 pn+1pn
Range Search in
B+tree
24
Range-Search(ptr, k1, k2)
1. Call Search(ptr, k1);
2. Follow the sequence pointers until the
search key value is larger than k2.
100
30 120 150 180
3 5 11 30 35 100 101 110 120 130 150 156 179 180 200
root
50
< 1
00
30 £ 50
Search(ptr, k);
\\ search a record of key value k in the subtree rooted at ptr
\\ assume the B+tree is a dense index of order n
Case 1. ptr is a leaf \\ pn+1 is the sequence pointer
IF (k = ki) for a key ki in *ptr THEN return(pi);
ELSE return(Null);
Case 2. ptr is not a leaf
find a key ki in *ptr such that ki-1 ≤ k < ki;
return(Search(pi, k));
Range-Search(*prt, 50, 125)
Search(*prt, 50)A tree node
k1 k2 ‧‧‧‧‧‧ kn
p1 p2 p3 pn+1pn
Range Search in
B+tree
25
Range-Search(ptr, k1, k2)
1. Call Search(ptr, k1);
2. Follow the sequence pointers until the
search key value is larger than k2.
100
30 120 150 180
3 5 11 30 35 100 101 110 120 130 150 156 179 180 200
root
120 £ 125
return
50
< 1
00
30 £ 50
110 £ 125
101 £ 125
100 £ 125
return
returnreturn
135 > 125
STOP
35 < 50
Not
Return
Search(ptr, k);
\\ search a record of key value k in the subtree rooted at ptr
\\ assume the B+tree is a dense index of order n
Case 1. ptr is a leaf \\ pn+1 is the sequence pointer
IF (k = ki) for a key ki in *ptr THEN return(pi);
ELSE return(Null);
Case 2. ptr is not a leaf
find a key ki in *ptr such that ki-1 ≤ k < ki;
return(Search(pi, k));
Range-Search(*prt, 50, 125)
Search(*prt, 50)A tree node
k1 k2 ‧‧‧‧‧‧ kn
p1 p2 p3 pn+1pn
Insert into B+tree
26
Insert into B+tree
Basic idea:
1. Find the leaf L where the record r should be
inserted;
2. If L has further room, then insert r into L, and return;
3. If L is full, spilt L plus r into two leaves (each is
about half full): this causes an additional child for the
parent P of L, thus we need to add a child to P;
4. If P is already full, then we have to split P and add an
additional child to P’s parent … (recursively)
27
Insert into B+tree
q Simple case (space available for new child)
q Leaf overflow
q Non-leaf overflow
q New root
28
Insert into B+tree
q Simple case (space available for new child)
q Leaf overflow
q Non-leaf overflow
q New root
29
order n=3
30
I. Simple case: Insert key 32
100
30 40
3 5 11 30 31
order n=3
31
I. Simple case: Insert key 32
100
30 40
3 5 11 30 31
Insert(prt, 32)
order n=3
32
I. Simple case: Insert key 32
100
30 40
3 5 11 30 31
Insert(prt, 32)
32
< 1
00
30 £ 32 <40
order n=3
33
I. Simple case: Insert key 32
100
30 40
3 5 11 30 31
Insert(prt, 32)
32
< 1
00
30 £ 32 <40
room for 32
order n=3
34
I. Simple case: Insert key 32
100
30 40
3 5 11 30 31 32
Insert(prt, 32)
32
< 1
00
30 £ 32 <40
Insert into B+tree
q Simple case (space available for new child)
q Leaf overflow
q Non-leaf overflow
q New root
35
Insert into B+tree
q Simple case (space available for new child)
q Leaf overflow
q Non-leaf overflow
q New root
36
Insert into B+tree
q Simple case (space available for new child)
q Leaf overflow
q Non-leaf overflow
q New root
37
Idea: when there is no space for a new child
(all pointers are in use), split the node into
two nodes, with both at least half full.
38
Complication: node overflow
39
Complication: Leaf overflow
40
pn+1 kn+1
p1 k1 … p k p k … … pn kn p* + 1 /2 + 1 /2 + 1 /2 +1 + 1 /2 +1
Complication: Leaf overflow
p k p’
41
p1 k1 … p k --- p** p k … pn kn pn+1 kn+1 --- p* + 1 /2 + 1 /2 + 1 /2 +1 + 1 /2 +1
pn+1 kn+1
p1 k1 … p k p k … … pn kn p* + 1 /2 + 1 /2 + 1 /2 +1 + 1 /2 +1
Complication: Leaf overflow
p k k p’
p k p’
42
p1 k1 … p k --- p** p k … pn kn pn+1 kn+1 --- p* + 1 /2 + 1 /2 + 1 /2 +1 + 1 /2 +1
pn+1 kn+1
p1 k1 … p k p k … … pn kn p* + 1 /2 + 1 /2 + 1 /2 +1 + 1 /2 +1
Complication: Leaf overflow
p k k p’
p k p’
43
p1 k1 … p k --- p** p k … pn kn pn+1 kn+1 --- p* + 1 /2 + 1 /2 + 1 /2 +1 + 1 /2 +1
pn+1 kn+1
p1 k1 … p k p k … … pn kn p* + 1 /2 + 1 /2 + 1 /2 +1 + 1 /2 +1
Complication: Leaf overflow
p k k p’ q
p k p’
44
p1 k1 … p k --- p** p k … pn kn pn+1 kn+1 --- p*
p k k p’ q
+ 1 /2 + 1 /2 + 1 /2 +1 + 1 /2 +1
pn+1 kn+1
p1 k1 … p k p k … … pn kn p* + 1 /2
p k p’
+ 1 /2 + 1 /2 +1 + 1 /2 +1
Complication: Leaf overflow
?
What is the
key here?
45
p1 k1 … p k --- p** p k … pn kn pn+1 kn+1 --- p*
p k k p’ q
+ 1 /2 + 1 /2 + 1 /2 +1 + 1 /2 +1
pn+1 kn+1
p1 k1 … p k p k … … pn kn p* + 1 /2
p k p’
+ 1 /2 + 1 /2 +1 + 1 /2 +1
Complication: Leaf overflow
?
What is the
key here?
46
p1 k1 … p k --- p** p k … pn kn pn+1 kn+1 --- p*
p k k p’ q
+ 1 /2 + 1 /2 + 1 /2 +1 + 1 /2 +1
pn+1 kn+1
p1 k1 … p k p k … … pn kn p* + 1 /2
p k p’
+ 1 /2 + 1 /2 +1 + 1 /2 +1
Complication: Leaf overflow
+ 1 /2 +1
k ≤ x < k; + 1 /2 +1
47
100
30
3 5 11 30 31
Leaf overflow: Insert key 7 (order n = 3)
48
100
30
3 5 11 30 31
Leaf overflow: Insert key 7 (order n = 3)
7
49
100
30
3 5 30 31
Leaf overflow: Insert key 7 (order n = 3)
7 11
50
100
30
3 5 30 31
Leaf overflow: Insert key 7 (order n = 3)
7 11
3 5 11
7
51
100
30
3 5 30 31
Leaf overflow: Insert key 7 (order n = 3)
7 11
3 5 11
7
52
100
30
3 5 30 31
Leaf overflow: Insert key 7 (order n = 3)
7 11
3 5 11
7
53
100
30
3 5 30 31
Leaf overflow: Insert key 7 (order n = 3)
7 11
3 5 11
7
54
100
7 30
3 5 30 31
Leaf overflow: Insert key 7 (order n = 3)
7 11
3 5 11
7
55
Complication: nonleaf overflow
56
kn+1 pn+2p1 k1 … p k p k p k … pn kn pn+1 ( + 1)/2( + 1)/2 -1 ( + 1)/2 -1 ( + 1)/2
p k’ p’
( + 1)/2 +1 ( + 1)/2 +1
Complication: nonleaf overflow
57
kn+1 pn+2p1 k1 … p k p k p k … pn kn pn+1 ( + 1)/2( + 1)/2 -1 ( + 1)/2 -1 ( + 1)/2
p k’ p’
p1 k1 p2 k2 … p k p( + 1)/2 -1 ( + 1)/2 -1 p k … pn kn pn+1 kn+1 pn+2( + 1)/2 +1
k ( + 1)/2p k’ p’q
( + 1)/2 ( + 1)/2 +1
( + 1)/2 +1 ( + 1)/2 +1
Complication: nonleaf overflow
58
kn+1 pn+2p1 k1 … p k p k p k … pn kn pn+1 ( + 1)/2( + 1)/2 -1 ( + 1)/2 -1 ( + 1)/2
p k’ p’
p1 k1 p2 k2 … p k p( + 1)/2 -1 ( + 1)/2 -1 p k … pn kn pn+1 kn+1 pn+2( + 1)/2 +1
k ( + 1)/2p k’ p’q
( + 1)/2 ( + 1)/2 +1
( + 1)/2 +1 ( + 1)/2 +1
Complication: nonleaf overflow
59
kn+1 pn+2p1 k1 … p k p k p k … pn kn pn+1 ( + 1)/2( + 1)/2 -1 ( + 1)/2 -1 ( + 1)/2
p k’ p’
p1 k1 p2 k2 … p k p( + 1)/2 -1 ( + 1)/2 -1 p k … pn kn pn+1 kn+1 pn+2( + 1)/2 +1
k ( + 1)/2p k’ p’q
( + 1)/2 ( + 1)/2 +1
( + 1)/2 +1 ( + 1)/2 +1
Complication: nonleaf overflow
60
kn+1 pn+2p1 k1 … p k p k p k … pn kn pn+1 ( + 1)/2( + 1)/2 -1 ( + 1)/2 -1 ( + 1)/2
p k’ p’
p1 k1 p2 k2 … p k p( + 1)/2 -1 ( + 1)/2 -1 p k … pn kn pn+1 kn+1 pn+2( + 1)/2 +1
k ( + 1)/2p k’ p’q
( + 1)/2 ( + 1)/2 +1
( + 1)/2 +1 ( + 1)/2 +1
Complication: nonleaf overflow
?
What is the
key here?
61
kn+1 pn+2p1 k1 … p k p k p k … pn kn pn+1 ( + 1)/2( + 1)/2 -1 ( + 1)/2 -1 ( + 1)/2
p k’ p’
p1 k1 p2 k2 … p k p( + 1)/2 -1 ( + 1)/2 -1 p k … pn kn pn+1 kn+1 pn+2( + 1)/2 +1
k ( + 1)/2p k’ p’q
( + 1)/2 ( + 1)/2 +1
( + 1)/2 +1 ( + 1)/2 +1
Complication: nonleaf overflow
?
not used
What is the
key here?
62
kn+1 pn+2p1 k1 … p k p k p k … pn kn pn+1 ( + 1)/2( + 1)/2 -1 ( + 1)/2 -1 ( + 1)/2
p k’ p’
p1 k1 p2 k2 … p k p( + 1)/2 -1 ( + 1)/2 -1 p k … pn kn pn+1 kn+1 pn+2( + 1)/2 +1
k ( + 1)/2p k’ p’q
( + 1)/2 ( + 1)/2 +1
( + 1)/2 +1 ( + 1)/2 +1
Complication: nonleaf overflow

63
Nonleaf overflow: Insert key 160 (order n = 3)
100
120 150 180
150 156 179 180 210
160
64
Nonleaf overflow: Insert key 160 (order n = 3)
100
120 150 180
150 156 180 210
150 156 179
160
160 179
65
Nonleaf overflow: Insert key 160 (order n = 3)
100
120 150 180
150 156 180 210
150 156 179
160
160 179
66
Nonleaf overflow: Insert key 160 (order n = 3)
100
120 150 180
150 156 180 210
150 156 179
160
160 179
160
67
Nonleaf overflow: Insert key 160 (order n = 3)
100
120 150 180
150 156 180 210
150 156 179
160
160 179
no room!
160
68
Nonleaf overflow: Insert key 160 (order n = 3)
100
120
150 156 180 210
150 156 179
160
160 179
120 150 180
160
160 180150
69
Nonleaf overflow: Insert key 160 (order n = 3)
100
120
150 156 180 210
150 156 179
160
160 179
160 180150
120 150 180
160
70
Nonleaf overflow: Insert key 160 (order n = 3)
100 150
120
150 156 180 210
150 156 179
160
160 179
160 180150
120 150 180
160
Delete in B+tree
71
Delete in B+tree
Basic idea:
1. Find the leaf L where the record r should be
deleted;
2. If L remains at least half-full after deleting r, then
delete r, and return;
3. Else consider the sibling L’ of L;
3.1 If L’ is more than half-full, then move a record
from L’ to L, and return;
3.2 Else combine L and L’ into a single leaf;
3.3 But now you need to consider the case of deleting
a child from L’s parent … (recursively)
72
q Simple case: the node remains at least half-full after deletion.
q Re-distribute keys among siblings
q Coalesce with a sibling and delete a pointer from its father
73
Delete in B+tree
q Simple case: the node remains at least half-full after deletion.
q Re-distribute keys among siblings
q Coalesce with a sibling and delete a pointer from its father
74
Delete in B+tree
75
order n=3Simple case: Delete key 35
76
order n=3Simple case: Delete key 35
105
10 40
3 5 8 10 20 35
Delete(prt, 35)
40 50
77
order n=3Simple case: Delete key 35
105
10 40
3 5 8 10 20 35
Delete(prt, 35)
40 50
Delete
35
78
order n=3Simple case: Delete key 35
105
10 40
3 5 8 10 20 35
Delete(prt, 35)
40 50
After deletion, the
node still keeps at
least half-full
79
order n=3Simple case: Delete key 35
105
10 40
3 5 8 10 20 40 50
q Simple case: the node remains at least half-full after
deletion.
q Re-distribute keys among siblings
q Coalesce with a sibling and delete a pointer from its father
80
Delete in B+tree
81
Key re-distribution at leaves
p1 k1 … pi ki ---
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht --- p* q*
i = ë(n+1)/2û - 1 t > ë(n+1)/2û
82
p1 k1 … pi ki ---
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht --- p* q*
p1 k1 … pi ki q1 h1 ---
p’ k’ p k p” k”
q2 h2 … qt ht --- p* q*
i = ë(n+1)/2û - 1 t > ë(n+1)/2û
Key re-distribution at leaves
83
p1 k1 … pi ki ---
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht --- p* q*
p1 k1 … pi ki q1 h1 ---
p’ k’ p k p” k”
q2 h2 … qt ht --- p* q*
h2
i = ë(n+1)/2û - 1 t > ë(n+1)/2û
Key re-distribution at leaves
84
order n=3
Key re-distribution at leaves: Delete 5
85
order n=3
105
10 40
3 5 10 20 35
Delete(prt, 5)
40 50
Key re-distribution at leaves: Delete 5
86
105
10 40
3 5 10 20 35
Delete(prt, 5)
40 50
Delete 5
order n=3
Key re-distribution at leaves: Delete 5
87
105
10 40
3 5 10 20 35
Delete(prt, 5)
40 50
order n=3
Key re-distribution at leaves: Delete 5
88
105
10 40
3 5 10 20 35
Delete(prt, 5)
40 50
Less than
half-full !!
order n=3
Key re-distribution at leaves: Delete 5
89
105
10 40
3 5 10 20 35
Delete(prt, 5)
40 50
Look at the sibling,
which is more than
half-full, so we can
redistribute the keysa
order n=3
Key re-distribution at leaves: Delete 5
90
105
10 40
3 5 10 20 35
Delete(prt, 5)
40 50
Look at the sibling,
which is more than
half-full, so we can
redistribute the keys
order n=3
Key re-distribution at leaves: Delete 5
91
105
10 40
3 10 20 35
Delete(prt, 5)
40 50
redistribution
3 10 20 35
order n=3
Key re-distribution at leaves: Delete 5
92
105
10 40
3 10 20 35
Delete(prt, 5)
40 50
redistribution
3 10 20 35
20
order n=3
Key re-distribution at leaves: Delete 5
93
105
10 40
3 10 20 35
Delete(prt, 5)
40 50
redistribution
3 10 20 35
20
20
order n=3
Key re-distribution at leaves: Delete 5
94
105
20 40
3 10 20 35 40 50
order n=3
Key re-distribution at leaves: Delete 5
95
Key re-distribution at nonleaves
96
Key re-distribution at nonleaves
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
i+1 = é(n+1)/2ù - 1 t+1> é(n+1)/2ù
97
Key re-distribution at nonleaves
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
i+1 = é(n+1)/2ù - 1 t+1> é(n+1)/2ù
98
Key re-distribution at nonleaves
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
p1 k1 … pi ki pi+1 q1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
i+1 = é(n+1)/2ù - 1 t+1> é(n+1)/2ù
99
Key re-distribution at nonleaves
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
p1 k1 … pi ki pi+1 q1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
?
i+1 = é(n+1)/2ù - 1 t+1> é(n+1)/2ù
100
Key re-distribution at nonleaves
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
p1 k1 … pi ki pi+1 q1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
?
i+1 = é(n+1)/2ù - 1 t+1> é(n+1)/2ù
101
Key re-distribution at nonleaves
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
p1 k1 … pi ki pi+1 q1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
k’
i+1 = é(n+1)/2ù - 1 t+1> é(n+1)/2ù
102
Key re-distribution at nonleaves
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
p1 k1 … pi ki pi+1 q1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
k’
?
i+1 = é(n+1)/2ù - 1 t+1> é(n+1)/2ù
103
Key re-distribution at nonleaves
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
p1 k1 … pi ki pi+1 q1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
k’
?
i+1 = é(n+1)/2ù - 1 t+1> é(n+1)/2ù
104
Key re-distribution at nonleaves
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
p1 k1 … pi ki pi+1 q1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
k’
h1
i+1 = é(n+1)/2ù - 1 t+1> é(n+1)/2ù
105
Key re-distribution at nonleaves
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 q2 h2 … qt ht qt+1
-
p1 k1 … pi ki pi+1 q1
p’ k’ p k p” k”
q2 h2 … qt ht qt+1 k’
h1
i+1 = é(n+1)/2ù - 1 t+1> é(n+1)/2ù
q Simple case: the node remains at least half-full after
deletion.
q Re-distribute keys among siblings
q Coalesce with a sibling and delete a pointer from its father
106
Delete in B+tree
q Simple case: the node remains at least half-full after
deletion.
q Re-distribute keys among siblings
q Coalesce with a sibling and delete a pointer from its father
107
Delete in B+tree
Observation: when two siblings both are no more than half full,
coalesce them into a single node (which is nearly full)
108
Node Coalescence
109
Leaf Coalescence
110
p1 k1 … pi ki ---
p’ k’ p k p” k”
q1 h1 … qt ht --- p* q*
i = ë(n+1)/2û - 1 t = ë(n+1)/2û
Leaf Coalescence
111
p1 k1 … pi ki ---
p’ k’ p k p” k”
q1 h1 … qt ht --- p* q*
p1 k1 … pi ki
p’ k’ p k p” k”
q1 h1 … qt ht - q* q*
i = ë(n+1)/2û - 1 t = ë(n+1)/2û
Leaf Coalescence
112
p1 k1 … pi ki ---
p’ k’ p k p” k”
q1 h1 … qt ht --- p* q*
p1 k1 … pi ki
p’ k’ p k p” k”
q1 h1 … qt ht - q* q*
i = ë(n+1)/2û - 1 t = ë(n+1)/2û
Leaf Coalescence
113
Leaf coalescence : Delete key 5
114
order n=3
Leaf coalescence : Delete key 5
38
10
3 5 10 20
Delete(prt, 5)
40 50
60 80
60 75 80 90
115
order n=3
Leaf coalescence : Delete key 5
38
10
3 5 10 20
Delete(prt, 5)
40 50
60 80
60 75
Delete 5
80 90
116
order n=3
Leaf coalescence : Delete key 5
38
10
3 5 10 20
Delete(prt, 5)
40 50
60 80
60 75 80 90
117
order n=3
Leaf coalescence : Delete key 5
38
10
3 5 10 20
Delete(prt, 5)
40 50
60 80
60 75
The sibling is just
half-full, so we
should coalesce
80 90
118
order n=3
Leaf coalescence : Delete key 5
38
10
3 10 20 10 20
Delete(prt, 5)
40 50
60 80
60 75
3 5 10 20
Leaf
coalescence
80 90
119
order n=3
Leaf coalescence : Delete key 5
38
10
3 10 20 10 20
Delete(prt, 5)
40 50
60 80
60 75
3 5 10 20
Less than
half-full
Leaf
coalescence
80 90
120
order n=3
Leaf coalescence : Delete key 5
38
10
3 10 20 10 20
Delete(prt, 5)
40 50
60 80
60 75
3 5 10 20
Less than
half-full
Leaf
coalescence
more than
half-full, so
we can re-
distribute
pointers at
nonleaves
80 90
121
order n=3
38
10
3 10 20 10 20
Delete(prt, 5)
40 50
60 80
60 75
3 5 10 20
Less than
half-full
Leaf
coalescence
more than
half-full, so
we can re-
distribute
pointers at
nonleaves
80 90
Leaf coalescence : Delete key 5
122
order n=3
Key re-distribution at Nonleaves
38
10
3 10 20 10 20
Delete(prt, 5)
40 50
60 80
60 75
3 5 10 20
Less than
half-full
Leaf
coalescence
more than
half-full, so
we can re-
distribute
pointers at
nonleaves
80 90
123
order n=3
Key re-distribution at Nonleaves
38
10
3 10 20 10 20
Delete(prt, 5)
40 50
60 80
60 75
3 5 10 20
Less than
half-full
Leaf
coalescence
38
60 more than
half-full, so
we can re-
distribute
pointers at
nonleaves
80 90
124
order n=3
Key re-distribution at Nonleaves
38
10
3 10 20 10 20
Delete(prt, 5)
40 50
60 80
60 75
3 5 10 20
Less than
half-full
Leaf
coalescence
38
60
80
more than
half-full, so
we can re-
distribute
pointers at
nonleaves
80 90
125
order n=3
Key re-distribution at Nonleaves
60
38
3 10 20 40 50
80 80
60 75 80 90
126
Nonleaf Coalescence
127
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 … qt ht qt+1
i+1 = é(n+1)/2ù - 1 t+1= é(n+1)/2ù
Nonleaf Coalescence
128
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 … qt ht qt+1
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 … qt ht qt+1 q1 h1 … qt ht qt+1
i+1 = é(n+1)/2ù - 1 t+1= é(n+1)/2ù
Nonleaf Coalescence
129
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 … qt ht qt+1
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 … qt ht qt+1 q1 h1 … qt ht qt+1 ?
i+1 = é(n+1)/2ù - 1 t+1= é(n+1)/2ù
Nonleaf Coalescence
130
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 … qt ht qt+1
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 … qt ht qt+1 q1 h1 … qt ht qt+1 ?
i+1 = é(n+1)/2ù - 1 t+1= é(n+1)/2ù
Nonleaf Coalescence
131
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 … qt ht qt+1
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 … qt ht qt+1 q1 h1 … qt ht qt+1 k
i+1 = é(n+1)/2ù - 1 t+1= é(n+1)/2ù
Nonleaf Coalescence
132
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 … qt ht qt+1
p1 k1 … pi ki pi+1
p’ k’ p k p” k”
q1 h1 … qt ht qt+1 q1 h1 … qt ht qt+1 k
i+1 = é(n+1)/2ù - 1 t+1= é(n+1)/2ù
Nonleaf Coalescence
133
order n=3
Nonleaf coalescence : Delete key 5
134
order n=3
Nonleaf coalescence : Delete key 5
55
10
Delete(prt, 5)
55 58
60
61 723 5 10 20
135
order n=3
Nonleaf coalescence : Delete key 5
55
10
Delete(prt, 5)
55 58
60
61 723 5 10 20
delete 5
136
order n=3
Nonleaf coalescence : Delete key 5
55
10
Delete(prt, 5)
55 58
60
61 723 5 10 20
137
order n=3
Nonleaf coalescence : Delete key 5
55
10
Delete(prt, 5)
55 58
60
61 723 10 20 10 20
leaf
coalescence
3 5 10 20
138
order n=3
Nonleaf coalescence : Delete key 5
55
10
Delete(prt, 5)
55 58
60
61 723 10 20 10 20
leaf
coalescence
3 5 10 20
less than
half-full
139
order n=3
Nonleaf coalescence : Delete key 5
55
10
Delete(prt, 5)
55 58
60
61 723 10 20 10 20
leaf
coalescence
3 5 10 20
less than
half-full
just half-full,
so we need to
coalesce
140
order n=3
Nonleaf coalescence : Delete key 5
55
55 60
Delete(prt, 5)
55 58
60
61 723 10 20 10 20
leaf
coalescence
3 5 10 20
55 60
nonleaf
coalescence
141
order n=3
Nonleaf coalescence : Delete key 5
55
55 60
Delete(prt, 5)
55 58
60
61 723 10 20 10 20
leaf
coalescence
3 5 10 20
55 60
nonleaf
coalescence new root
142
order n=3
Nonleaf coalescence : Delete key 5
55 60
55 58 61 723 10 20
B+tree deletions in practice
q Often, coalescing is not implemented
Too hard and not worth it!
143
Pseudo Code for Insertion in B+tree
Insert(pt, (p, k), (p', k')); \\ technically, the smallest key kmin in pt is also returned
\\ (p, k) is a pointer-key pair to be inserted into the subtree rooted at pt; p' is a new sibling
\\ of pt, if created, and k' is the smallest key value in p' ;
Case 1. pt = (p1, k1, ..., pi, ki, --, pn+1) is a leaf \\ pn+1 is the sequence pointer
IF (i < n) THEN insert (p, k) into pt; return(p' = Null, k' = 0);
ELSE re-arrange (p1, k1), ..., (pn, kn), and (p, k) into (ρ1, κ1, ..., ρn+1, κn+1);
create a new leaf p''; put (ρr+1, κr+1, …, ρn+1, κn+1, --, pn+1) in p''; \\ r = ë(n+1)/2û
put (ρ1, κ1, ..., ρr, κr, --, p'') in pt; \\ pn+1 and p'' are sequence pointers in p'' and pt.
IF pt is the root THEN create a new root with children pt and p'' (and key κr+1)
ELSE return(p' = p'', k' = κr+1);
Case 2. pt is not a leaf
find a key ki in pt such that ki-1 ≤ k < ki;
Insert(pi , (k, p), (k", p"));
IF (p" = Null) THEN return(k' = 0, p' = Null);
ELSE IF there is room in pt, THEN insert (k", p") into pt; return(k' = 0, p' = Null);
ELSE re-arrange the content in pt and (k", p") into (ρ1, κ1, ..., ρn+1, κn+1, ρn+2);
create a new node p''; put (ρr+1, κr+1, …, ρn+1, κn+1, ρn+2, -- ) in p''; \\ r = é(n+1)/2ù
leave (ρ1, κ1, ..., ρr-1, κr-1, ρr , -- ) in pt;
IF pt is the root THEN create a new root with children pt and p'' (and key κr)
ELSE return(p' = p'', k' = κr ).

144
Pseudo Code for Deletion in a B+tree
Delete(pt, (k,p), belowmin); \\ technically, the smallest key kmin in *pt is also returned
\\ (k,p) is the data record to be deleted from the subtree rooted at pt; belowmin = true if
\\ after deletion, pt has fewer than the required min # of pointers;
Case 1. pt is a leaf
delete (k,p) in pt;
IF pt has at least ë(n+1)/2û data pointers OR pt is the root
THEN return (belowmin = false) ELSE return (belowmin = true);
Case 2. pt is not a leaf
find a key ki in pt such that ki-1 ≤ k < ki;
Delete(pi , (k, p), belowmin');
IF (not belowmin') THEN return(belowmin= false);
ELSE IF pi has an adjacent sibling p' that has more than the required min # of pointers
THEN move one key-pointer pair from p' to pi;
ELSE combine pi with an adjacent sibling of pi into a single node;
IF pt is the root with only one pointer pi
THEN pt = pi; return(belowmin= false);
IF pt has at least é(n+1)/2ù pointers OR pt is the root
THEN return(belowmin= false) ELSE return(belowmin= true);

145
Application of B+ Tree
• Range query 19. Range Search in B+tree
• (a,b)
• What if b is infinite? - to the end of the chain of leaves.
• What if a is –infinite? – start from the first leaf.
• Duplicate keys
• B-tree on multiple attributes
• Scan efficiency
B-tree with Duplicate keys
• A non-leaf node stores the first key of the first node that is not
already present in the previous left sibling.
• If there is no such key, then a null (placeholder) value is stored at
this location.
B-tree with Duplicate keys
• A non-leaf node stores the first key of the first node that is not
already present in the previous left sibling.
• If there is no such key, then a null (placeholder) value is stored at
this location.
B-tree with Duplicate keys
• A non-leaf node stores the first key of the first node that is not
already present in the previous left sibling.
• If there is no such key, then a null (placeholder) value is stored at
this location.
B-tree with Duplicate keys
• A non-leaf node stores the first key of the first node that is not
already present in the previous left sibling.
• If there is no such key, then a null (placeholder) value is stored at
this location.
B-tree with Duplicate keys
• A non-leaf node stores the first key of the first node that is not
already present in the previous left sibling.
• If there is no such key, then a null (placeholder) value is stored at
this location.
Any key search becomes range query.
Index on multiple attributes
• An index on multiple attributes like A,B will sort tuples first by A
and then by B Index on R(X, Y)
X = 'C' & Y = 8
X = 'J' & 3 <= Y <= 8
Search for J,3 - J,8
'C' <= X <= 'E' & Y = 4
Search for C,4 - E,4
'C' <= X <= 'E' & 3 <= Y <= 8
Search for C,3 - E,8
Y <= 5
B-tree indices
• Each node in a B-tree is a disk page (stored on disk)
• Each B-tree is created on one or more key values
• Leaf nodes store one entry for each tuple: each entry has a key
value and a pointer to a tuple (dense index: one leaf node for each
tuple)
Example
• 92,000 tuples in instructors Index on instructors(coursecode,
instructor)
• To index each tuple: 9 (course code) + 16 (instructor) + 20 byte (for
tuple address) 45 bytes per tuple!
• Index page (assume) is 8KB Store: 8000/45 = about 177 tuples per
node
• Each node must have: 177 tuples max (88 tuples min) Assume
each node is 100% full (mostly):
• At leaf level: ceil(92,000/177) = 520 nodes in the leaf level
• The level above: ceil(520/177) = 3 nodes in the next internal level The level
above: ceil(3/177) = 1 node (root)
• Assume each node is 50% full (mostly):
• At leaf level: 1040 nodes At a level above: 12 nodes At a level above: 1
node
Cost of queries/index search
• Number of disk pages read/written
• For any search, find the first leaf node in the search and then
scan leaf nodes left to right following sibling pointers until the end
of the range is reached. This will find all the matching tuples for a
query.
• Depending on the query, these tuples may need to be read from
disk as well.
Example
• R(A,B,C,D,E), Assume: 100,000 tuples 10,000 pages ( 10 tuples
per page)
• Index I1 on R(A): 400 pages at leaf, 3 levels (root+internal+leaf)
• Index I2 on R(B): 400 pages at leaf, 3 levels (root+internal+leaf)
• Index I3 on R(A,B): 1,000 pages at leaf, 3 levels
(root+internal+leaf)
• Index I4 on R(B,A): 1,000 pages at leaf, 3 levels
(root+internal+leaf)
Example
• SELECT A,B,C,D,E FROM R
WHERE 10 <= A and A <= 20 ; (returns: 100 tuples)
Query plan 1 -> Scan the whole relation: Cost = 10,000
Query plan 2: Scan I1 (find tuple pointers that match 10<=A<=20) + Read all
tuples that I find based on the index from relation R
100,000/400 = 250 tuples per node
100 tuples for this query will fit in a single leaf node!
Cost to scan the index = 1 (root) + 1 (internal) + 1 or 2 (leaf) = 4 max
To read the matching 100 tuples: I need to read pages of R
How many pages do I need to read?
Best case: 10 pages (all packed sorted by A) + 4 = 14 pages
Worst case: 100 Cost of this query (max) : 4 + 100 = 104 pages
Example
• Query plan 3: Use index I3:
• 100,000 (tuples of R) / 1,000 = 100 tuples per node
• Cost of index search = 4 (max)
• Cost of searching the relation = 100 Total cost = 104 (max)
• Query plan 4: Use index I4: Index I4 on R(B,A): 1,000 pages at leaf,
3 levels (root+internal+leaf)
• Scan all leaf, cost of index search = 1 (root) + 1 (internal) + 1,000 (all leaf)
= 1002
• Scan the tuples = 100
• Cost = 1,102
Example
• SELECT B FROM R WHERE 10 <= A and A <= 20 ; (returns: 100
tuples)
• Query plans:
• 1. Scan all of R = 10,000
• 2. Use I1 on R(A) = 104 (max)
• 3. Use I3 on R(A,B) = 4 (index only search)
• 4. Use I4 on R(B,A) = 1,002 (index only search)

学霸联盟