Bài giảng Cơ sở dữ liệu nâng cao - ĐH Hàng Hải

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:60

Thêm vào BST

Báo xấu

287
lượt xem 72
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

"Bài giảng Cơ sở dữ liệu nâng cao" trình bày các nội dung lưu trữ và tổ chức tệp tin, lập chỉ mục và băm, tối ưu hóa truy vấn, giao dịch trong cơ sở dữ liệu, điều khiển đồng thời và khôi phục hệ thống. Mời bạn đọc tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cơ sở dữ liệu nâng cao - ĐH Hàng Hải

TRƢỜNG ĐẠI HỌC HÀNG HẢI KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN HỆ THỐNG THÔNG TIN -----***----- BÀI GIẢNG CƠ SỞ DỮ LIỆU NÂNG CAO TÊN HỌC PHẦN : CƠ SỞ DỮ LIỆU NÂNG CAO MÃ HỌC PHẦN : 17406 TRÌNH ĐỘ ĐÀO TẠO : ĐẠI HỌC CHÍNH QUY DÙNG CHO SV NGÀNH: CÔNG NGHỆ THÔNG TIN HẢI PHÕNG – 2011
2 MỤC LỤC CHƢƠNG 1: LƢU TRỮ VÀ TỔ CHỨC TỆP TIN 6 1.1. Tổng quan về phƣơng tiện lƣu trữ 6 1.2. Tổ chức tệp tin 7 1.2.1. Bản ghi với độ dài cố định (Fixed – Length Records) 7 1.2.2. Bản ghi với độ dài thay đổi (Variable – Length Records) 9 1.3. Tổ chức các bản ghi trong tệp tin 11 1.3.1. Tổ chức tệp tin Heap 11 1.3.2. Tổ chức tệp tin tuần tự 11 1.3.3. Tổ chức tệp tin băm 12 1.4. Câu hỏi ôn tập chƣơng 1 14 CHƢƠNG 2: LẬP CHỈ MỤC VÀ BĂM 15 2.1. Các khái niệm cơ bản 15 2.2. Các chỉ mục có thứ tự 15 2.2.1. Chỉ mục chính (Primary Indexes) 15 2.2.2. Chỉ mục cụm (Clustering Indexes) 17 2.2.3. Chỉ mục phụ (Secondary Indexes) 17 2.3. Chỉ mục cây B+ 19 2.3.1. Tóm lược về cây tìm kiếm 19 2.3.2. Chỉ mục B – Tree 20 2.3.3. Chỉ mục B+ – Tree 21 2.4. Băm tĩnh và băm động 23 2.4.1. Băm tĩnh (Static Hashing) 23 2.4.2. Băm động (Dynamic Hashing) 24 2.5. Câu hỏi ôn tập chƣơng 2 26 CHƢƠNG 3: TỐI ƢU HÓA TRUY VẤN 28 3.1. Giới thiệu 28 3.2. Các phép biến đổi tƣơng đƣơng 28 3.3. Thuật toán tối ƣu hóa cây đại số quan hệ 30 3.3.1. Thuật toán 30 3.3.2. Ví dụ 30 3.4. Câu hỏi ôn tập chƣơng 3 32 CHƢƠNG 4: GIAO DỊCH TRONG CƠ SỞ DỮ LIỆU 33 4.1. Giới thiệu 33
3 4.2. Các tính chất và trạng thái của giao dịch 33 4.2.1. Tính chất của giao dịch 33 4.2.2. Trạng thái của giao dịch 33 4.3. Lịch biểu 34 4.3.1. Khái niệm lịch biểu 34 4.3.2. Tính khả tuần tự của lịch biểu 35 4.4. Thuật toán kiểm tra tính khả tuần tự của lịch biểu 35 4.5. Câu hỏi ôn tập chƣơng 4 37 CHƢƠNG 5: ĐIỀU KHIỂN ĐỒNG THỜI VÀ KHÔI PHỤC HỆ THỐNG 38 5.1. Các giao thức dựa vào khóa 38 5.1.1. Mô hình khóa nhị phân 38 5.1.2. Mô hình khóa đọc – ghi (chia sẻ – độc quyền) 38 5.1.3. Giao thức khóa 2 pha 40 5.1.4. Deadlock 41 5.2. Giao thức thứ tự nhãn thời gian (Timestamp – Ordering protocol) 43 5.2.1. Nhãn thời gian (Timestamp) 43 5.2.2. Giao thức thứ tự nhãn thời gian (Timestamp – Ordering Protocol) 43 5.3. Phục hồi hệ thống dựa vào nhật ký giao dịch (Log-based) 44 5.3.1. Cập nhật trì hoãn cơ sở dữ liệu (Deferred Database Modification) 44 5.3.2. Cập nhật tức thời (Immediate Database Modification) 45 5.4. Kỹ thuật phân trang bóng (Shadow Paging) 46 5.5. Câu hỏi ôn tập chƣơng 5 49 MỘT SỐ ĐỀ THI MẪU 50
4 Tên học phần: Cơ sở dữ liệu nâng cao Loại học phần: 2 Bộ môn phụ trách giảng dạy: Hệ thống Thông tin Khoa phụ trách: CNTT. Mã học phần: 17406 Tổng số TC: 2 Tổng số tiết Lý thuyết Thực hành/Xemina Tự học Bài tập lớn Đồ án môn học 45 30 15 0 không không Học phần học trƣớc: Cơ sở dữ liệu. Học phần tiên quyết: Cơ sở dữ liệu. Học phần song song: Không yêu cầu. Mục tiêu của học phần: Cung cấp cho sinh viên những kiến thức nâng cao về cơ sở dữ liệu quan hệ. Nội dung chủ yếu: Các vấn đề nâng cao về cơ sở dữ liệu quan hệ: Lưu trữ và tổ chức tệp tin; Lập chỉ mục và băm; Tối ưu hóa truy vấn; Quản lý giao dịch trong cơ sở dữ liệu; Điều khiển tương tranh; Phục hồi hệ thống. Nội dung chi tiết: PHÂN PHỐI SỐ TIẾT TÊN CHƢƠNG MỤC TS LT TH BT KT Chƣơng 1: Lƣu trữ và tổ chức tệp tin 2 2 1.1. Tổng quan về phương tiện lưu trữ 1.2. Tổ chức tệp tin 1.3. Tổ chức các bản ghi trong tệp tin Chƣơng 2: Lập chỉ mục và băm 12 6 5 1 2.1. Các khái niệm cơ bản 2.2. Các chỉ mục có thứ tự 2.3. Chỉ mục cây B+ 2.4. Băm tĩnh 2.5. Băm động Chƣơng 3: Tối ƣu hóa truy vấn 7 6 1 3.1. Giới thiệu 3.2. Các phép biến đổi tương đương 3.4. Thuật toán tối ưu hóa cây đại số quan hệ Chƣơng 4: Giao dịch trong cơ sở dữ liệu (Transactions) 12 6 5 1 4.1. Giới thiệu 4.2. Các tính chất của giao dịch
5 PHÂN PHỐI SỐ TIẾT TÊN CHƢƠNG MỤC TS LT TH BT KT 4.3. Các trạng thái của giao dịch 4.4. Lịch biểu (Schedule) 4.5. Tính khả tuần tự của lịch biểu (Serializability) 4.6. Thuật toán kiểm tra tính khả tuần tự của lịch biểu Chƣơng 5: Điều khiển đồng thời và khôi phục hệ thống 12 7 5 5.1. Các giao thức dựa vào khóa (Lock-based) 5.2. Giao thức thứ tự nhãn thời gian 5.3. Phục hồi hệ thống dựa vào nhật ký giao dịch (Log-based) 5.4. Kỹ thuật phân trang bóng (Shadow Paging) Nhiệm vụ của sinh viên: Tham dự các buổi học lý thuyết và thực hành, làm các bài tập được giao, làm các bài thi giữa học phần và bài thi kết thúc học phần theo đúng quy định. Tài liệu học tập: 1. Avi Silberschatz, Henry F. Korth, S. Sudarshan, Database System Concepts, 6th ed, McGraw-Hill. Hình thức và tiêu chuẩn đánh giá sinh viên: Hình thức thi: tự luận hoặc trắc nghiệm. Tiêu chuẩn đánh giá sinh viên: căn cứ vào sự tham gia học tập của sinh viên trong các buổi học lý thuyết và thực hành, kết quả làm các bài tập được giao, kết quả của các bài thi giữa học phần và bài thi kết thúc học phần. Thang điểm: Thang điểm chữ A, B, C, D, F. Điểm đánh giá học phần: Z = 0,3X + 0,7Y. Bài giảng này là tài liệu chính thức và thống nhất của Bộ môn Hệ thống Thông tin, Khoa Công nghệ Thông tin và được dùng để giảng dạy cho sinh viên. Ngày phê duyệt: __/__/____ Trƣởng Bộ môn Ngƣời biên soạn
6 CHƢƠNG 1: LƢU TRỮ VÀ TỔ CHỨC TỆP TIN 1.1.Tổng quan về phƣơng tiện lƣu trữ Có một vài kiểu lưu trữ dữ liệu tồn tại trong hầu hết các hệ thống máy tính. Các thiết bị lưu trữ này được phân loại theo tốc độ truy cập dữ liệu, giá trên một đơn vị dữ liệu và độ tin cậy của thiết bị: Cache: Là thiết bị lưu trữ nhanh nhất và cũng có giá đắt nhất. Bộ nhớ cache tương đối nhỏ, được quản lý bởi phần cứng của hệ thống máy tính. Main Memory: Dung lượng có thể lên tới vài Gigabytes trên máy tính cá nhân và hàng trăm Gigabytes trên các máy Server. Tuy nhiên vẫn là quá nhỏ để lưu toàn bộ cơ sở dữ liệu. Dữ liệu lưu trữ trên Main Memory sẽ mất khi mất nguồn hay lỗi hệ thống. Flash Memory: Khác với Main Memory, dữ liệu lưu trên thiết bị lưu trữ loại này vẫn còn ngay cả khi mất nguồn hay lỗi hệ thống. Flash Memory có giá thấp hơn Main Memory, thường sử dụng rộng rãi để lưu trữ dữ liệu trên các thiết bị như camera, máy nghe nhạc, điện thoại, USB, ... Magnetic – disk storage: Là phương tiện chủ yếu lưu trữ dữ liệu lâu dài, thường toàn bộ cơ sở dữ liệu được lưu trữ trên đĩa từ. Để xử lý dữ liệu trên đĩa từ, dữ liệu phải được chuyển sang bộ nhớ chính (Main Memory). Hiện nay, dung lượng của đĩa từ có thể từ vài chục Gigabytes đến hàng Terabyte. Optical storage: Các đĩa CD (Compact Disk) với dung lượng khoảng 700 Megabytes là dạng phổ biến nhất của các thiết bị lưu trữ loại này. Và khoảng 4.7 đến 8.5 Gigabytes với đĩa DVD (Digital Video Disk). Đĩa hai mặt có dung lượng lên tới 17 Gigabytes. Tape storage: Là thiết bị chủ yếu dùng để sao lưu dữ liệu. Thiết bị lưu trữ loại này có giá rẻ hơn đĩa từ nhưng tốc độ truy xuất chậm do phải đọc tuần tự. Khả năng lưu trữ của băng từ là rất lớn (40 – 300 Gigabytes). Các thiết bị lưu trữ được tổ chức như hình sau phân cấp theo tốc độ và giá cả: Ở mức cao là các thiết bị lưu trữ có khả năng truy xuất nhanh hơn nhưng có giá đắt hơn.
7 Hình 1.1: Phân cấp các thiết bị lưu trữ 1.2. Tổ chức tệp tin 1.2.1. Bản ghi với độ dài cố định (Fixed – Length Records) Xem xét các bản ghi trong file instructor, mỗi bản ghi được định nghĩa như sau: Giả sử mỗi ký tự chiếm một byte và kiểu numeric(8, 2) chiếm 8 bytes như vậy một bản ghi instructor sẽ có độ dài là 53 byte. Một cách tiếp cận đơn giản để lưu trữ các bản ghi này là dùng 53 byte đầu tiên lưu bản ghi đầu tiên, 53 byte tiếp theo cho bản ghi thứ hai, ... Hình 1.2: File chứa các bản ghi Instructor Tuy nhiên với các tiếp cận này sẽ có hai vấn đề nảy sinh: Nếu kích thước của một khối không chia hết cho 53 thì một số bản ghi sẽ vượt quá một khối đĩa, nghĩa là một bản ghi có thể nằm trong hai khối đĩa. Như vậy có thể phải truy xuất tới hai khối đĩa để đọc hay ghi một bản ghi.
8 Khó khăn khi xóa một bản ghi với cấu trúc lưu trữ kiểu này. Khoảng trống bị chiếm bởi bản ghi đã xóa hoặc là phải được lấp đầy bởi bản ghi khác hoặc là phải được đánh dấu xóa. Để giải quyết vấn đề đầu tiên, chúng ta chỉ lưu mỗi bản ghi trong một khối. Phần khoảng trống dư lại ở cuối khối sẽ bị bỏ quả. Với vấn đề thứ hai, khi một bản ghi bị xóa và để lại khoảng trống trên khối đĩa, ta có thể giải quyết bằng một số cách như sau: Dịch chuyển các bản ghi sau bản ghi bị xóa về trước: Hình 1.3: File Instructor trong hình 1.2 sau khi đã xóa bản ghi thứ 3 và dịch chuyển các bản ghi sau về trước Với cách tiếp cận này thì khoảng không gian còn trống luôn ở cuối khối, tuy nhiên nhược điểm của nó là phải dịch chuyển một lượng lớn bản ghi để thực hiện thao tác xóa. Một cách tiếp cận đơn giản hơn là di chuyển bản ghi cuối cùng: Hình 1.4: File Instructor trong hình 1.2 sau khi đã xóa bản ghi thứ 3 và dịch chuyển bản ghi cuối cùng Sử dụng phương pháp đánh dấu các bản ghi bị xóa: Thực tế ta không mong muốn phải di chuyển các bản ghi khi thực hiện thao tác xóa, hơn nữa những thao tác thêm một bản ghi được thực hiện thường xuyên hơn những thao tác xóa. Do vậy, một cách tiếp cận hợp lý hơn là đánh dấu vị trí các bản ghi bị xóa và chờ thao tác thêm bản ghi tiếp theo sẽ sử dụng lại khoảng không gian bị trống đó.
9 Một phương pháp đơn giản để đánh dấu các bản ghi bị xóa là sử dụng một số byte ở phần đầu của tệp tin (ta gọi là file header) để lưu địa chỉ của bản ghi đầu tiên bị xóa, rồi sử dụng bản ghi đầu tiên bị xóa để lưu địa chỉ của bản ghi thứ hai bị xóa, ... Như vậy ta sẽ có một danh sách các bản ghi được đánh dấu xóa. Hình 1.5: File Instructor trong hình 1.2 với các bản ghi 1, 4, 6 đã đánh dấu xóa Khi thêm mới một bản ghi, ta sử dụng con trỏ đầu danh sách được chứa trong file header để xác định danh sách, nếu danh sách không rỗng ta xen bản ghi mới vào nơi được trỏ bởi con trỏ đầu danh sách nếu không ta xen bản ghi mới vào cuối file. Ta thấy rằng với cấu trúc bản ghi có độ dài cố định việc cài đặt các thao tác thêm hay xóa bản ghi là đơn giản do khoảng không gian để lại bởi bản ghi bị xóa cũng vừa bằng khoảng không gian cần thiết cho bản ghi thêm vào. Nhưng nếu cho phép bản ghi có độ dài thay đổi thì vấn đề trở nên phức tạp hơn nhiều. 1.2.2. Bản ghi với độ dài thay đổi (Variable – Length Records) Lưu trữ nhiều kiểu bản ghi trong một tệp tin. Các kiểu bản ghi với độ dài thay đổi trên một hay nhiều thuộc tính. Các kiểu bản ghi cho phép các trường được lặp lại, như mảng hay tập hợp. Biểu diễn một bản ghi với các thuộc tính có độ dài thay đổi thường gồm hai phần. Phần đầu chứa các thuộc tính có độ dài cố định và phần sau là các thuộc tính với độ dài thay đổi. Các thuộc tính với độ dài cố định như các giá trị số, ngày tháng, hoặc các xâu với độ dài cố định. Các thuộc tính với độ dài thay đổi như các thuộc tính kiểu varchar được biểu diễn với một cặp (offset, length), trong đó offset cho biết vị trí bắt đầu của dữ liệu và length là độ dài (số byte) dữ liệu. Ví dụ với một bản ghi instructor thì các thuộc tính: ID, name và dept_name là các xâu với độ dài thay đổi, và thuộc tính salary là kiểu số với độ dài cố định. Giả sử mỗi giá trị offset và length được lưu trữ trong hai byte và kiểu số được lưu trong 8 byte:
10 Hình 1.6: Biểu diễn bản ghi có độ dài thay đổi Với các thuộc tính trong bản ghi có giá trị null, ta sử dụng cấu trúc null bitmap để đánh dấu các giá trị null. Với bản ghi instructor có bốn thuộc tính: ID, name, dept_name và salary, nếu thuộc tính salary nhận giá trị null thì bít thứ tư của bitmap được gán là 1 và giá trị trong các byte từ 12 đến 19 bị bỏ qua. Do bản ghi instructor chỉ có bốn thuộc tính nên chỉ cần một byte để lưu thông tin về null bitmap. Trong một số cách biểu diễn, null bitmap được lưu trử ở phần đầu của bản ghi. Cách biểu diễn này rất hữu dụng khi số lượng thuộc tính trong một bản ghi, và số lướng thuộc tính null là lớn. Trên đây đã trình bày vấn đề tổ chức các thuộc tính có độ dài thay đổi trong một bản ghi. Sau đây ta xem xét vấn đề lưu các bản ghi độ dài thay đổi trong một khối. Cấu trúc slotted – page thường được sử dụng để lưu trữ các bản ghi với độ dài thay đổi trong khối đĩa: Hình 1.7: Cấu trúc Slotted – page Phần đầu mỗi khối (Block Header) chứa thông tin về: Số lượng bản ghi. Phần cuối khoảng không gian trống trong khối. Mảng chứa vị trí và kích thước mỗi bản ghi. Các bản ghi được lưu trữ liên tiếp trong khối và bắt đầu từ cuối khối. Khoảng khôi gian trống trong khối là liên tiếp nhau và nằm giữa mục cuối cùng trong mảng header và và bản ghi đầu tiên. Khi một bản ghi được thêm vào khối, nó sẽ được lưu ở phần cuối cùng trong không gian trống của khối, sau đó một mục chứa vị trí và kích thước của bản ghi đó sẽ được thêm vào phần Block Header. Nếu một bản ghi bị xóa, khoảng không gian chứa nó sẽ được giải phóng và mục thông tin về bản ghi đó trong phần Block Header sẽ được xóa (ví dụ kích thước được gán bằng -1). Sau đó các
11 bản ghi trước bản ghi bị xóa sẽ được dịch chuyển về cuối để đảm bảo phần không gian trống trong khối luôn nằm giữa Block Header và bản ghi đầu tiên. SQL hỗ trợ các kiểu blob và clob cho các trường hợp mà kích thước dữ liệu cần lưu trữ lớn hơn kích thước của khối đĩa như: ảnh, các tệp tin audio, video, ... Các kiểu này lưu trữ các đối tượng nhị phân và các chuỗi ký tự lớn. Các đối tượng này sẽ được lưu trữ trong các tệp tin đặc biệt và sử dụng cấu trúc cây B+ sẽ được trình bày trong chương sau. 1.3. Tổ chức các bản ghi trong tệp tin Ở phần trước ta đã xem xét làm thế nào để biểu diễn các mẩu tin trong một cấu trúc file. Một quan hệ là một tập các bản ghi. Với một tập các bản ghi, vấn đề là làm sao để tổ chức chúng trong một file. Có một vài cách tổ chức các bản ghi trong file như sau: Tổ chức tệp tin Heap: Một bản ghi được lưu ở bất kỳ đâu trong file. Không có thứ tự của các bản ghi. Thông thường một file lưu một quan hệ. Tổ chức tệp tin tuần tự: Các bản ghi được tổ chức tuần tự theo giá trị của một khóa tìm kiếm (search key) trong mỗi bản ghi. Tổ chức tệp tin băm: Sử dụng một hàm băm tính toán trên một số thuộc tính của bản ghi và dùng kết quả để đó để xác định khối đĩa mà bản ghi được lưu trữ. 1.3.1. Tổ chức tệp tin Heap Là kiểu tổ chức file đơn giản nhất, các bản ghi không được sắp xếp thứ tự. Việc thêm mới một bản ghi là đơn giản: Tìm khối đĩa cuối cùng của file, sao chép khối đĩa vào bộ đệm, thêm mới bản ghi rồi ghi lại vào đĩa. Địa chỉ của khối đĩa cuối cùng được cập nhật lại vào file header. Do các bản ghi trong file không được sắp xếp theo thứ tự nên khi tìm kiếm phải sử dụng phương pháp tìm kiếm tuần tự: Đọc lần lượt từng khối đĩa vào bộ nhớ chính rồi tiến hành tìm kiếm các bản ghi. Như vậy nếu file gồm b khối đĩa thì thời gian tìm kiếm trung bình sẽ là n/2. 1.3.2. Tổ chức tệp tin tuần tự Tổ chức file tuần tự được thiết kế để xử lý hiệu quả các bản ghi theo thứ tự được sắp dựa trên một khoá tìm kiếm nào đó. Một khóa tìm kiếm là một hay một nhóm thuộc tính bất kỳ, không nhất thiết phải là khóa chính hay siêu khóa. Ta sử dụng kỹ thuật con trỏ để truy xuất nhanh chóng tới bản ghi theo thứ tự khoá tìm kiếm. Con trỏ trong mỗi bản ghi sẽ trỏ tới bản ghi tiếp theo trong thứ tự khoá tìm kiếm. Hình 1.8 cho thấy tổ chức file tuần tự của các bản ghi instructor với khóa tìm kiếm là thuộc tính ID. Tổ chức file tuần tự cho phép đọc các bản ghi theo thứ tự được sắp thuận lợi cho mục đích hiển thị cũng như cho các thuật toán xử lý truy vấn (query – processing algorithms). Tuy vậy, kho khăn gặp phải khi tổ chức file tuần tự là việc duy trì thứ tự vật lý của các bản ghi trong file khi xảy ra các thao tác thêm, xóa bản ghi. Ta có thể quản lý thao tác xóa nhờ việc sử dụng kỹ thuật con trỏ như đã trình bày ở phần trên. Với phép chèn một bản ghi, ta áp dụng các quy tắc sau:
12 Xác định vị trí bản ghi trước bản ghi được thêm vào theo thứ tự của khóa tìm kiếm. Nếu có bản ghi trống (để lại do phép xóa) trong cùng khối với bản ghi vừa xác định thì đặt bản ghi mới vào không gian trống đó, nếu không chèn bản ghi mới vào khối tràn (overflow block). Sau đó điều chỉnh lại con trỏ của các bản ghi liên quan cho đúng với thứ tự của khóa tìm kiếm. Hình 1.9 chỉ ra file trong hình 10.10 sau khi chèn thêm bản ghi (32222, Verdi, Music, 48000). Hình 1.8: File tuần tự chứa các bản ghi Instructor Hình 1.9: File tuần tự sau khi thêm bản ghi vào khối tràn 1.3.3. Tổ chức tệp tin băm Phương pháp tổ chức file dạng này cho phép truy cập nhanh tới bản ghi cần tìm. Điều kiện tìm kiếm phải là điều kiện bằng trên một thuộc tính, gọi là thuộc tính băm (hash attribute, hash field) của file. Thông thường thuộc tính đem băm cũng là khóa. Ý tưởng của phương pháp này là sử
13 dụng một hàm h nhận giá trị đầu vào là giá trị băm và cho ra kết quả là địa chỉ của khối đĩa chứa bản ghi cần tìm. Ưu điểm của phương pháp tổ chức file dạng này là cho phép thực hiện các thao tác nhanh, tuy vậy việc xây dựng hàm băm là khó khăn vì phải đảm bảo dễ tính toán và phân phối đều các bản ghi.
14 1.4. Câu hỏi ôn tập chƣơng 1 1.4.1. Trình bày tổng quan về các phương tiện lưu trữ 1.4.2. Trình bày các phương pháp tổ chức tệp tin cơ sở dữ liệu 1.4.3. Trình bày các phương pháp tổ chức bản ghi trong tệp tin 1.4.4. Chỉ ra cấu trúc của file trong hình 1.5 sau mỗi thao tác dưới đây: Thêm bản ghi (24556, Turnamian, Finance, 98000) Xóa bản ghi 2 Thêm bản ghi (34556, Thompson, Music, 67000) 1.4.5. Xét bản ghi trong file Employee (ID, Name, Dept_ID, Age, Address) trong đó: ID, Dept_ID là kiểu numberic (8, 2) độ dài cố định, lưu trong 8 byte Name là kiểu varchar(30) độ dài thay đổi lưu, mỗi ký tự, lưu trong 1 byte Age là kiểu số tinyint độ dài cố định, lưu trong 1 byte Address là kiểu varchar (50) độ dài thay đổi, mỗi ký tự lưu trong 1 byte Hãy biểu diễn bản ghi sau trong cấu trúc bản ghi với độ dài thay đổi: 1002, Nimzowitsch, 102, 60, Russian 1105, Lindan, 111, NULL, China
15 CHƢƠNG 2: LẬP CHỈ MỤC VÀ BĂM 2.1. Các khái niệm cơ bản Ở chương trước ta đã tìm hiểu về cách thức tổ chức các bản ghi trong file. Mỗi phương pháp đều có những ưu, nhược điểm nhất định. Chương này sẽ trình bày một số kỹ thuật lập chỉ mục cho phép truy cập hiệu quả tới bản ghi cần tìm dựa vào một giá trị tìm kiếm. Có nhiều kỹ thuật lập chỉ mục và không có kỹ thuật nào là tốt nhất. Ta sẽ xem xét các kỹ thuật này thông qua các tiêu chí: Kiểu truy xuất: Kiểu tìm kiếm mà kỹ thuật lập chỉ mục hỗ trợ: Tìm kiếm với một giá trị cụ thể hay tìm kiếm với các giá trị trong một khoảng giới hạn. Thời gian truy xuất: Thời gian cần thiết để truy xuất tới một hay một số bản ghi. Thời gian thêm mới một bản ghi: Thời gian cần thiết để thêm mới một bản ghi, bao gồm thời gian thêm bản ghi vào đúng vị trí trong file và thời gian cập nhật lại cấu trúc chỉ mục. Thời gian xóa bản ghi: Thơi gian cần thiết để xóa bản ghi, bao gồm thời gian để tìm, xóa bản ghi và thời gian cập nhật lại cấu trúc chỉ mục. Thường ta muốn trong một file có thể có nhiều hơn một chỉ mục. Chẳng hạn, ta muốn tìm kiếm một quyển sách theo nhiều tiêu chí: tác giả, tên sách, chủ đề, ... Thuộc tính hay một nhóm thuộc tính dùng để tìm kiếm các bản ghi trong file gọi là khóa tìm kiếm (search key – Khái niệm này khác với khái niệm khóa chính, khóa ứng cử hay siêu khóa). 2.2. Các chỉ mục có thứ tự 2.2.1. Chỉ mục chính (Primary Indexes) Là chỉ mục được thiết lập trên trường khóa chính của file được sắp xếp thứ tự theo khóa chính. File chỉ mục là một file có thứ tự gồm hai trường với các bản ghi có độ dài cố định. Một bản ghi trong file chỉ mục, gồm hai phần: [Ki, Pi] trong đó Ki là giá trị tương ứng với giá trị trên trường khóa đã sắp thứ tự, Pi chứa địa chỉ khối chứa bản ghi có khóa Ki của file dữ liệu. Với chỉ mục chính: số bản ghi trong file chỉ mục bằng số khối trong file dữ liệu. Hình sau minh họa cấu trúc file chỉ mục chính thiết lập trên trường khóa (Name) có sắp thứ tự trong file Employee:
16 Hình 2.1: Chỉ mục chính thiết lập trên trường khóa có thứ tự Tìm kiếm với điều kiện trên trường khóa: Search (K) Xác định bản ghi thứ i của file chỉ mục thỏa mãn: Ki ≤ K < Ki+1. Dựa vào con trỏ Pi trong file chỉ mục đọc khối đĩa chứa bản ghi cần tìm vào bộ đệm và tiến hành tìm kiếm bản ghi. Xét một file dữ liệu có thứ tự với 30000 bản ghi với độ dài cố định là 100 byte và tổ chức theo kiểu không kéo dài (unspanned) được lưu trên đĩa với kích thước khối đĩa là 1024 byte. Như vậy một khối đĩa lưu được bfr = 1024 / 100 = 10 bản ghi. Do vậy, số khối cần để lưu file dữ liệu là: b = 30000 / 10 = 3000 khối đĩa. Để tìm kiếm một bản ghi có trường khóa là K ta sử dụng phương pháp tìm kiếm nhị phân mất: log2 (b) = log2 (3000) = 12. Giả sử tạo file chỉ mục chính có số bản ghi bằng số khối trong file dữ liệu. Mỗi bản ghi gồm 2 trường: trường khóa kích thước 9 byte, kích thước con trỏ là 6 byte thì một bản ghi trong file chỉ mục có độ dài 15 byte. Mỗi khối đĩa sẽ lưu
17 được bfri = 1024 / 15 = 68 bản ghi của file chỉ mục. Do vậy để lưu file chỉ mục cần b i = 30000 / 68 = 45 khối đĩa. Khi đó muốn tìm bản ghi có giá trị khóa K cần: log2 (45) + 1 (truy cập file dữ liệu) = 7. Như vậy rõ ràng nếu có file chỉ mục thì việc tìm kiếm trên trường khóa sẽ nhanh hơn nhiều lần. 2.2.2. Chỉ mục cụm (Clustering Indexes) Nếu các bản ghi trong file dữ liệu được sắp sếp thứ tự trên trường không khóa (không có giá trị duy nhất cho mỗi bản ghi), ta có thể tạo ra một kiểu chỉ mục khác – gọi là chỉ mục cụm – để tăng tốc độ truy xuất tới các bản ghi với điều kiện trên trường không khóa. Hình 2.2: Chỉ mục cụm trên trường không khóa (DeptNumber) có sắp thứ tự 2.2.3. Chỉ mục phụ (Secondary Indexes) Chỉ mục phụ cung cấp một phương thức để truy cập nhanh tới file dữ liệu trên trường không được sắp thứ tự. Chỉ mục phụ có thể áp dụng trên trường khóa ứng cử (có giá trị duy nhất với mỗi bản ghi trong file dữ liệu) hoặc trên trường không khóa (có giá trị giống nhau với những bản ghi khác nhau trong file dữ liệu). Nếu chỉ mục được thiết lập trên trường khóa không được sắp xếp thì mỗi bản ghi trên file dữ liệu sẽ có tương ứng một bản ghi trong file chỉ mục (Khác với chỉ mục chính: Số bản ghi trong file chỉ mục chính chỉ bằng số khối cần để lưu trữ file dữ liệu). Do vậy chỉ mục phụ cần nhiều không gian lưu trữ và thời gian tìm kiếm hơn so với chỉ mục chính.
18 Hình 2.3: Chỉ mục phụ trên trường khóa không sắp thứ tự Giả sử có một file dữ liệu với r = 30000 bản ghi. Các bản ghi có kích thước cố định R = 100 byte. Lưu trên đĩa với kích thước khối đĩa là B = 1024 byte. Khi đó file dữ liệu sẽ được lưu trong 3000 khối. Khi cần tìm kiếm trên một trường không sắp thứ tự: Nếu không có file chỉ mục phụ: Thực hiện tìm kiếm tuần tự trung bình cần 3000 / 2 = 1500 lần truy cập khối. Nếu tạo một file chỉ mục phụ trên trường cần tìm kiếm kích thước 9 byte, kích thước con trỏ là 6 byte, khi đó kích thước một bản ghi trong file chỉ mục phụ là 15 byte. Như vậy một khối đĩa sẽ lưu được 1024 / 15 = 68 bản ghi của file chỉ mục phụ. Do chỉ mục được xây dựng trên trường khóa không được sắp thứ tự nên số bản ghi trong file chỉ mục bằng số bản ghi trong file dữ liệu (như hình trên). Do vậy số khối cần để lưu file chỉ mục phụ là: 30000 / 68 = 442 khối. Như vậy để tìm kiếm cần: log2 (442) + 1 (lần truy cập khối đĩa trên file dữ liệu) = 10 lần truy cập khối đĩa.
19 Như vậy file chỉ mục phụ là giải pháp hiệu quả để giảm thời gian tìm kiếm trên trường khóa không được sắp xếp. Ta cũng có thể tạo chỉ mục phụ trên trường không khóa. Khi đó sẽ có nhiều bản ghi trên file dữ liệu có cùng giá trị trên trường cần tạo chỉ mục. Khi đó giải pháp thông dụng là tạo thêm một file trung gian (giữa file chỉ mục phụ với file dữ liệu) để xử lý các bản ghi có giá trị trùng nhau trên trường tìm kiếm. Hình 2.4: Chỉ mục phụ trên trường không khóa không sắp thứ tự 2.3. Chỉ mục cây B+ 2.3.1. Tóm lược về cây tìm kiếm Cây là một khái niệm trong cấu trúc dữ liệu. Cây được tạo thành từ các nút; Mỗi nút trong cây (trừ nút gốc) đều có một nút cha và có thể có hoặc không có nút con. Một nút không có nút con nào gọi là nút lá. Mức của nút gốc là 0. Mức của nút con = Mức của nút cha + 1.
20 Cây tìm kiếm bậc p là một cây mà mỗi nút chứa nhiều nhất p – 1 giá trị tìm kiếm và p con trỏ theo thứ tự: với q ≤ p. Mỗi con trỏ Pi trỏ tới một nút con hoặc không trỏ tới nút nào (Null Pointer). Có hai ràng buộc trên cây: Trong mỗi nút: K1 < K2 < ... < Kq-1. Với các giá trị X trong cây con được trỏ bởi Pi: o Ki-1 < X < Ki (1 < i < q). o X < Ki (i = 1). o Ki-1 < X (i = q). Hình 2.5: Một nút trong cây tìm kiếm với các con trỏ tới cây con Ta có thể sử dụng cấu trúc cây tìm kiếm để tìm kiếm các bản ghi, các giá trị K trên mỗi là một trường trên file ta gọi là search field (giống khái niệm index field trong file chỉ mục). 2.3.2. Chỉ mục B – Tree Cấu trúc của B – Tree bậc p: Mỗi nút trong (internal node) có dạng: