Ch ơng 7
Các cấu trúc dữ liệu ở bộ nhớ ngoài
Chơng này giành để trình bày mô hình tổ chức dữ liệu ở bộ nhớ ngoài,
các cấu trúc dữ liệu để lu giữ và tìm kiếm thông tin ở bộ nhớ ngoài : file băm,
file có chỉ số, B cây. Với mỗi phơng pháp tổ chức file, chúng ta sẽ trình bày
các thuật toán để thực hiện các phép toán tìm kiếm, xen vào, loại bỏ và sửa đổi
trên file.
7.1. Mô hình tổ chức dữ liệu ở bộ nhớ ngoài :
Các cấu trúc dữ liệu (CTDL) mà chúng ta xét từ đầu tới nay đều là các
CTDL đợc lu giữ trong bộ nhớ chính. Nhng trong nhiều áp dụng, số các dữ liệu
cần đợc lu giữ vợt quá khả năng của bộ nhớ chính. Các máy tính hiện nay đều
đợc trang bị các thiết bị bộ nhớ ngoài, thông thờng là đĩa. Nó có khả năng lu
giữ một khối lợng rất lớn các dữ liệu. Tuy nhiên các thiết bị nhớ ngoài có
những đặc trng truy cập hoàn toàn khác bộ nhớ chính. Sau đây chúng ta sẽ
trình bày mô hình tổng quát mà các hệ điều hành hiện đại sử dụng để quản lý
dữ liệu ở bộ nhớ ngoài. Trong các mục sau chúng ta sẽ xét các CTDL để lu giữ
file sao cho các phép toán trên file đợc thực hiện một cách hiệu quả. Đó là file
băm, file có chỉ số, B - cây.
Các hệ điều hành hiện đại đều cho chúng ta khả năng tổ chức dữ liệu ở
bộ nhớ ngoài dới dạng các file.
Chúng ta có thể quan niệm file nh là một tập hợp nào đó các dữ liệu (các
bản ghi) đợc lu giữ ở bộ nhớ ngoài. Các bản ghi trong file có thể có độ dài cố
định (số các trờng của bản ghi là cố định) hoặc có thể có độ dài thay đổi. Các
file với các bản ghi có độ dài cố định đợc sử dụng nhiều trong các hệ quản trị
cơ sở dữ liệu. Các file với các bản ghi có độ dài thay đổi hay đợc sử dụng để lu
giữ các thông tin văn bản. Chúng ta sẽ chỉ xét các file với các bản ghi có độ
dài cố định. Các kỹ thuật mà chúng ta sẽ trình bày để lu giữ và thao tác với các
file này có thể sửa đổi để áp dụng cho các file với các bản ghi có độ dài thay
đổi.
Trong chơng này chúng ta sẽ hiểu khoá của bản ghi là một tập hợp nào
đó các trờng của bản ghi hoàn toàn xác định bản ghi, tức là hai bản ghi khác

File có thể đợc lu giữ trong một danh sách liên kết các khối. Điển hình
hơn, file có thể đợc lu giữ trong các khối tổ chức dới dạng cây. Các khối không
là lá của cây chứa các con trỏ tới một số khối trong cây.
Trong mỗi khối có thể giành ra một số byte (phần này đợc gọi là đầu
khối) để chứa các thông tin cần thiết về khối, chẳng hạn để ghi số bản ghi
trong khối.
Trong một khối, không gian để lu trữ một bản ghi đợc gọi là khối con.
Cần phần biệt khối con đầy và rỗng. Khối con đầy là khối con có chứa bản
ghi, ngợc lại là khối con rỗng. Để chỉ một khối con là đầy hoặc rỗng, trong
đầu khối ta giành cho mỗi khối con một bit (gọi là bit đầy), bit nhận giá trị 1
(0) nếu khối con tơng ứng là đầy (rỗng). Một cách khác, trong mỗi khối con ta
giành ra một bit (bit xoá), bit nhận giá trị 1 có nghĩa là bản ghi đã bị xoá.
Đánh giá thời gian thực hiện các phép toán trên file
Các phép toán trên file (tìm kiếm, xen vào, loại bỏ, sửa đổi) đợc thực
hiện thông qua phép toán cơ bản, đọc một khối dữ liệu ở bộ nhớ ngoài vào
vùng đệm trong bộ nhớ chính hoặc viết các dữ liệu ở vùng đệm trong bộ nhớ
chính vào một khối ở bộ nhớ ngoài. Ta gọi phép toán này là phép toán truy cập
khối (block access). Cần chú ý rằng, việc chuyển một khối dữ liệu ở bộ nhớ
ngoài vào bộ nhớ chính đòi hỏi nhiều thời gian hơn việc tìm kiếm đữ liệu trong
173
9 21 15 6 41
khối khi nó đã ở trong bộ nhớ chính. Cũng cần biết rằng , các dữ liệu cần phải
có ở bộ nhớ chính trớc khi nó đợc sử dụng bằng cách nào đó. Vì vậy khi đánh
giá thời gian thực hiện một thuật toán thao tác với các dữ liệu đợc lu giữ trong
file, chúng ta phải tính số lần cần thiết phải thực hiện phép toán truy cập khối.
Số lần thực hiện phép toán truy cập khối đợc dùng để biểu diễn tính hiệu quả
của các thuật toán trên các file.
Tổ chức file đơn giản
Phơng pháp đơn giản nhất, đồng thời cũng kém hiệu quả nhất để lu giữ
các bản ghi của file là, xếp các bản ghi của file vào một số khối cần thiết theo

174
9 21 15 6 41
0
i
K-1
Hình 7.1 Cấu trúc file băm
Việc phân phối các bản ghi của file vào các lớp đợc thực hiện bởi hàm
băm h. Đó là hàm xác định trên tập các giá trị khoá của các bản ghi và nhận
các giá trị nguyên từ 0 đến K-1. Nếu x là một giá trị khoá và h(x) = i, 0 i
K-1, thì bản ghi với khoá x thuộc lớp thứ i.
Để tìm kiếm bản ghi với khoá x cho trớc, đầu tiên ta tính h(x), con trỏ
chứa ở thành phần thứ i = h(x) trong bảng chỉ dẫn ta tìm đến các khối của lớp
i. lần lợt đọc các khối, ta sẽ tìm ra bản ghi với khoá x, hoặc đọc hết các khối
mà không thấy có nghĩa là bản ghi không có ở trong file.
Muốn xen vào file bản ghi với khoá x, ta cần kiểm tra xem nó có ở trong
file hay cha. Nếu cha ta có thể xen nó vào khối đầu tiên trong danh sách các
khối của h (x), nếu tại đó còn đủ chỗ cho bản ghi. Nếu tất cả các khối của lớp
h(x) đều đầy, ta thêm vào danh sách các khối của lớp h(x) một khối mới và đặt
bản ghi vào đó.
Để loại bỏ bản ghi với khoá x, trớc hết ta cần xác định vị trí của bản ghi
trong file bằng cách áp dụng thủ tục tìm kiếm. Sau đó có thể xoá bỏ bản ghi
này bằng cách, chẳng hạn cho bit xoá nhận giá trị 1.
Cấu trúc file băm là cấu trúc rất có hiệu quả nếu các phép toán trên file
chỉ đòi hỏi đến việc truy cập các bản ghi theo khoá. Giả sử file có n bản ghi,
nếu hàm băm đợc thiết kế tốt, thì trung bình mỗi lớp chứa n/k bản ghi. Giả sử
mỗi khối chứa đợc m bản ghi. Nh vậy mỗi lớp gồm khoảng n/mk khối. Tức là
các phép toán trên file băm sẽ k lần nhanh hơn so với tổ chức file tuần tự.
7.3. File có chỉ số ( indexed file)
Cấu trúc file băm đợc tạo ra dựa trên khoá của bản ghi. Trong mục này
chúng ta trình bày một phơng pháp tổ chức file khác cũng dựa vào khoá của

1
) sao cho v
1
là giá trị khoá lớn nhất trong file chỉ số
thoả mãn điều kiện v
1
v. Ta sẽ nói v
1
phủ v.
Việc tìm kiếm trên file chỉ số một giá trị khoá v
1
phủ giá trị khoá v cho
trớc có thể thực hiện bằng cách tìm kiếm tuần tự hoặc tìm kiếm nhị phân.
Trong tìm kiếm tuần tự, ta cần xem xét tất cả các bản ghi của file chỉ số
cho tới khi tìm thấy một chỉ số (v
1
, b
1
) với v
1
phủ v. Nếu v nhỏ hơn giá trị khoá
của bản ghi đầu tiên trong file chỉ số thì điều đó có nghĩa là trong file chỉ số
không chứa giá trị khoá phủ v.
Phơng pháp có hiệu quả hơn là tìm kiếm nhị phân. Giả sử các bản ghi
của file chỉ số đợc sắp xếp vào các khối đợc đánh số từ 1 đến m. Xét khối thứ
m/2. Giả sử (v
2
, b
2
) là bản ghi đầu tiên trong khối. So sánh giá trị khoá cho