Bài giảng Hệ quản trị cơ sở dữ liệu - Chương V: Cấu trúc lưu trữ và phương pháp truy xuất

Chương V. Cấu trúc lưu trữ
và phương pháp truy xuất
1
Nội dung
Giới thiệu
Đĩa (magnetic disk)
Mẫu tin (record)
 Sắp xếp các mẫu tin vào block
Tổ chức mẫu tin trên tập tin
2
Giới thiệu (tt)
Phân cấp lưu trữ
Bộ nhớ chính
Dữ liệu hiện hành
Đĩa
CSDL chính thức
Băng từ (tape) hay đĩa quang (optical disk)
Phiên bản cũ của CSDL
3
Đĩa (Disk)
4
5
Quản lý đĩa
6
 Một mặt đĩa chia thành nhiều track, 1 track chia thành nhiều 
block(page). 1 cluster = n block.
 Dùng đĩa từ (magnetic disk) để lưu CSDL vì:
 Khối lương lưu trữ lớn.
 Lưu một cách bền bỉ, lâu dài, phục vị truy cập và xử lý lặp lại.
 Chi phí rẻ.
 Dữ liệu trên đĩa phải được chép vào bộ nhớ chính khi cần xử lý. 
Nếu dữ liệu này có thay đổi thì sẽ được ghi trở lại vào đĩa.
 Bộ điều khiển đĩa(Disk controller - DC): giao tiếp giữa ổ đĩa và 
máy tính, nhận lệnh I/O, định vị đầu đọc và làm cho hành động 
R/W diễn ra.
 Block cũng là đơn vị để lưu trữ và chuyển dữ liệu.
Lưu tập tin trên đĩa
7
Mục đích
8
Mẩu tin
9
Tập tin
10
Tập tin (tt)
11
Tập tin (tt)
12
Lưu mẩu tin vào block
13
Tổ chức file block trên đĩa
14
Thao tác trên file
15
Mẫu tin có chiều dài cố định
 Xét 1 tập tin gồm các mẫu tin account 
 Giả sử
 1 char : 1 byte
 Real : 8 bytes
 1 mẫu tin account : 40 bytes
 40 bytes đầu tiên là mẫu tin thứ 1
 40 bytes tiếp theo là mẫu tin thứ 2
type deposit = record
account-number: char(10);
branch-name: char(22);
balance: real;
end
16
Mẫu tin có chiều dài cố định (tt)
 Record header
 Lược đồ của mẫu tin
Chiều dài của mẫu tin
 Thời gian sau cùng cập nhật mẫu tin
 Không nhất thiết để các thông tin này ở record header
 Block header
Con trỏ nối các block có liên quan với nhau
 Thông tin về mối quan hệ giữa các mẫu tin trong block
 Block ID
 Thời gian sau cùng truy xuất block
17
Mẫu tin có chiều dài cố định (tt)
 Ví dụ
Mỗi mẫu tin có thêm 1 bit
 =0: Xóa
 =1: Đang dùng
Danh sách các mẫu tin trống (free list)
Perryridg
e
1 A-102 400 1 A-305 Round 
Hill
350
Mianus1 A-215 700 Downtow
n
1 A-101 500
Redwood1 A-222 700 Perryridg
e
1 A-201 900
Brighton1 A-217 750 Downtow
n
1 A-110 600
Perryridg
e
1 A-218 700 0
0 0
0 411 10 11 32 33 40
18
Mẫu tin có chiều dài cố định (tt)
 Hủy mẫu tin
Đánh dấu xóa vào bit thông tin 
Đưa mẫu tin bị đánh dấu xóa vào free list
F
H Perryridg
e
1 A-102 400 1 A-305 Round 
Hill
350
Mianus0 A-215 700 Downtow
n
1 A-101 500
Redwood1 A-222 700 Perryridg
e
1 A-201 900
Brighton0 A-217 750 Downtow
n
1 A-110 600
Perryridg
e
1 A-218 700 0
0 0
800A-111 Redwood
19
Mẫu tin có chiều dài cố định (tt)
 Thêm một mẫu tin
 Hoặc thêm vào những mẫu tin bị đánh dấu xóa hoặc thêm vào cuối 
tập tin
 Cập nhật lại free list
 Tìm kiếm
 Quét tuần tự trên tập tin
FH
Perryridge1 A-102 400 1 A-305 Round Hill 350
Downtown1 A-111 700 Downtown1 A-101 500
Redwood1 A-222 700 Perryridge1 A-201 900
Brighton0 A-217 750 Downtown1 A-110 600
Perryridge1 A-218 700 0
0 0
20
Mẫu tin có chiều dài động
 Byte-String Representation
Cuối mỗi mẫu tin có 1 byte ký tự đặc biệt cho biết kết thúc 
mẫu tin
Perryridge -A-102 400
-
A-305Round Hill 350
Mianus
-
A-215 700
Downtown A-101 500
Redwood
-
A-222 700
A-201 900
Brighton
-
A-217 750
A-110 600
-
A-218 700
21
Mẫu tin có chiều dài động (tt)
 Byte-String Representation
 Sử dụng lại không gian trống sau khi xóa 1 mẫu tin không 
hiệu quả
Dẫn đến tình trạng phân mãnh 
Perryridge -A-102 400
-
A-305Round Hill 350
Mianus
-
A-215 700
Downtown A-101 500
Redwood
-
A-222 700
A-201 900
Brighton
-
A-217 750
A-110 600
-
A-218 700
22
Mẫu tin có chiều dài động (tt)
A-202 950
 Byte-String Representation
Tốn nhiều chi phí khi chiều dài mẫu tin thay đổi
-
Perryridge -A-102 400
A-305Round Hill 350
A-201 900 A-218 700
Brighton A-217 750 -
-
Mianus A-215 700
Downtown A-101 500
Redwood
-
A-222 700 -
A-110 600
23
Mẫu tin có chiều dài động (tt)
 Fixed-Length Representation
 Sử dụng 1 hay nhiều mẫu tin có chiều dài cố định biểu diễn 
cho những mẫu tin có chiều dài động
Có 2 kỹ thuật
 Reserved space
 Sử dùng độ dài lớn nhất của 1 mẫu tin nào đó cài đặt cho tất cả
các mẫu tin còn lại
 Độ dài này phải đảm bảo không bao giờ dài thêm được nữa
Perryridg
e
A-102 400
A-305Round 
Hill
350
Mianus A-215 700
Downtow
n
A-101 500
Redwood A-222 700
A-201 900
Brighton A-217 750
A-110 600
A-218 700
24
Mẫu tin có chiều dài động (tt)
 Fixed-Length Representation
 Pointer
 Các mẫu tin có chiều dài động 
móc xích với nhau thông qua 
danh sách các mẫu tin có chiều 
dài cố định
 Có 2 loại blocks trong tập tin
o Anchor block – Chứa mẫu tin 
đầu tiên của mảng account-
info
o Overflow block – Chứa các 
mẫu tin tiếp theo của mảng 
account-info
Perryridge A-102 400
A-305Round Hill 350
Mianus A-215 700
Downtown A-101 500
Redwood A-222 700
Brighton A-217 750
A-201 900
A-110 600
A-218 700
Anchor block
Overflow block
25
Tổ chức mẫu tin trên tập tin 
 Cho 1 tập các mẫu tin 
Tổ chức các mẫu tin trên tập tin như thế nào?
 Sequential
Clustering
 Indexing
Hashing
 B-Tree
26
Tuần tự (Sequential)
 Các mẫu tin được tổ chức lưu trữ tuần tự theo 1 thứ tự nào 
đó, thông thường theo trường khóa tìm kiếm (search-key)
 Khóa tìm kiếm không nhất thiết là khóa chính hay siêu khóa
 Mỗi mẫu tin có 1 con trỏ trỏ
đến mẫu tin khác theo thứ tự
khóa tìm kiếm
27
Tuần tự (tt)
 Xóa mẫu tin
 Sử dụng danh sách các con trỏ trỏ đến vùng trống 
 Thêm mẫu tin
 Tìm vị trí thích hợp trên tập tin
 Nếu có vị trí trống trong cùng 1
block thì thêm vào
 Ngược lại sẽ thêm vào vùng
overflow block
 Cập nhật lại con trỏ theo đúng thứ
tự của khóa tìm kiếm
28
Tuần tự (tt)
 Nhận xét
Giảm tối thiểu khối lượng block cần đọc khi truy 
xuất tập tin
 Tốn nhiều chi phí di chuyển các mẫu tin sau khi thêm 
hoặc xóa 1 mẫu tin
 Phải tổ chức lại tập tin theo thứ tự khóa tìm kiếm sau mỗi 
lần thêm hoặc xóa
29
Clustering
 Xét 2 quan hệ depositor và customer
 Thực hiện câu truy vấn
 Nếu các bộ của quan hệ depositor và customer nằm gần nhau 
trong tập tin thì câu truy vấn sẽ được thực hiện 1 cách hiệu 
quả
Khi 1 bộ của customer được đọc thì nguyên cả khối chứa bộ
này cũng được đưa vào bộ nhớ chính
 Lúc đó các bộ của depositor có liên quan đến customer đã có 
sẳn và được xử lý ngay
select account-number, customer-name, customer-street, customer-city
from depositor, customer
where depositor.customer-name=customer.customer-name
30
Clustering (tt)
 Tổ chức clustering lưu trữ các mẫu tin tương ứng của 2 hay 
nhiều quan hệ trong cùng 1 block
 Nhận xét
 Có hiệu quả khi truy vấn có phép
kết
 Chưa thật sự tốt nếu truy vấn trên
1 quan hệ
 Một block có nhiều loại mẫu tin
31
Chỉ mục (Indexing)
 Chỉ mục được dùng để truy xuất dữ liệu nhanh hơn
 Một tập tin dữ liệu sẽ có 1 hoặc nhiều tập tin chỉ mục kèm 
theo
 Tập tin chỉ mục gồm
 Tập tin chỉ mục sẽ nhỏ hơn rất nhiều so với tập tin dữ liệu ban 
đầu
 Tập tin chỉ mục được sắp xếp thứ tự theo khóa tìm kiếm
pointersearch-key
32
Chỉ mục (tt)
 Nếu 1 tập tin chứa các mẫu tin đã được sắp thứ tự
Chỉ mục sơ cấp (Primary index)
 Là chỉ mục có khóa tìm kiếm định nghĩa ra thứ tự sắp xếp 
các mẫu tin của tập tin gốc
 Còn được gọi là clustering index
Chỉ mục thứ cấp (Secondary index)
 Là chỉ mục có khóa tìm kiếm đưa ra 1 thứ tự sắp xếp khác với 
thứ tự tuần tự của tập tin gốc
 Còn được gọi là nonclustering index
33
Chỉ mục (tt)
 Chỉ mục dày (Dense index)
 Tập tin gốc có bao nhiêu mẫu tin thì tập tin chỉ mục có bấy 
nhiêu
34
Chỉ mục (tt)
 Chỉ mục thưa (Sparse index)
 Tập tin chỉ mục chỉ lưu lại 1 số khóa của tập tin gốc
 Để xác định vị trí của 1 khóa k
 Tìm trong tập tin chỉ mục khóa lớn nhất nhưng vẫn bé hơn k
 Tìm trong tập tin gốc bắt đầu từ địa chỉ vừa xác định trong tập tin chỉ mục
35
Băm (hashing)
 Chia các mẫu tin trong tập tin thành từng 
vùng (bucket) tùy theo giá trị khóa của mẫu 
tin
Mẫu tin thuộc về vùng nào tùy thuộc vào hàm 
băm được áp dụng trên mẫu tin đó
 Sử dụng hàm băm để xác định vị trí của mẫu tin
 Các mẫu tin có khóa khác nhau có thể được 
băm vào cùng 1 vùng, vì vậy cần phải tìm 
tuần tự trên vùng để định vị mẫu tin
36
Băm (tt)
 Xét 1 tập tin gồm các mẫu tin account có trường branch-name là 
khóa
 Giả sử
 10 vùng
 Thứ tự thứ i của các ký tự trong bảng chữ cái là các số
nguyên i 
Hàm băm sum(các ký tự) modulo 10
 h(Perryridge) = 5
 h(Round Hill) = 3
 h(Brighton) = 3
37
38
Băm (tt)
 Các vùng có thể xãy ra hiện tượng tràn khi
 Không đủ kích thước
 Phân phối mẫu tin vào các vùng không cân xứng
 Có nhiều mẫu tin trùng giá trị khóa
 Hàm băm cho ra kết quả băm không tốt
 Vấn đề tràn vùng được giải
quyết bằng cách sử dụng
thêm các vùng tràn (overflow
buckets)
39
Cây cân bằng (B-Tree)
 B-Tree là 1 cây có gốc thỏa điều kiện
 Tất cả các đường đi từ nút gốc đến đến nút là đều bằng 
nhau
Ngoại trừ nút gốc, mỗi nút có từ n/2 đến n cây con
 n là bậc của cây
Nút lá có từ (n-1)/2 đến n-1 khóa
 Cấu trúc 1 nút 
 Khóa tìm kiếm trên 1 nút được sắp thứ tự tăng dần
K1 < K2 < K3 < . . . < Kn–1
40
Cây cân bằng (tt)
41