Example multiway tree of order 5 (This is not a B-Tree, BTW)
E
K
P
B
D
G
M
N
Q
T
W
R
S
X
Y
Z
B-Tree Invariants
– Affix the order – m
– All nodes, except the top, have ceil(m/2)-1 keys. – All external nodes are at the same level.
B-Tree Invariants
– Affix the order – m
– All nodes, except the top, have ceil(m/2)-1 keys. – All external nodes are at the same level.
The tree from the first page is not a
B-Tree.
E
K
P
B
D
G
M
N
Q
T
W
R
S
X
Y
Z
To Construct a B-Tree
– Fill in the first node’s keys, until it’s full
– Example: Insert C, G and N into a tree of order 5:
To Construct a B-Tree
– Fill in the first node’s keys, until it’s full
– Example: Insert C, G and N into a tree of order 5: – Next, insert A:
C
G
N
To Construct a B-Tree
– Fill in the first node’s keys, until it’s full
– Example: Insert C, G and N into a tree of order 5: – Next, insert A:
– Suppose we now insert H.
A
C
G
N
To Construct a B-Tree
– Fill in the first node’s keys, until it’s full
– Example: Insert C, G and N into a tree of order 5: – Next, insert A:
– Suppose we now insert H.
A
C
G
H
N
It’s too big now, so we “split” it into three nodes:
To Construct a B-Tree
– Next, we’ll insert E, K and Q – these all go into leaf nodes.
G
H
N
A
C
To Construct a B-Tree
– Next, we’ll insert E, K and Q – these all go into leaf nodes. – Next, insert M – this requires a split:
G
H
K
N
Q
A
C
E
To Construct a B-Tree
– Next, we’ll insert E, K and Q – these all go into leaf nodes. – Next, insert M – this requires a split:
G
A
C
E
H
K
M
QN
Q
To Construct a B-Tree
– Next, we’ll insert E, K and Q – these all go into leaf nodes. – Next, insert M – this requires a split:
M moves up.
G
These keys go into a new external node
A
C
E
These keys stay
H
K
M
QN
Q
To Construct a B-Tree
– Next, we’ll insert E, K and Q – these all go into leaf nodes. – Next, insert M – this requires a split.
– Insert F, W, L, T
G
M
H
K
Q
N
Q
Q
A
C
E
To Construct a B-Tree
– Next, we’ll insert E, K and Q – these all go into leaf nodes. – Next, insert M – this requires a split.
– Insert F, W, L, T
– Insert Z: Another split
G
M
H
K
L
Q
N
Q
T
WQ
A
C
E
F
To Construct a B-Tree
– Next, we’ll insert E, K and Q – these all go into leaf nodes. – Next, insert M – this requires a split.
– Insert F, W, L, T
– Insert Z: Another split
G
M
H
K
L
Q
A
C
E
F
N
Q
T
WQ
Z
To Construct a B-Tree
– Next, we’ll insert E, K and Q – these all go into leaf nodes. – Next, insert M – this requires a split.
– Insert F, W, L, T
– Insert Z: Another split
T moves up.
G
M
These keys go into a new external node
H
K
L
Q
A
C
E
F
These keys stay
N
Q
T
WQ
QZ
To Construct a B-Tree
– Next, we’ll insert E, K and Q – these all go into leaf nodes. – Next, insert M – this requires a split.
– Insert F, W, L, T
– Insert Z: Another split
G
M
T
H
K
L
Q
N
Q
Q
W
Z
Q
A
C
E
F
To Construct a B-Tree – Insert D – another split:.
G
M
T
H
K
L
Q
N
Q
Q
W
Z
Q
A
C
E
F
To Construct a B-Tree – Insert D – another split:
G
M
T
H
K
L
Q
N
Q
Q
W
Z
Q
A
C
D
E
F
To Construct a B-Tree – Insert D – another split:
G
M
T
H
K
L
Q
N
Q
Q
W
Z
Q
A
C
D
These keys These keys stay go into a new external node
E
F
To Construct a B-Tree – Insert D – another split:
D
G
M
T
H
K
L
Q
N
Q
Q
W
Z
Q
A
C
E
F
To Construct a B-Tree
– Insert D – another split: – Add P, R, X, Y
D
G
M
T
H
K
L
Q
N
Q
Q
W
Z
Q
A
C
E
F
To Construct a B-Tree
– Insert D – another split: – Add P, R, X, Y
– Add S: Two Splits.
D
G
M
T
H
K
L
Q
W
X
Y
QZ
A
C
E
F
N
P
Q
QR
QS
To Construct a B-Tree
– Insert D – another split: – Add P, R, X, Y
– Add S: Two Splits.
D
G
M
T
H
K
L
Q
W
X
Y
QZ
A
C
E
F
N
P
Q
QR
QS
These keys stay
These keys go into a new external node
To Construct a B-Tree
– Insert D – another split: – Add P, R, X, Y
– Add S: Two Splits.
D
G
M
Q
T
H
K
L
Q
W
X
Y
QZ
A
C
E
F
N
P
Q
R
S
Q
– Add P, R, X, Y
– Add S: Two Splits.
These keys stay
These keys go into a new internal node
To Construct a B-Tree
– Insert D – another split:
New Root
D
G
M
Q
T
H
K
L
Q
W
X
Y
QZ
A
C
E
F
N
P
Q
R
S
Q
To Construct a B-Tree
– Insert D – another split: – Add P, R, X, Y
– Add S: Two Splits.
M
D
G
Q
T
H
K
L
Q
W
X
Y
QZ
A
C
E
F
N
P
Q
R
S
Q
Onto Deletion
– Delete H: It’s in a leaf & deleting it leaves enough keys – yay.
M
D
G
Q
T
H
K
L
Q
W
X
Y
QZ
A
C
E
F
N
P
Q
R
S
Q
Onto Deletion
– Delete T: It’s in an internal node. Replace with successor (W) & delete successor.
M
D
G
Q
T
K
L
Q
W
X
Y
QZ
A
C
E
F
N
P
Q
R
S
Q
Onto Deletion
– Delete R: If a sibling has an extra key, move it to its parent, and move the parent down.
M
D
G
Q
W
K
L
Q
X
Y
Z
Q
A
C
E
F
N
P
Q
R
S
Q
Onto Deletion
– Delete R: If a sibling has an extra key, move it to its parent, and move the parent down.
M
D
G
Q
W
K
L
Q
X
Y
Z
Q
A
C
E
F
N
P
Q
R
S
Q
Onto Deletion
– Delete E – no siblings w/ extra keys, so move parent down & coalesc with a sibling.
M
D
G
Q
X
K
L
Q
Y
Z
Q
A
C
E
F
N
P
Q
S
W
Q
Onto Deletion
– Delete E – no siblings w/ extra keys, so move parent down & coalesc with a sibling.
M
D
G
Q
X
K
L
Q
Y
Z
Q
A
C
E
F
N
P
Q
S
W
Q
Onto Deletion
– Now G has too few keys. – So move its parent down – & coalesce with sibling.
M
G
Q
X
K
L
Q
N
P
Q
S
W
Q
Y
Z
Q
A
C
D
F
Onto Deletion
– Now G has too few keys. – So move its parent down – & coalesce with sibling.
G
M
Q
X
K
L
Q
N
P
Q
S
W
Q
Y
Z
Q
A
C
D
F
B+ Tree (Backward from stvincent’s explanation)
– External nodes have pointers too.
– These are to data associated w/ key. – Internal key’s data in predecessor’s rightmost rightmost empty val.
M
D
G
Q
X
Y
Z
Q
K
L
Q
A
C
E
F
YZ
Nothing
N
P
Q
S
W
Q
ACD EFG KL
M
NP
QSW
X