Bài giảng Cơ sở dữ liệu - Chương 5: Tổ chức dữ liệu vật lý - Vũ Tuyết Trinh

Nội dung text: Bài giảng Cơ sở dữ liệu - Chương 5: Tổ chức dữ liệu vật lý - Vũ Tuyết Trinh

1. Nhập môn cơ sở dữ liệu Bộ xử lý câu hỏi Bộ quảnlý Giao dịch Bộ quảnlý Quảnlýlưu trữ lưu trữ { Tổ chức tệp: sắp xếp các bản ghi trên thiết bị nhớ Bộ quảnlýlưu trữ ngoài Quản lý buffer Quản z RID (record id): xác định địa lý chỉ vật lý của các bản ghi giao z chỉ số: cấu trúc dữ liệu xác Quảnlý tệp dịch định sự tương ứng giữa RID củaba bản ghi và giá trị của trường (khoá) { Vùng nhớ đệm: trung gian Metadata & Data & index giữa thiết bị nhớ ngoài và Data dictionary bộ nhớ trong (có thể sử dụng cho cả DL và chỉ số) Tổ chứcbộ nhớ ngoài { Mục đích: giảm thiểu truy xuất đến dữ liệu không cần thiết trên thiết bị nhớ ngoài { Các vấn đề cần quan tâm z Cấu trúc lưu trữ z Các phép toán (thêm, xoá, sửa, tìm kiếm) Vũ Tuyết Trinh, b/m Hệ thống thông tin, Khoa CNTT, ĐHBKHN 2
2. Nhập môn cơ sở dữ liệu Nội dung 9 Tổng quan về tổ chứcbộ nhớ ngoài { Tổ chứctệp đống { Tổ chứctệpbăm { Tổ chứctệpchỉ dẫn { Cây cân bằng Tổ chứctệp đống (Heap File) { Lưu trữ kế tiếp các bản ghi trong các trang không tu ân theo mộttth thứ tự đặc biệtàt nào { Để thực hiện các phép toán, cần: z Ghi nhớ số trang trong 1 tệp z Ghi nhớ không gian trống trên các trang z Ghi nhớ các bản ghi trên các trang ¾ Có các con trỏ trỏ tới tất cả các trang của tệp và các con trỏ này được lưu trữ ở bộ nhớ trong. Vũ Tuyết Trinh, b/m Hệ thống thông tin, Khoa CNTT, ĐHBKHN 4
3. Nhập môn cơ sở dữ liệu Sử dụng trang danh bạ Data Header Page 1 Page Data Page 2 Data DIRECTORY Page N { Lưu thông tin về số byte còn trống trên trang đó { Danh bạ là 1 tập các trang Tổ chứctệpbăm (Hash File) { Mục đích z Sử dụng chỉ sốđểhạn chế số lượng phép truy xuất đĩa bằng các phân nhóm các bản ghi (giả thiết n nhóm) z Mapping giá trị khoá với vị trí của (nhóm) bản ghi tương ứng { Dựa ttêrên b ảng băm (hhtblhash table) z Hàm băm (hash function) z Cụm (bucket) Vũ Tuyết Trinh, b/m Hệ thống thông tin, Khoa CNTT, ĐHBKHN 6
4. Nhập môn cơ sở dữ liệu Các phép toán { Tìm kiếm1 bản ghi { Thêm 1 bản ghi { Xoá 1 bản ghi { Sửa đổimộtbản ghi Tiêu chí chọn hàm băm { Phân bố các bản ghi tương đối đồng đều (theo các cụm) { Hạnchế việcsử dụng nhiều trang bộ nhớ cho 1 cụm Vũ Tuyết Trinh, b/m Hệ thống thông tin, Khoa CNTT, ĐHBKHN 8
5. Nhập môn cơ sở dữ liệu Tìm kiếm1 bản ghi { Tìm kiếmtuầntự z Duyệt tệp chỉ dẫn từ bản ghi đầu tiên đến khi tìm thấy bản ghi có khoá k cần tìm z Nhận xét { chậm đối với các tệp chỉ dẫn nói chung. { Thích hợp với các tệp chỉ dẫn nhỏ đủ để lưu ở bộ nhớ trong { Tìm kiếmnhị phân z Chia đôi tệp chỉ dẫn đã sắp xếp để hạn chế số bản ghi cần duyệt z Tạimỗilần chia hạnchếđược½ số bản ghi cầnxem xét Cây cân bằng (BalanceTree) { B-tree cân bằng được tổ chức theo cấp m, có các tính chất sau đây: z Gốc của cây hoặc là một nút lá hoặc ít nhất có hai con. z Mỗi nút (trừ nút gốc và nút lá) có từ [m/2] đến m con. z Mỗi đường đi từ nút gốc đến bất kỳ nút lá nào đều có độ dài như nhau. Vũ Tuyết Trinh, b/m Hệ thống thông tin, Khoa CNTT, ĐHBKHN 10
6. Nhập môn cơ sở dữ liệu Các phép toán { Tìm kiếm1 bản ghi { Thêm 1 bản ghi { Xoá 1 bản ghi { Sửa đổimộtbản ghi So sánh các cách tổ chức dữ liệu { Tệp đống { Tệp băm { Tệp chỉ dẫn { Cây cân bằng Vũ Tuyết Trinh, b/m Hệ thống thông tin, Khoa CNTT, ĐHBKHN 12