Bài giảng Lưu trữ dữ liệu vật lý và các phương pháp truy xuất

 pointer
• Thích hợp cho những ứng dụng đặc trưng làm việc 
trên dữ liệu được sắp xếp (theo search key)
– Tìm kiếm: duyệt hoặc tìm tuần tự.
• Nên lưu trữ vật lý theo thứ tự của search key để 
giảm thiểu số block cần phải truy cập. Nhưng:
– Khi dữ liệu lớn, thao tác Insert, Delete phức tạp
33
• Insert: Định vị -> insert vào overflow block (≠ anchor block)-> phá 
vỡ thứ tự vật lý, phải tổ chức lại
… 1
… 2
… 4
… 1
… 2
… 4
3
Anchor
block
Overflow 
block
Hashing file
• Một hàm băm (hash function) được thiết lập 
trên 1 thuộc tính là search key của quan hệ.
• Nguyên lý: “lưu ở đâu, tìm ở đó”
• Chia tập tin thành các lô (bucket) tùy giá trị 
của search key. Mỗi lô có một số block, link 
nhau bởi pointer. Dữ liệu trong block được tổ 
chức như heap.
• B là số lượng các lô. Giá trị hàm băm tại giá 
34
trị tìm kiếm là số nguyên ∈ [0,B-1] cho biết lô 
chứa mẫu tin.Nếu khóa là chuỗi ký tự, ta định 
ra nguyên tắc chuyển chuỗi ký tự thành số.
18
Hashing file
• Tìm kiếm mẫu tin khóa v
– Tính h(v) để biết lô, và thực hiện tìm kiếm trong lô 
này.
Chèn•
– Tính h(v) để biết lô. Tìm kiếm khối cuối cùng của lô, 
nếu còn chỗ thì chèn, còn không thì cấp phát 1 khối 
khác chèn vào cuối danh sách của lô h(v).
• Xóa/ Sửa
– Tìm kiếm và sửa hoặc xóa (đánh dấu)
35
– Sau khi xóa, có thể phải thực hiện bước hiệu chỉnh 
(dồn dữ liệu trong khối) để giảm số lượng khối trong 
lô này.
Clustering file
MANV TENNV MAPB …
N1
N2
N3
A
B
C
20
10
20
…
…
…
10 TENPB ĐĐ
KT HCM
MANV TENNV …
N2 B …
N4
N5
N6
D
E
G
20
10
10
…
…
…
N5
N6
E
G
…
…
20 TENPB ĐĐ
KT HCM
MANV TENNV …
MAPB TENPB ĐĐ
10
20
KT
KD
HCM
HN
36
Unclustered tablesClustered tables
N1
N3
N4
A
C
D
…
…
…
DL liên 
quan tách 
biệt, tốn 
không gian 
DL liên quan được 
lưu cùng nhau, tiết 
kiệm không gian 
19
Clustering file
• 1 cluster được hình thành từ việc lưu dữ liệu của một vài 
table chung trên một vài block. 
• Cluster key là 1 hoặc nhiều field chung của các table 
tham gia việc gom nhóm Cluster key được chỉ định khi . 
người dùng tạo cluster.
• Các table này thường được dùng chung hoặc kết (join 
operator ZY) để phục vụ cho nhu cầu truy xuất dữ liệu.
• Việc lưu trữ này có ích:
– Giảm thời gian truy xuất đĩa vì số block phải đọc giảm
Giá trị tại field là cluster key chỉ được lưu 1 lần bất kể có bao
37
– , 
nhiêu record ở table khác tham chiếu đến dòng này ⇒ tiết kiệm 
không gian để lưu trữ (và tạo mối quan hệ trên dữ liệu)
• Tổ chức dl theo kiểu cluster không ảnh hưởng gì đến 
việc tạo index trên các table tham gia tạo cluster.
Sử dụng cluster file
• Chỉ định cluster ở giai đọan thiết kế vật lý.
• Chọn các table để gom nhóm:
– Các table chủ yếu phục vụ cho truy vấn (select), ít khi thêm mới 
(insert) hoặc cập nhật (update). 
– Chứa dữ liệu được truy vấn chung hoặc kết với tần suất cao.
• Chọn các field làm cluster key
– Cluster key phải có đủ các giá trị phân biệt để các record liên quan 
đến mỗi giá trị của cluster key lấp gần đầy 1 block dữ liệu.
• Nếu có ít dòng quá sẽ làm tốn không gian lưu trữ mà hiệu quả 
không đáng kể.
38
• Có thể định SIZE khi tạo cluster, là số byte trung bình ước tính 
để có thể lưu 1 cluster
• Nếu có nhiều dòng quá cũng không hiệu quả.
• Dùng cluster key có quá ít giá trị, vd: PHAI, sẽ phản tác dụng.
20
Index (1)
• Dùng chỉ mục cho file giống như việc dùng bản 
liệt kê danh mục (catalog) trong một thư viện.
– Thông tin trên catalog đã được sắp xếp ⇒ tìm kiếm 
nhanh mà không phải duyệt tất cả.
• Về kỹ thuật có 2 lọai index cơ bản: , 
– Index sắp thứ tự (ordered indices) dựa trên các giá trị 
làm index.
• Dùng PP tìm nhị phân trên file index.
• Index là 1 file có thứ tự gồm các mẫu tin có chiều dài cố định gồm 2 field.
– Field 1: khóa tìm kiếm.
– Field 2: con trỏ trỏ đến các block.
– Index dùng kỹ thuật băm (hash indices)
Đá h iá á kỹ th ật dù i d
39
• n g c c u ng n ex
• Lọai truy xuất
• Thời gian truy xuất (access time)
• Thời gian Insert / delete
• Không gian đĩa dùng cho index.
Index (2)
• Dense / Sparse index
– Dense index
• File dữ liệu có bao nhiêu giá trị trên search key thì trên 
file index có bấy nhiêu record
• Mỗi record của file index chứa 1 giá trị là search key và 1 
con trỏ trỏ đến record đầu tiên trên file dữ liệu có cùng 
giá trị trên trường search key.
– Sparse index
Các record trên tập tin index chỉ ứng với một số giá trị
40
• 
trên file dữ liệu trên trường search key (chứ không phải 
tất cả các giá trị của search key như dense index)
• Để tìm 1 giá trị, ta tìm trong tập tin index 1 mẫu tin sao 
cho giá trị search key lớn nhất <= giá trị cần tìm, và duyệt 
record xuất phát từ vị trí đầu tiên mà pointer chỉ đến.
21
Ví dụ
• Dense index
1
5
7
1 … …
5 … …
5 … …
7 … …
• Sparse index
10 7 … …
10 … …
10 … …
1
1 … …
2 … …
3
41
5
7
10
… …
5 … …
6 … …
7 … …
9 … …
10 … …
Index (3)
• File có cách tổ chức riêng và có cách thao tác trên file 
tương ứng.
• Bên cạnh đó, ta cần bổ sung thêm cấu trúc truy cập hỗ trợ 
truy cập nhanh trên file.
• Index là cơ chế giúp HQT CSDL truy xuất dữ liệu nhanh .
• Index key dùng để chỉ 1 hoặc nhiều trường (field) dùng 
làm index.
– Simple Index: index key chỉ có 1 field duy nhất.
– Composite index: index key có nhiều 1 field, nhưng <=16
– Ví dụ:
• NOIGD (…,TENNGD, SONHA, DUONG, QH,TP)
42
– Nhu cầu tìm nhanh 1 địa chỉ giao dịch.
– Nếu index key là DUONG (simple index) thì không hiệu quả 
– Mà phải dùng SONHA, DUONG, QH, TP (composite index), 
và trên các field này, giá trị là duy nhất
22
Index(4)
• Mỗi cấu trúc index kết hợp với 1 index key cụ thể.
• Truy cập đến CSDL dùng index, ta phải sử dụng 1 hoặc một 
số field là index key trong mệnh đề WHERE của câu SQL.
– Nếu là composite index thì nên dùng nhiều hơn 1 field trong 
mệnh đề WHERE, khi đó truy xuất sẽ hiệu quả hơn.
• Cơ bản, bất cứ field nào cũng có thể là index và có thể có 
nhiều index trên cùng 1 file. Vấn đề là index có mang lại hiệu 
quả hay không.
• Index có hiệu quả hay không căn cứ vào:
– Lọai dữ liệu mà trên đó thiết lập index.
– Giá trị trên index key có phân biệt hay không.
– Lọai câu SQL được dùng.
• Khi thi hành 1 câu SQL nếu nhiều hơn 20% các dòng dữ liệu trong
43
1 bảng được truy cập đến thì việc dùng index mới có lợi hơn là 
không dùng index (table scan).
– Các truy cập khác trên bảng, nếu cập nhật nhiều trên field làm 
index sẽ làm chậm hệ thống. 
– Có quá nhiều index sẽ làm chậm hệ thống.
Index (5)
Primary index
Các thuật ngữ:
Single-level 
index
Multi-level 
index
Index
Clustered index
Secondary index
44
23
Primary index
• Được tạo trên field làm khóa sắp xếp cho file dữ liệu. Thứ tự vật lý của các record trên 
đĩa cũng dựa trên field này, và trên đó các record có giá trị duy nhất.
– Nếu có nhiều record có cùng giá trị trên field dùng để sắp xếp, ta sẽ tạo clustering index trên 
field này.
• Có 1 mẫu tin index trong file index ứng với 1 block trong file dữ liệu
• File primary index có kích thước nhỏ hơn rất nhiều so với file dữ liệu.
– Record đầu tiên trong mỗi block của file dữ liệu gọi là anchor record hay block anchor.
Chỉ ó thể ó 1 i i d h ặ 1 l t i i d t ê 1 fil dữ liệ khô thể ó• c c pr mary n ex, o c c us er ng n ex r n e u, ng c 
cả hai loại index này trên cùng 1 file.
An
Bằng
.
TEN PHAI DIACHI NGSINH
An
Ánh
…
Áng
File chỉ mục
File dữ liệu
45
.
.
Vinh
Bằng
Bin
...
Bình
Vinh
Vịnh
…
Xuân
Clustering index
• Nếu dữ liệu trên data file được sắp vật lý theo field không phải là khóa (không 
duy nhất đối với từng mẫu tin) thì field đó là clustering field.
• Clustering index được tạo trên clustering field để tăng tốc độ tìm kiếm các 
mẫu tin có cùng giá trị trên clutering field.
• Có 1 record trên file index chứa 1 giá trị của clustering field, con trỏ trỏ đến 
block đầu tiên chứa giá trị phân biệt.
1
2
3
PHG HOTEN MANV PHAI
1
1
2
2
2
3
3
3
File chỉ mục
File dữ liệu
46
4
5
3
3
4
4
4
5
5
5
24
Secondary Index
• Một secondary index cung cấp thêm phương tiện để truy cập file, 
ngoài primary index ra.
– Được tạo trên field là candidate key và có giá trị duy nhất trên mỗi record, 
dữ liệu của data file không được sắp thứ tự trên field này.
– Cũng có thể tạo trên field không phải là khóa và có giá trị trùng nhau.
– Field 1 là field dữ liệu không được sắp thứ tự của data file, và cần tìm 
kiếm trên đó.
– Field 2 là con trỏ trỏ đến block đầu tiên chứa giá trị, hoặc trỏ đến record 
chứa giá trị.
• Có thể tạo nhiều secondary index cho 1 file dữ liệu.
– TH1: tạo trên field có giá trị duy nhất, field này còn được gọi là secondary 
key. HOTEN SOGP SOXE NGAYCAP
60P1-3445
47
52X1-1234
52X1-2345
53X2-0123
60P1-3445
61P2-3121
63P4-5678
63X5-0908
66X7-1234
66X7-1234
52X1-2345
63P4-5678
53X2-0123
63X5-0908
61P2-3121
52X1-1234
File chỉ mục
File dữ liệu
Secondary index
PHG MANV TENNV PHAI NSINH
3
5
1
6
2
3
4
1
File chỉ mục
File dữ liệu
1
2
3
4
5
6
8
6
8
4
8
6
5
2
5
48
5
1
6
3
6
3
8
3
25
Nhận xét
File dữ liệu sắp 
theo Index field 
File dữ liệu không sắp theo 
index field
Index field làm khóa Primary index Secondary index (Key)
Index field không là khóa Clustering index Secondary index (non key)
•Trong SQL Server, có thể tạo tối đa là 1 primary index và 249 secondary index.
•1 file có thể có nhiều index vì có thể có nhiều nhu cầu tìm kiếm trên file.
49
Multi – level Index
Data 
block 0
D
Index 
block 0
ata 
block 1
50
Index 
block 1
26
Dùng index
• Nên tạo index trên các field có giá trị phân biệt, 
được truy xuất đến với tần suất cao, và kết quả 
câu truy vấn là nhiều dòng dữ liệu.
• Truy vấn trên một miền giá trị dùng các tóan tử 
BETWEEN, >, >=, <, <=.
• Index key là các trường sẽ dùng cho phép kết, 
hoặc trong mệnh đề GROUP BY, ORDER BY.
51
• Không nên tạo clustered index trên các trường 
sẽ thường xuyên cập nhật.
Hết chương 4.
52