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 - Lê Thị Minh Nguyện

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 Downtown1 A-101 500
Redwood1 A-222 700 Perryridge1 A-201 900
Brighton1 A-217 750 Downtown1 A-110 600
Perryridge1 A-218 700 0
0 0
0 411 1011 3233 40
8/25/2017
6
3.1. Mẫu tin có chiều dài cố định(tt)
Hệ quản trị Cơ sở dữ liệu 21
• 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
FH
Perryridge1 A-102 400 1 A-305 Round Hill 350
Mianus0 A-215 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
800A-111 Redwood
3.1. Mẫu tin có chiều dài cố định(tt)
Hệ quản trị Cơ sở dữ liệu 22
• 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
3.2. Mẫu tin có chiều dài động
Hệ quản trị Cơ sở dữ liệu 23
• Trong DBMS, mẫu tin có chiều dài động
• Lưu trữ nhiều loại mẫu tin trong 1 tập tin
• Các loại mẫu tin chứa các trường có chiều dài động
• Có 2 cách biểu diễn
• Byte-String
• Fixed-Length
• Ví dụ:
type account-list = record
branch-name: char(22);
account-info: array [1..n] of
record
account-number: char(10);
balance: real;
end
end
3.2. Mẫu tin có chiều dài động (tt)
Hệ quản trị Cơ sở dữ liệu 24
• 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
8/25/2017
7
3.2. Mẫu tin có chiều dài động (tt)
Hệ quản trị Cơ sở dữ liệu 25
• 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
• 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
3.2. Mẫu tin có chiều dài động (tt)
Hệ quản trị Cơ sở dữ liệu 26
Byte-String Representation
Tốn nhiều chi phí khi chiều dài mẫu tin thay đổi
A-202 950-
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
3.2. Mẫu tin có chiều dài động (tt)
Hệ quản trị Cơ sở dữ liệu 27
• 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
• Point
3.2. Mẫu tin có chiều dài động (tt)
Hệ quản trị Cơ sở dữ liệu 28
• Fixed-Length Representation
• 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
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
8/25/2017
8
3.2. Mẫu tin có chiều dài động (tt)
Hệ quản trị Cơ sở dữ liệu 29
• 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
• Anchor block – Chứa mẫu tin 
đầu tiên của mảng account-
info
• 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
4. Sắp xếp các mẫu tin vào block
Hệ quản trị Cơ sở dữ liệu 30
Kích thước 
cố định
Giả sử chỉ có 1 filea file
blocks
records
5. Tổ chức mẫu tin trên tập tin 
Hệ quản trị Cơ sở dữ liệu 31
• 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
5.1. Tuần tự (Sequential)
Hệ quản trị Cơ sở dữ liệu 32
• 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
8/25/2017
9
5.1. Tuần tự (Sequential) (tt)
Hệ quản trị Cơ sở dữ liệu 33
• 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
5.1. Tuần tự (Sequential) (tt)
Hệ quản trị Cơ sở dữ liệu 34
• 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
5.1. Tuần tự (Sequential) (tt)
Hệ quản trị Cơ sở dữ liệu 35
• 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
5.2. Clustering
Hệ quản trị Cơ sở dữ liệu 36
• 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
from depositor, customer
where depositor.customer-name=customer.customer-name
8/25/2017
10
5.2. Clustering (tt)
Hệ quản trị Cơ sở dữ liệu 37
• 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
Chỉ mục
Hệ quản trị Cơ sở dữ liệu 38
• 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
Chỉ mục (tt)
Hệ quản trị Cơ sở dữ liệu 39
• 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
Chỉ mục (tt)
Hệ quản trị Cơ sở dữ liệu 40
• 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
8/25/2017
11
Chỉ mục (tt)
Hệ quản trị Cơ sở dữ liệu 41
• 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
Chỉ mục (tt)
• Cú pháp:
CREATE INDEX ON (,,) 
• Ví dụ: 
CREATE INDEX ON MonHoc(TenMH)
Hệ quản trị Cơ sở dữ liệu 42
Chỉ mục (tt)
Hệ quản trị Cơ sở dữ liệu 43
• Nhận xét
• Tìm kiếm nhanh trong trường hợp so sánh
với hằng số và phép kết
• Làm chậm đi các thao tác thêm, xóa và
sửa
• Tốn chi phí
• Lưu trữ chỉ mục
• Truy xuất đĩa nhiều
• Chọn lựa cài đặt chỉ mục hợp lý???
Hệ quản trị Cơ sở dữ liệu 44