Bài giảng Nhập môn cơ sở dữ liệu - Bài 5: Tổ chức dữ liệu vật lý - Vũ Tuyết Trinh
Tổ chức dữ liu vt l
Vũ Tuyết Trinh
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ệ
Ứng dụng
CSDL
Hệ QTCSDL
CSDL
CSDL
ũ Tuyết Trinh, b/m Hệ thống thông tin,
Bộ xử lý
câu hỏi
Bộ quản lý
Giao dịch
Bộ quản lý
lưu trữ
Quản lý lưu trữ
{ Tổ chức tệp: sắp xếp các
bản ghi trên thiết bị nhớ
ngoài
Bộ quản lý lưu trữ
Quản lý buffer
Quản
lý
giao
dịch
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ị
của trường (khoá)
Quản lý tệp
{ 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ố)
Metadata &
Data dictionary
Data & index
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)
ũ Tuyết Trinh, b/m Hệ thống thông tin,
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ỳ
{ ăừ
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
ũ Tuyết Trinh, b/m Hệ thống thông tin,
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ông tuân theo mộứ ự đặệt 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.
ũ Tuyết Trinh, b/m Hệ thống thông tin,
Cài đặt tệp đống bằng danh sách
Data
Data
Data
Full Pages
Page
Page
Page
Header
Page
Data
Data
Data
Pages with
Free Space
Page
Page
Page
{ 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
ũ Tuyết Trinh, b/m Hệ thống thông tin,
Sử dụng trang danh bạ
Data
Header
Page
Data
Page 2
Data
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
{ ựảăhash table
z Hàm băm (hash function)
z Cụm (bucket)
ũ Tuyết Trinh, b/m Hệ thống thông tin,
Ví dụ
1
2
4
3
Store
hash
1
4
2
3
Ví dụ tiếp
h(x) = x mod 4
Store
hash
10
12
6
1
1
2
3
4
2
3
4
10
12
6
ũ Tuyết Trinh, b/m Hệ thống thông tin,
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
ũ Tuyết Trinh, b/m Hệ thống thông tin,
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
ũ Tuyết Trinh, b/m Hệ thống thông tin,
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.
ũ Tuyết Trinh, b/m Hệ thống thông tin,
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.
ũ Tuyết Trinh, b/m Hệ thống thông tin,
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
ũ Tuyết Trinh, b/m Hệ thống thông tin,
Kết luận
{ Truy cập đến CSDL thường liên quan đến một
ầỏ ảộệữ ệ
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
ũ Tuyết Trinh, b/m Hệ thống thông tin,
Bạn đang xem tài liệu "Bài giảng Nhập môn cơ sở dữ liệu - Bài 5: Tổ chức dữ liệu vật lý - Vũ Tuyết Trinh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_nhap_mon_co_so_du_lieu_bai_5_to_chuc_du_lieu_vat_l.pdf