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

8/25/2017
1
Chương 2.
Cấu trúc lưu trữ và phương
pháp truy xuất
GV: Lê Thị Minh Nguyện
Email: nguyenltm@huflit.edu.vn
Nội dung
1. Tổ chức dữ liệu
2. Các bộ phận của tổ chức tổ chức dữ liệu
3. Mẫu tin (record)
4. Sắp xếp các mẫu tin vào block
5. Tổ chức mẫu tin trên tập tin
6. Tổ chức băm
7. Tổ chức B cây
8. Chỉ mục (index)
Hệ quản trị Cơ sở dữ liệu 2
1. Tổ chức dữ liệu
1.1. Khái niệm
1.2. Sự cần thiết của tổ chức dữ liệu
1.3. Các thuận lợi và khó khăn khi tổ chức dữ liệu
1.4. Các giải pháp tổ chức dữ liệu
Hệ quản trị Cơ sở dữ liệu 3
1.1. Khái niệm
• Tổ chức dữ liệu là tiến trình phân tích và cấu trúc lại dữ
liệu (đôi khi chỉ là các giá trị dữ liệu, phức tạp hơn là cơ
sở dữ liệu) của hệ thống
• Kết quả của việc tổ chức dữ liệu là có được hệ thống
tổ chức và quản lý dữ liệu tốt hơn, có thể có một cơ sở
dữ liệu chuẩn với các mô hình dữ liệu được cài đặt
Hệ quản trị Cơ sở dữ liệu 4
8/25/2017
2
1.1. Khái niệm (tt)
• Các hoạt động khi tổ chức dữ liệu thường gặp:
• Tổ chức dưới dạng tập tin đơn giản trong hệ thống
• Tổ chức thành cơ sở dữ liệu được quản lý bởi DBMS
• Chuyển hệ thống dùng một DBMS này sang hệ thống dùng một
DBMS khác
• Chuyển đổi dữ liệu toàn cục dùng chung cho toàn bộ hệ thống
thành các đối tượng hay các dạng dữ liệu với cấu trúc trừu tượng
Hệ quản trị Cơ sở dữ liệu 5
1.2. Sự cần thiết của tổ chức dữ liệu
Hệ quản trị Cơ sở dữ liệu 6
1.2. Sự cần thiết của tổ chức dữ liệu (tt)
• Đối với các hệ thống cũ, những khó khan bao gồm:
• Những người tham gia tổ chức dữ liệu không còn làm việc
trong công ty.
• Một số hệ thống hoạt động trên máy tính lớn, dữ liệu lưu trữ ở
một nơi, khó khan cho việc khai thác phân bố ở nhiều nơi
khác nhau.
• Một số hệ thống sử dụng các cơ sở dữ liệu cũ hay các tập tin
đã lỗi thời có sự gia tang lớn về sự trùng lắp dữ liệu.
Hệ quản trị Cơ sở dữ liệu 7
1.3. Các thuận lợi và khó khăn khi tổ chức dữ liệu
• Thuận lợi
• Tăng tính hiệu quả khi khai thác dữ liệu
• Giảm thiểu rủi ro trong tương lai
• Tận dụng các tri thức đã tích lũy trong hệ thống cũ,
• Khó khăn
• Vấn đề chi phí
• Đối với các hệ thống cũ, nếu thay đổi cách tiếp cận khi phân
tích, thiết kế nhằm phục vụ cho việc tổ chức dữ liệu thì gần
như xây dựng lại từ đầu
• Đào tạo nhân sự tiếp cận công nghệ mới,
Hệ quản trị Cơ sở dữ liệu 8
8/25/2017
3
1.4. Các giải pháp tổ chức dữ liệu
• Tổ chức Dữ liệu theo tập tin
• Tổ chức dữ liệu theo cơ sở dữ liệu
• Nêu ứng dụng, ưu và khuyết điểm của 2 loại tổ
chức dữ liệu?????
Hệ quản trị Cơ sở dữ liệu 9
2. Các bộ phận của tổ chức tổ chức dữ liệu
2.1. Bộ phận quản lý tập tin (File Manager)
2.2. Bộ phận quản lý đĩa (magnetic disk)
2.3. Tổ chức vật lý Tổ chức vật lý
Hệ quản trị Cơ sở dữ liệu 10
Bộ phận quản lý tập tin (File Manager)
• Lưu trữ thông tin trên đĩa từ dưới dạng các file. Các file
sẽ có con trỏ xác định điểm vào các sector đầu tiên
chứa thông tin. Các file được quản lý dưới dạng cây gọi
là cây thư mục
11
2.1. Bộ phận quản lý đĩa (magnetic disk)
Hệ quản trị Cơ sở dữ liệu 12
Memory
Registers
CPU
I/O Devices
I/O BusMemory Bus
C
A
C
H
E
Size Speed
Virtural 
Memory File 
System
Disk
Second 
storage
Tertiary storage
8/25/2017
4
2.1. Bộ phận quản lý đĩa (magnetic disk) (tt) 
Hệ quản trị Cơ sở dữ liệu 13
• Dung lượng lớn
• Dữ liệu không bị mất khi hệ thống mất điện
hay gặp sự cố (non-volatile)
• Tốc độ truy xuất
• Thời gian định vị track (seek time): ? ms
• Thời gian định vị sector (rotational delay): ? ms
• Thời gian chuyển dữ liệu (transfer time): ? kb 
• Truy xuất dữ liệu
• Đọc trực tiếp dữ liệu ở 1 vị trí bất kỳ trên đĩa
• Theo đơn vị lưu trữ - block hay page
2.1. Bộ phận quản lý đĩa (magnetic disk) (tt) 
• Làm sao bố trí dữ liệu trên đĩa?????
Hệ quản trị Cơ sở dữ liệu 14
• Muốn lưu trữ dữ liệu
• Mã tài khoản
• Tên chi nhánh
• Số dư
• Ngày rút tiền
• Dữ liệu được biểu diễn bằng chuỗi các bytes
8
bits
2.3. Tổ chức vật lý
• Hai cách tổ chức lưu trữ dữ liệu cơ bản của hệ thống là lưu trữ
ở dạng văn bản (text) và nhị phân (binary).
• Thường tổ chức ở dạng nhị phân
Hệ quản trị Cơ sở dữ liệu 15
Tổ chức trên SQL Server
Hệ quản trị Cơ sở dữ liệu 16
8/25/2017
5
Tổ chức trên Oralce
Hệ quản trị Cơ sở dữ liệu 17
3. Mẫu tin (record)
Hệ quản trị Cơ sở dữ liệu 18
• Tập hợp các dữ liệu có liên quan với nhau tạo thành một mẫu
tin
• Ví dụ
• Mẫu tin account có những thông tin
• Account-number
• Branch-name
• Balance
• Có 2 loại mẫu tin
• Mẫu tin có chiều dài cố định (Fixed-Length Record)
• Mẫu tin có chiều dài động (Variable-Length Record)
3.1. Mẫu tin có chiều dài cố định
Hệ quản trị Cơ sở dữ liệu 19
type deposit = record
account-number: char(10);
branch-name: char(22);
balance: real;
end
3.1. Mẫu tin có chiều dài cố định(tt)
Hệ quản trị Cơ sở dữ liệu 20
• Ví dụ
• Mỗi mẫu tin có thêm 1 bit (tương tự .dbf)
• =0: Xóa
• =1: Đang dùng
• Danh sách các mẫu tin trống (free list)
Perryridge1 A-102 400 1 A-305 Round Hill 350
Mianus1 A-215 700 Down