Clustered index (1)

Alternative table structure to heap

Data stored in defined order

Fast lookup through B-tree

Records located through logical RID

create table foo (
first char(100), last char (100), city char (100))

create clustered index foo_c on foo (city)

Clustered index (2)
index tree pages
P
L L
P
L L
P
L L
R
data pages

Non-clustered index (1)

A way to provide a different ordering


Allows skipping of sort step in query

Singleton lookup
Matching record

Range scan

Allocation-order scan
1 23 45 6

What causes fragmentation (1)
Index leaf level of newly built index
Red arrow is the allocation order
Black arrows are following the logical order

What causes fragmentation (2)
Newly built index leaf after a single page split
Red arrow is the allocation order
Black arrows are following the logical order

What causes fragmentation (3)
Index leaf level after random inserts/deletes
Red arrow is the allocation order
Black arrows are following the logical order

Logical scan fragmentation

Occurs when the next logical page is not the next
physical page


Operates on leaf level only
17
Inside INDEXDEFRAG (4)
1 2 3 4
Physical Page ID
AB
BC
DE
EF
JK
KL
VW
WZ
1 2 3 4
Physical Page ID
AB
BC
DE
EF
JK
KL
VW
WZ
21041 2 3 4
Physical Page ID
AB
BC
DE
EF
JK

KL
VW
WZ
21041 2 3 4
Physical Page ID
AB
BC
DE
EF
JK
KL
VW
WZ
21041 2 3 4
Physical Page ID
AB
BC
DE
EF
JK
KL
VW
WZ
Page reordering example