Hệ quản trị cơ sở dữ liệu - Chương 3: Lưu trữ và cấu trúc tập tin

ằng số tối đa các con trỏ có 
thể được chứa trong các đối tượng trong một trang. Với một trang kích thước 4096 byte, con trỏ kích thước 4 byte, số 
tối đa các con trỏ là 1024. Trong thực tế số tối đa nhỏ hơn con số này rất nhiều. Định danh trang nhỏ chỉ cần đủ số bit 
để định danh một dòng trong bảng, nếu số dòng tối đa là 1024, chỉ cần 10 bit để định danh trang nhỏ. Bảng dịch cho 
phép toàn bộ một con trỏ bền lấp đầy một không gian bằng không gian cho một con trỏ trong bộ nhớ. 
PageID Off. 
 Trong hình 1, trình bày sơ đồ biểu diễn con trỏ bền, có ba đối tượng trong trang, mỗi một chứa một con trỏ 
bền. Bảng dịch cho ra ánh xạ giữa định danh trang ngắn và định danh trang CSDL đầy đủ đối với mỗi định danh trang 
ngắn trong các con trỏ bền này. Định danh trang CSDL được trình bày dưới dạng volume.file.offset. Thông tin phụ 
được duy trì với mỗi trang sao cho tất cảc các con trỏ bền trong trang có thể tìm thấy. Thông tin được cập nhất khi 
một đối tượng được tạo ra hay bị xoá khỏi trang. Khi một con trỏ trong bộ nhớ được dereferencing, nếu hệ điều hành 
phát hiện trang trong không gian địa chỉ ảo được trỏ tới không được cấp phát lưu trữ hoặc có truy xuất được bảo vệ, 
khi đó một sự vi phạm đoạn được ước đoán là xảy ra. Nhiều hệ điều hành cung cấp một cơ chế xác định một hàm sưe 
được gọi khi vi phạm đoạn xảy ra, một cơ chế cấp phát lưu trữ cho các trang trong không gian địa chỉ ảo, và một tập 
các quyền truy xuất trang. Đầu tiên, ta xét một con trỏ trong bộ nhớ trỏ tới trang v được khử tham chiếu, khi lưu trữ 
chưa được cấp phát cho trang này. Một vi phạm đoạn sẽ xảy ra và kết quả là một lời gọi hàm trên hệ CSDL. Hệ 
CSDL dầu tiên xác định trang CSDL nào đã được cấp phát cho trang bộ nhớ ảo v, gọi định danh trang đầy đủ của 
trang CSDL là P, nếu không có trang CSDL cấp phát cho v, một lỗi được thông báo., nếu không, hệ CSDL cấp phát 
không gian lưu trữ cho trang v và nạp trang CSDL P vào trong v. Pointer swizzling bây giờ được làm đối với trang P 
như sau: Hệ thông tìm tất cả các con trỏ bèn được chứa trong các đối tương trong trang, bằng cách sử dụng thông tin 
phụ được lưu trữ trong trang. Ta xét một con trỏ như vậy và gọi nó là (pi, oi), trong đó pi là định danh trang ngắn và 
 PageID Off. PageID Off. 
2395 255 4867 020 2395 170 
 Object 1 Object 2 Object 3 
Translation Table 
PageID FullPageID 
2395 679.34.28000 
4867 519.56.84000 
Hình 1. ảnh trang trước khi swizzling
PageID Off. PageID Off. PageID Off. 
5001 255 4867 020 5001 170 
 Object 1 Object 2 Object 3 
Translation Table 
PageID FullPageID 
5001 679.34.28000 
4867 519.56.84000 
Hình 2. ảnh trang sau khi swizzling
CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 67
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 
oi là offset trong trang. Giả sử Pi là định danh trang đầy đủ của pi được tìm thấy trong bảng dịch trong trang P. Nếu 
trang Pi chưa có một trang bộ nhớ ảo được cấp cho nó, một trang tự do trong không gian địa chỉ ảo sẽ được cấp cho 
nó. Trang Pi sẽ nằm ở vị trí địa chỉ ảo nàynếu và khi nó được mang vào. Tại điểm này, trang trong không gian địa chỉ 
ảo không có bất kỳ một lưu trữ nào được cấp cho nó, cả trong bộ nhớ lẫn trên đĩa, đơn tuần chỉ là một khoảng địa chỉ 
dự trữ cho trang CSDL. Bây giờ giả sử trang bộ nhớ ảo đã được cấp phát cho Pi là vi . Ta cập nhật con trỏ (pi, oi) bởi 
thay thế pi bởi vi , cuối cùng sau khi swizzling tất cả các con trỏ bền trong P, sự khử tham chiếu gây ra vi phạm đoạn 
được cho phép tiếp tục và sẽ tìm thấy đối tượng đang được tìm kiếm trong bộ nhớ. 
 Trong hình 2, trình bày trạng thái trang trong hình 1 sau khi trang này được mang vào trong bộ nhớ và các 
con trỏ trong nó đã được swizzling. ở đây ta giả thiết trang định danh trang CSDL của nó là 679.34.28000 được ánh 
xạ đến trang 5001 trong bộ nhớ, trong khi trang định danh của nó là 519.56.84000 được ánh xạ dến trang 4867. Tất cả 
các con trỏ trong đối tượng đã được cập nhật để phản ánh tương ứng mới và bây giờ có thể được dùng như con trỏ 
trong bộ nhớ. ở cuối của giai đoạn dịch đói với một trang, các đối tượng trong trang thoả mãn một tính chất quan 
trọng: Tất cả các con trỏ bền được chứa trong đối tượng trong trang được chuyển đổi thành các con trỏ trong bộ nhớ. 
CÂU HỎI VÀ BÀI TẬP CHƯƠNG III 
III.1 Xét sự sắp xếp các khối dữ liệu và các khối parity trên bốn đĩa sau: 
 Trong đó các Bi biểu diễn các khối dữ liệu, các khối Pi biểu diễn các khối parity. Khối Pi 
là khối parity đối với các khối dữ liệu B4i - 3 , B4i - 2 , B4i - 1 , B4i . Hãy nêu các vấn đề gặp phải của 
cách sắp xếp này. 
Đĩa 1 Đĩa 2 Đĩa 3 Đĩa 4 
B B BB3 BB1 B2 B4
P1 B B BB5 B6 B7
BB8 P2 B BB9 B10
... 
... 
... 
... 
III.2 Một sự mất điện xảy ra trong khi một khối đang được viết sẽ dẫn tới kết quả là khối đó có 
thể chỉ được viết một phần. Giả sử rằng khối được viết một phần có thể phát hiện được. Một viết 
khối nguyên tử là hoặc toàn bộ khối được viết hoặc không có gì được viết (không có khối được 
viết một phần). Hãy đề nghị những sơ đồ để có được các viết khối nguyên tử hiệu quả trên các sơ 
đồ RAID: 
1. Mức 1 (mirroring) 
2. Mức 5 (block interleaved, distributed parity) 
CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 68
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 
III.3 Các hệ thống RAID tiêu biểu cho phép thay thế các đĩa hư không cần ngưng truy xuất hệ thống. 
Như vậy dữ liệu trong đĩa bị hư sẽ phải được tái tạo và viết lên đĩa thay thế trong khi hệ thống vẫn tiếp tục 
hoạt động. Với mức RAID nào thời lượng giao thoa giữa việc tái tạo và các truy xuất đĩa còn đang chạy là 
ít nhất ? Giải thích. 
III.4 Xét việc xoá mẩu tin 5 trong file: 
 0 Perryridge A-102 400 
1 Round Hill A-305 350 
8 Perryridge A-218 700 
3 Downtown A-101 500 
4 Redwood A-222 700 
5 Perryridge 
 A-201 900 
6 Brighton A-217 750 
7 Downtown A-110 600 
 So sánh các điều hay/dở tương đối của các kỹ thuật xoá sau: 
1. Di chuyển mẩu tin 6 đến không gian chị chiếm bởi mẩu tin 5, rồi di chuyển 
mẩu tin 7 đến chỗ bị chiếm bởi mẩu tin 6. 
2. Di chuyển mẩu tin 7 đến chỗ bị chiếm bởi mẩu tin 5 
3. Đánh dấu xoá mẩu tin 5. 
III.5 Vẽ cấu trúc của file: 
 header 
0 Perryridge A-102 400 
1 
2 Mianus A-215 700 
3 Downtown A-101 500 
4 
5 Perryridge A-201 900 
6 
7 Downtown A-110 600 
8 Perryridge A-218 700 
Sau mỗi bước sau: 
1. Insert(Brighton, A-323, 1600) 
2. Xoá mẩu tin 2 
3. Insert(Brighton, A-636, 2500) 
CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 69
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 
III.6 Vẽ lại cấu trúc file: 
 0 Perryridge A-102 400 A-201 900 A210 700 ⊥ 
1 Round Hill A-301 350 ⊥ 
2 Mianus 
 Sau mỗi bước sau: 
1. Insert(Mianus, A-101, 2800) 
2. Insert(Brighton, A-323, 1600) 
3. Delete (Perryridge, A-102, 400) 
III.7 Điều gì sẽ xảy ra nếu xen mẩu tin (Perryridge, A-999, 5000) vào file trong III.6. 
III.8 Vẽ lại cấu trúc file dưới đây sau mỗi bước sau: 
1. Insert(Mianus, A-101, 2800 
2. Insert(Brighton, A-323, 1600) 
3. Delete (Perryridge, A-102, 400) 
III.9 Nêu lên một ví dụ, trong đó phương pháp không gian dự trữ để biểu diễn các mẩu tin 
độ dài thay đổi phù hợp hơn phương pháp con trỏ. 
III.10 Nêu lên một ví dụ, trong đó phương pháp con trỏ để biểu diễn các mẩu tin độ dài thay đổi phù hợp 
hơn phương pháp không gian dự trữ. 
III.11 Nếu một khối trở nên rỗng sau khi xoá. Khối này được tái sử dụng vào mục đích gì ? 
A-101 800 ⊥ 
3 Downtown A-211 500 A-222 600 ⊥ 
4 Redwood A-300 650 A-200 1200 A-255 950 ⊥ 
5 Brighton A-111 750 ⊥ 
0 Perryridge A-102 400 
1 A-201 900 
2 A-210 700 • 
3 Round Hill A-301 350 • 
4 Mianus A-101 800 • 
5 Downtown A-211 500 
6 Redwood A-300 650 
7 Brighton A-111 750 • 
8 A-222 600 • 
9 A-200 1200 
10 A-255 950 • 
( • = con trỏ nil ) 
CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 70
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 
III.12 Trong tổ chức file tuần tự, tại sao khối tràn được sử dụng thậm chí, tại thời điểm đang xét, chỉ có 
một mẩu tin tràn ? 
III.13 Liệt kê các ưu điểm và nhược điểm của mỗi một trong các chiến lược lưu trữ CSDL quan hệ sau: 
1. Lưu trữ mỗi quan hệ trong một file 
2. Lưu trữ nhiều quan hệ trong một file 
III.14 Nêu một ví dụ biểu thức đại số quan hệ và một chiến lược xử lý vấn tin trong đó: 
1. MRU phù hợp hơn LRU 
2. LRU phù hợp hơn MRU 
III.15 Khi nào sử dụng chỉ mục đặc phù hợp hơn chỉ mục thưa ? Giải thích. 
III.16 Nêu các điểm khác nhau giữa chỉ mục sơ cấp và chỉ mục thứ cấp . 
III.17 Có thể có hai chỉ mục sơ cấp đối với hai khoá khác nhau trên cùng một quan hệ ? Giải thích. 
III.18 Xây dựng một B+-cây đối với tập các giá trị khoá: (2, 3, 5, 7, 11, 15, 19, 25, 29, 33, 37, 41, 47). 
Giả thiết ban đầu cây là rỗng và các giá trị được xen theo thứ tự tăng. Xét trong các trường hợp sau: 
1. Mỗi nút chứa tối đa 4 con trỏ 
2. Mỗi nút chứa tối đa 6 con trỏ 
3. Mỗi nút chứa tối đa 8 con trỏ 
III.19 Đối với mỗi B+-cây trong bài tập III.18 Bày tỏ các bước thực hiện trong các vấn tin sau: 
1. Tìm mẩu tin với giá trị khoá tìm kiếm 11 
2. Tìm các mẩu tin với giá trị khoá nằm trong khoảng [ 7..19 ] 
III.20 Đối với mỗi B+-cây trong bài tập III.18. Vẽ cây sau mỗi một trong dãy hoạt động sau: 
1. Insert 9 
2. Insert 11 
3. Insert 11 
4. Delete 25 
5. Delete 19 
III.21 Cùng câu hỏi như trong III.18 nhưng đối với B-cây 
III.22 Nêu và giải thích sự khác nhau giữa băm đóng và băm mở. Nêu các ưu, nhược điểm của mỗi kỹ 
thuật này. 
III.23 Điều gì gây ra sự tràn bucket trong một tổ chức file băm ? Làm gì để giảm sự tràn này ? 
III.24 Giả sử ta đang sử dụng băm có thể mở rộng trên một trên một file chứa các mẩu tin với các giá trị 
khoá tìm kiếm sau: 
 2, 3, 5, 7, 11, 17, 19, 23, 37, 31, 35, 41, 49, 55 
 Vẽ cấu trúc băm có thể mở rộng đối với file này nếu hàm băm là h(x) = x mod 8 và mỗi bucket có 
thể chứa nhiều nhất được ba mẩu tin. 
III.25 Vẽ lại cấu trúc băm có thể mở rộng trong bài tập III.24 sau mỗi bước sau: 
1. Xoá 11 
2. Xoá 55 
3. Xen 1 
CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 71
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 
4. Xen 15 
CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 72