intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Tổ chức dữ liệu vật lý - Vũ Tuyết Trinh

Chia sẻ: Sinh Nhân | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST
Báo xấu
113
lượt xem 9
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Tổ chức dữ liệu vật lý" cung cấp cho sinh viên các kiến thức về quản lý lưu trữ dữ liệu, tổ chức bộ nhớ ngoài, thiết bị nhớ ngoài, tổ chức tệp, các phép toán, so sánh các tổ chức dữ liệu. Đây là một tài liệu hữu ích dành cho các bạn sinh viên Công nghệ thông tin dùng làm tài liệu học tập và nghiên cứu.

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 Tổ chức dữ liệu vật lý - Vũ Tuyết Trinh

  1. Nhập môn cơ sở dữ liệu Tổ chức dữ liệu ệ vật ậ lý ý Vũ Tuyết Trinh trinhvt@it-hut.edu.vn Bộ môn Các hệ thống thông tin, Khoa Công nghệ thông tin Đại học Bách Khoa Hà Nội Hệ CSDL Ứng dụng Hệ QTCSDL CSDL CSDL Vũ Tuyết Trinh, b/m Hệ thống thông tin, Khoa CNTT, ĐHBKHN 1
  2. Nhập môn cơ sở dữ liệu Bộ xử lý câu hỏi Bộ quản lý Giao dịch Quản lý lưu trữ Bộ quản lý 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ản lý 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ản lý tệp dịch định sự tương ứng giữa RID của 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ức bộ 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
  3. Nhập môn cơ sở dữ liệu Các thiết bị nhớ ngoài { Đĩa từ, băng từ, trống từ, ... { Đĩa từ: được tổ chức thành từng trang z Chí phí truy nhập đến các trang bất kỳ là tương đương z Chí phí đọc nhiều trang liền nhau < chí phí đọc các trang đó theo thứ tự bất kỳ { Băng từ: z chỉ có thể đọc được các trang liền nhau z rẻ hơn đĩa từ nhưng chi phí truy nhập thương lớn hơn { ... Đĩa từ vs. bộ nhớ trong { Tốc độ truy nhập bộ ms vs. ns (~1000 lần) { Kích thước GB vs. 10x MB (~ 100 lần với cùng chi phí) { Lưu trữ ổn định (kể cả khi mất điện) vs. tạm thời { Phân chia block 4KB vs. 1Byte Vũ Tuyết Trinh, b/m Hệ thống thông tin, Khoa CNTT, ĐHBKHN 3
  4. Nhập môn cơ sở dữ liệu Nội dung 9 Tổng quan về tổ chức bộ nhớ ngoài { Tổ chức tệp đống { Tổ chức tệp băm { Tổ chức tệp chỉ dẫn { Cây cân bằng Tổ chức tệp đống (Heap File) { Lưu trữ kế tiếp các bản ghi trong các trang khô ttuân không â ththeo một ột thứ ttự đặc đặ biệ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
  5. Nhập môn cơ sở dữ liệu Cài đặt tệp đống bằng danh sách Data Data Data Full Pages Page Page Page Header Page Data Data Data Pages with Page Page Page Free Space { Cần lưu trữ HeaderPage và tên của tệp { Mỗi trang gồm dữ liệu và 2 con trỏ Các phép toán { Tìm kiếm 1 bản ghi { Thêm 1 bản ghi { Xoá 1 bản ghi { Sửa đổi một bản ghi Vũ Tuyết Trinh, b/m Hệ thống thông tin, Khoa CNTT, ĐHBKHN 5
  6. 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ức tệp bă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 Dựa trên t ê bảng bả băm bă (hash (h h ttable) bl ) 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
  7. Nhập môn cơ sở dữ liệu Ví dụ h(x) = x mod 4 1 Store hash 2 4 3 1 2 3 4 1 2 3 4 Ví dụ tiếp h(x) = x mod 4 Store hash 10 12 6 1 2 3 4 1 2 3 4 10 12 6 Vũ Tuyết Trinh, b/m Hệ thống thông tin, Khoa CNTT, ĐHBKHN 7
  8. Nhập môn cơ sở dữ liệu Các phép toán { Tìm kiếm 1 bản ghi { Thêm 1 bản ghi { Xoá 1 bản ghi { Sửa đổi một bả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ạn chế việc sử 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
  9. Nhập môn cơ sở dữ liệu Tổ chức tệp chỉ dẫn (Index File) { Tệp chỉ dẫn theo khoá được chọn trong bản ghi { Tệp chỉ dẫn bao gồm các cặp (k,d), trong đó k là giá trị của khoá của bản ghi đầu tiên, d là địa chỉ của khối (hay con trỏ khối). { Tệp chỉ dẫn được sắp xếp theo giá trị của khoá. Các phép toán { Tìm kiếm 1 bản ghi { Thêm 1 bản ghi { Xoá 1 bản ghi { Sửa đổi một bản ghi Vũ Tuyết Trinh, b/m Hệ thống thông tin, Khoa CNTT, ĐHBKHN 9
  10. Nhập môn cơ sở dữ liệu Tìm kiếm 1 bản ghi { Tìm kiếm tuần tự 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ếm nhị 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ại mỗi lần chia hạn chế được ½ số bản ghi cần xem 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
  11. Nhập môn cơ sở dữ liệu Ví dụ Nhận xét { Cấu trúc của mỗi nút trong B-tree (p0, kl, p1, k2,...,kn, pn) z pi (i=l..n) là con trỏ trỏ tới khối i của nút có ki là khoá đầu tiên của khối đó. z Các khoá k trong một nút được sắp xếp theo thứ tự tăng dần. { Mọi khoá trong cây con, trỏ bởi pi đều nhỏ hơn ki+1 { Mọi khoá trong cây con, trỏ bởi pn đều lớn hơn kn. Vũ Tuyết Trinh, b/m Hệ thống thông tin, Khoa CNTT, ĐHBKHN 11
  12. Nhập môn cơ sở dữ liệu Các phép toán { Tìm kiếm 1 bản ghi { Thêm 1 bản ghi { Xoá 1 bản ghi { Sửa đổi một bả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
  13. Nhập môn cơ sở dữ liệu Kết luận { Truy cập đến CSDL thường liên quan đến một phần nhỏ các bản ghi trong một tệp dữ liệu hay một vài trường (đặc biệt là các trường khoá) của các bản ghi dữ liệu. ¾ Xác định các yêu cầu này cho phép thiết kế dữ liệu vật lý hiệu quả thông qua việc sử dụng các tổ chức lưu trữ đặc biệt { Tệp ệp chỉ dẫn được ợ tạo ạ lập ập trên khoá tìm kiếm để tăng hiệu quả của lưu trữ dữ liệu ¾ Hiệu quả của các cấu trúc chỉ dẫn khác nhau phụ thuộc vào điều kiện áp dụng chúng Vũ Tuyết Trinh, b/m Hệ thống thông tin, Khoa CNTT, ĐHBKHN 13
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2