Cơ sở dữ liệu - Tổ chức dữ liệu vật lý

Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Hệ thống thông tin, 
Khoa CNTT, ĐHBKHN 1
Tổ chức dữ liệu vật lý
Vũ Tuyết Trinh
trinhvt@it-hut.edu.vn
Bộ môn Các hệ thống thông tin, Khoa Công nghệ thông tin
Đại học Bách Khoa Hà Nội
Hệ QTCSDL
Ứng dụng
Hệ
CSDL
CSDL CSDL
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Hệ thống thông tin, 
Khoa CNTT, ĐHBKHN 2
Quản lý lưu trữ
{ Tổ chức tệp: sắp xếp các 
ế
Bộ xử lý
câu hỏi Bộ quản lý
Giao dịch
Bộ quản lý
lưu trữ
bản ghi trên thi t bị nhớ 
ngoài
z RID (record id): xác định địa 
chỉ vật lý của các bản ghi 
z chỉ số: cấu trúc dữ liệu xác 
định sự tương ứng giữa 
RID của bản ghi và giá trị
Quản lý buffer
Quản lý tệp
Quản
lý
giao 
dịch
Bộ quản lý lưu trữ
của trường (khoá)
{ Vùng nhớ đệm: trung gian 
giữa thiết bị nhớ ngoài và 
bộ nhớ trong (có thể sử 
dụng cho cả DL và chỉ số)
Data & indexMetadata &
Data dictionary
Tổ chức bộ nhớ ngoài
{ Mục đích: giảm thiểu truy xuất đến dữ liệu 
ầ ế ếkhông c n thi t trên thi t bị nhớ ngoài
{ Các vấn đề cần quan tâm
z Cấu trúc lưu trữ
z Các phép toán (thêm, xoá, sửa, tìm kiếm)
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Hệ thống thông tin, 
Khoa CNTT, ĐHBKHN 3
Các thiết bị nhớ ngoài
{ Đĩa từ, băng từ, trống từ, ...
{ Đĩa từ: được tổ chức thành từng trang 
z Chí phí truy nhập đến các trang bất kỳ là tương 
đương
z Chí phí đọc nhiều trang liền nhau < chí phí đọc các 
trang đó theo thứ tự bất kỳ
{ Băng từ: 
z chỉ có thể đọc được các trang liền nhau
z rẻ hơn đĩa từ nhưng chi phí truy nhập thương lớn hơn
{ ...
Đĩa từ vs. bộ nhớ trong
{ Tốc độ truy nhập bộ 
ms vs. ns (~1000 lần)
{ Kích thước 
GB vs. 10x MB (~ 100 lần với cùng chi phí)
{ Lưu trữ 
ổn định (kể cả khi mất điện) vs. tạm thời
{ Phân chia block
4KB vs. 1Byte
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Hệ thống thông tin, 
Khoa CNTT, ĐHBKHN 4
Nội dung
9 Tổng quan về tổ chức bộ nhớ ngoài
{ Tổ chức tệp đống
{ Tổ chức tệp băm
{ Tổ chức tệp chỉ dẫn
{ Cây cân bằng
Tổ chức tệp đống (Heap File)
{ Lưu trữ kế tiếp các bản ghi trong các trang 
khô t â th ột thứ t đặ biệt àng u n eo m ự c n o 
{ Để thực hiện các phép toán, cần:
z Ghi nhớ số trang trong 1 tệp
z Ghi nhớ không gian trống trên các trang
z Ghi nhớ các bản ghi trên các trang
¾ Có các con trỏ trỏ tới tất cả các trang của tệp và 
các con trỏ này được lưu trữ ở bộ nhớ trong.
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Hệ thống thông tin, 
Khoa CNTT, ĐHBKHN 5
Cài đặt tệp đống bằng danh sách
Header
Page
Data
Page
Data
Page
Data
Page
Data
Page
Data
Page
Data
Page Pages withFree Space
Full Pages
{ Cần lưu trữ HeaderPage và tên của tệp
{ Mỗi trang gồm dữ liệu và 2 con trỏ
Các phép toán
{ Tìm kiếm 1 bản ghi
{ Thêm 1 bản ghi
{ Xoá 1 bản ghi
{ Sửa đổi một bản ghi
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Hệ thống thông tin, 
Khoa CNTT, ĐHBKHN 6
Sử dụng trang danh bạ
Data
Page 1Header
Data
Page 2
Data
Page N
Page
DIRECTORY
{ Lưu thông tin về số byte còn trống trên trang đó
{ Danh bạ là 1 tập các trang
Tổ chức tệp băm (Hash File)
{ Mục đích
z Sử dụng chỉ số để hạn chế số lượng phép truy xuất 
đĩa bằng các phân nhóm các bản ghi (giả thiết n 
nhóm)
z Mapping giá trị khoá với vị trí của (nhóm) bản ghi 
tương ứng 
D t ê bả bă (h h t bl ){ ựa r n ng m as a e
z Hàm băm (hash function)
z Cụm (bucket)
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Hệ thống thông tin, 
Khoa CNTT, ĐHBKHN 7
Ví dụ
h(x) = x mod 4
1
2
4
3
Store hash
1 2 3 4
1 2 3 4
Ví dụ tiếp
h(x) = x mod 4
10
12
6
Store hash
1 2 3 4
1 2 3 4
10 12
6
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Hệ thống thông tin, 
Khoa CNTT, ĐHBKHN 8
Các phép toán
{ Tìm kiếm 1 bản ghi
{ Thêm 1 bản ghi
{ Xoá 1 bản ghi
{ Sửa đổi một bản ghi
Tiêu chí chọn hàm băm
{ Phân bố các bản ghi tương đối đồng đều (theo 
các cụm)
{ Hạn chế việc sử dụng nhiều trang bộ nhớ cho 1 
cụm
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Hệ thống thông tin, 
Khoa CNTT, ĐHBKHN 9
Tổ chức tệp chỉ dẫn (Index File)
{ Tệp chỉ dẫn theo khoá được chọn trong bản ghi
{ Tệp chỉ dẫn bao gồm các cặp (k,d), trong đó k 
là giá trị của khoá của bản ghi đầu tiên, d là địa 
chỉ của khối (hay con trỏ khối). 
{ Tệp chỉ dẫn được sắp xếp theo giá trị của khoá.
Các phép toán
{ Tìm kiếm 1 bản ghi
{ Thêm 1 bản ghi
{ Xoá 1 bản ghi
{ Sửa đổi một bản ghi
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Hệ thống thông tin, 
Khoa CNTT, ĐHBKHN 10
Tìm kiếm 1 bản ghi 
{ Tìm kiếm tuần tự
ẫ ầ ế ấz Duyệt tệp chỉ d n từ bản ghi đ u tiên đ n khi tìm th y 
bản ghi có khoá k cần tìm
z Nhận xét
{ chậm đối với các tệp chỉ dẫn nói chung. 
{ Thích hợp với các tệp chỉ dẫn nhỏ đủ để lưu ở bộ 
nhớ trong
{ Tìm kiếm nhị phân
z Chia đôi tệp chỉ dẫn đã sắp xếp để hạn chế số bản 
ghi cần duyệt
z Tại mỗi lần chia hạn chế được ½ số bản ghi cần xem 
xét
Cây cân bằng (BalanceTree)
{ B-tree cân bằng được tổ chức theo cấp m, có 
ấcác tính ch t sau đây:
z Gốc của cây hoặc là một nút lá hoặc ít nhất có hai 
con.
z Mỗi nút (trừ nút gốc và nút lá) có từ [m/2] đến m con.
z Mỗi đường đi từ nút gốc đến bất kỳ nút lá nào đều có 
độ dài như nhau.
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Hệ thống thông tin, 
Khoa CNTT, ĐHBKHN 11
Ví dụ
Nhận xét
{ Cấu trúc của mỗi nút trong B-tree 
(p0, kl, p1, k2,...,kn, pn) 
z pi (i=l..n) là con trỏ trỏ tới khối i của nút có ki là khoá 
đầu tiên của khối đó. 
z Các khoá k trong một nút được sắp xếp theo thứ tự
tăng dần.
{ Mọi khoá trong cây con, trỏ bởi pi đều nhỏ hơn 
ki+1
{ Mọi khoá trong cây con, trỏ bởi pn đều lớn hơn 
kn.
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Hệ thống thông tin, 
Khoa CNTT, ĐHBKHN 12
Các phép toán
{ Tìm kiếm 1 bản ghi
{ Thêm 1 bản ghi
{ Xoá 1 bản ghi
{ Sửa đổi một bản ghi
So sánh các cách tổ chức dữ liệu
{ Tệp đống
{ Tệp băm
{ Tệp chỉ dẫn
{ Cây cân bằng
Nhập môn cơ sở dữ liệu
Vũ Tuyết Trinh, b/m Hệ thống thông tin, 
Khoa CNTT, ĐHBKHN 13
Kết luận
{ Truy cập đến CSDL thường liên quan đến một 
phần nhỏ các bản ghi trong một tệp dữ liệu hay 
một vài trường (đặc biệt là các trường khoá) 
của các bản ghi dữ liệu.
¾ Xác định các yêu cầu này cho phép thiết kế dữ liệu 
vật lý hiệu quả thông qua việc sử dụng các tổ chức 
lưu trữ đặc biệt
{ Tệp chỉ dẫn được tạo lập trên khoá tìm kiếm để 
tăng hiệu quả của lưu trữ dữ liệu
¾ Hiệu quả của các cấu trúc chỉ dẫn khác nhau phụ 
thuộc vào điều kiện áp dụng chúng