Giáo trình Hệ quản trị cơ sở dữ liệu - Chương 2: Cấu trúc lưu trữ và phương pháp truy xuất - Lê Thị Minh Nguyên

8/25/2017 1 Chương 2. Cấu trúc lưu trữ và phương pháp truy xuất GV: Lê Thị Minh Nguyện Email: nguyenltm@huflit.edu.vn Nội dung 1. Tổ chức dữ liệu 2. Các bộ phận của tổ chức tổ chức dữ liệu 3. Mẫu tin (record) 4. Sắp xếp các mẫu tin vào block 5. Tổ chức mẫu tin trên tập tin 6. Tổ chức băm 7. Tổ chức B cây 8. Chỉ mục (index) Hệ quản trị Cơ sở dữ liệu 2 1. Tổ chức dữ liệu 1.1. Khái niệm 1.2. Sự cần thiết của tổ chức dữ liệu 1.3. Các thuận lợi và khó khăn khi tổ chức dữ liệu 1.4. Các giải pháp tổ chức dữ liệu Hệ quản trị Cơ sở dữ liệu 3 1.1. Khái niệm • Tổ chức dữ liệu là tiến trình phân tích và cấu trúc lại dữ liệu (đôi khi chỉ là các giá trị dữ liệu, phức tạp hơn là cơ sở dữ liệu) của hệ thống • Kết quả của việc tổ chức dữ liệu là có được hệ thống tổ chức và quản lý dữ liệu tốt hơn, có thể có một cơ sở dữ liệu chuẩn với các mô hình dữ liệu được cài đặt Hệ quản trị Cơ sở dữ liệu 4 8/25/2017 2 1.1. Khái niệm (tt) • Các hoạt động khi tổ chức dữ liệu thường gặp: • Tổ chức dưới dạng tập tin đơn giản trong hệ thống • Tổ chức thành cơ sở dữ liệu được quản lý bởi DBMS • Chuyển hệ thống dùng một DBMS này sang hệ thống dùng một DBMS khác • Chuyển đổi dữ liệu toàn cục dùng chung cho toàn bộ hệ thống thành các đối tượng hay các dạng dữ liệu với cấu trúc trừu tượng Hệ quản trị Cơ sở dữ liệu 5 1.2. Sự cần thiết của tổ chức dữ liệu Hệ quản trị Cơ sở dữ liệu 6 1.2. Sự cần thiết của tổ chức dữ liệu (tt) • Đối với các hệ thống cũ, những khó khan bao gồm: • Những người tham gia tổ chức dữ liệu không còn làm việc trong công ty. • Một số hệ thống hoạt động trên máy tính lớn, dữ liệu lưu trữ ở một nơi, khó khan cho việc khai thác phân bố ở nhiều nơi khác nhau. • Một số hệ thống sử dụng các cơ sở dữ liệu cũ hay các tập tin đã lỗi thời có sự gia tang lớn về sự trùng lắp dữ liệu. Hệ quản trị Cơ sở dữ liệu 7 1.3. Các thuận lợi và khó khăn khi tổ chức dữ liệu • Thuận lợi • Tăng tính hiệu quả khi khai thác dữ liệu • Giảm thiểu rủi ro trong tương lai • Tận dụng các tri thức đã tích lũy trong hệ thống cũ, • Khó khăn • Vấn đề chi phí • Đối với các hệ thống cũ, nếu thay đổi cách tiếp cận khi phân tích, thiết kế nhằm phục vụ cho việc tổ chức dữ liệu thì gần như xây dựng lại từ đầu • Đào tạo nhân sự tiếp cận công nghệ mới, Hệ quản trị Cơ sở dữ liệu 8 8/25/2017 3 1.4. Các giải pháp tổ chức dữ liệu • Tổ chức Dữ liệu theo tập tin • Tổ chức dữ liệu theo cơ sở dữ liệu • Nêu ứng dụng, ưu và khuyết điểm của 2 loại tổ chức dữ liệu????? Hệ quản trị Cơ sở dữ liệu 9 2. Các bộ phận của tổ chức tổ chức dữ liệu 2.1. Bộ phận quản lý tập tin (File Manager) 2.2. Bộ phận quản lý đĩa (magnetic disk) 2.3. Tổ chức vật lý Tổ chức vật lý Hệ quản trị Cơ sở dữ liệu 10 Bộ phận quản lý tập tin (File Manager) • Lưu trữ thông tin trên đĩa từ dưới dạng các file. Các file sẽ có con trỏ xác định điểm vào các sector đầu tiên chứa thông tin. Các file được quản lý dưới dạng cây gọi là cây thư mục 11 2.1. Bộ phận quản lý đĩa (magnetic disk) Hệ quản trị Cơ sở dữ liệu 12 Memory Registers CPU I/O Devices I/O BusMemory Bus C A C H E Size Speed Virtural Memory File System Disk Second storage Tertiary storage 8/25/2017 4 2.1. Bộ phận quản lý đĩa (magnetic disk) (tt) Hệ quản trị Cơ sở dữ liệu 13 • Dung lượng lớn • Dữ liệu không bị mất khi hệ thống mất điện hay gặp sự cố (non-volatile) • Tốc độ truy xuất • Thời gian định vị track (seek time): ? ms • Thời gian định vị sector (rotational delay): ? ms • Thời gian chuyển dữ liệu (transfer time): ? kb • Truy xuất dữ liệu • Đọc trực tiếp dữ liệu ở 1 vị trí bất kỳ trên đĩa • Theo đơn vị lưu trữ - block hay page 2.1. Bộ phận quản lý đĩa (magnetic disk) (tt) • Làm sao bố trí dữ liệu trên đĩa????? Hệ quản trị Cơ sở dữ liệu 14 • Muốn lưu trữ dữ liệu • Mã tài khoản • Tên chi nhánh • Số dư • Ngày rút tiền • Dữ liệu được biểu diễn bằng chuỗi các bytes 8 bits 2.3. Tổ chức vật lý • Hai cách tổ chức lưu trữ dữ liệu cơ bản của hệ thống là lưu trữ ở dạng văn bản (text) và nhị phân (binary). • Thường tổ chức ở dạng nhị phân Hệ quản trị Cơ sở dữ liệu 15 Tổ chức trên SQL Server Hệ quản trị Cơ sở dữ liệu 16 8/25/2017 5 Tổ chức trên Oralce Hệ quản trị Cơ sở dữ liệu 17 3. Mẫu tin (record) Hệ quản trị Cơ sở dữ liệu 18 • Tập hợp các dữ liệu có liên quan với nhau tạo thành một mẫu tin • Ví dụ • Mẫu tin account có những thông tin • Account-number • Branch-name • Balance • Có 2 loại mẫu tin • Mẫu tin có chiều dài cố định (Fixed-Length Record) • Mẫu tin có chiều dài động (Variable-Length Record) 3.1. Mẫu tin có chiều dài cố định Hệ quản trị Cơ sở dữ liệu 19 type deposit = record account-number: char(10); branch-name: char(22); balance: real; end 3.1. Mẫu tin có chiều dài cố định(tt) Hệ quản trị Cơ sở dữ liệu 20 • Ví dụ • Mỗi mẫu tin có thêm 1 bit (tương tự .dbf) • =0: Xóa • =1: Đang dùng • Danh sách các mẫu tin trống (free list) Perryridge1 A-102 400 1 A-305 Round Hill 350 Mianus1 A-215 700 Downtown1 A-101 500 Redwood1 A-222 700 Perryridge1 A-201 900 Brighton1 A-217 750 Downtown1 A-110 600 Perryridge1 A-218 700 0 0 0 0 411 1011 3233 40 8/25/2017 6 3.1. Mẫu tin có chiều dài cố định(tt) Hệ quản trị Cơ sở dữ liệu 21 • Hủy mẫu tin • Đánh dấu xóa vào bit thông tin • Đưa mẫu tin bị đánh dấu xóa vào free list FH Perryridge1 A-102 400 1 A-305 Round Hill 350 Mianus0 A-215 700 Downtown1 A-101 500 Redwood1 A-222 700 Perryridge1 A-201 900 Brighton0 A-217 750 Downtown1 A-110 600 Perryridge1 A-218 700 0 0 0 800A-111 Redwood 3.1. Mẫu tin có chiều dài cố định(tt) Hệ quản trị Cơ sở dữ liệu 22 • Thêm một mẫu tin • Hoặc thêm vào những mẫu tin bị đánh dấu xóa hoặc thêm vào cuối tập tin • Cập nhật lại free list • Tìm kiếm • Quét tuần tự trên tập tin FH Perryridge1 A-102 400 1 A-305 Round Hill 350 Downtown1 A-111 700 Downtown1 A-101 500 Redwood1 A-222 700 Perryridge1 A-201 900 Brighton0 A-217 750 Downtown1 A-110 600 Perryridge1 A-218 700 0 0 0 3.2. Mẫu tin có chiều dài động Hệ quản trị Cơ sở dữ liệu 23 • Trong DBMS, mẫu tin có chiều dài động • Lưu trữ nhiều loại mẫu tin trong 1 tập tin • Các loại mẫu tin chứa các trường có chiều dài động • Có 2 cách biểu diễn • Byte-String • Fixed-Length • Ví dụ: type account-list = record branch-name: char(22); account-info: array [1..n] of record account-number: char(10); balance: real; end end 3.2. Mẫu tin có chiều dài động (tt) Hệ quản trị Cơ sở dữ liệu 24 • Byte-String Representation • Cuối mỗi mẫu tin có 1 byte ký tự đặc biệt cho biết kết thúc mẫu tin Perryridge -A-102 400 - A-305Round Hill 350 Mianus - A-215 700 Downtown A-101 500 Redwood - A-222 700 A-201 900 Brighton - A-217 750 A-110 600 - A-218 700 8/25/2017 7 3.2. Mẫu tin có chiều dài động (tt) Hệ quản trị Cơ sở dữ liệu 25 • Byte-String Representation • Cuối mỗi mẫu tin có 1 byte ký tự đặc biệt cho biết kết thúc mẫu tin • Sử dụng lại không gian trống sau khi xóa 1 mẫu tin không hiệu quả • Dẫn đến tình trạng phân mãnh Perryridge -A-102 400 - A-305Round Hill 350 Mianus - A-215 700 Downtown A-101 500 Redwood - A-222 700 A-201 900 Brighton - A-217 750 A-110 600 - A-218 700 3.2. Mẫu tin có chiều dài động (tt) Hệ quản trị Cơ sở dữ liệu 26 Byte-String Representation Tốn nhiều chi phí khi chiều dài mẫu tin thay đổi A-202 950- Perryridge -A-102 400 A-305Round Hill 350 A-201 900 A-218 700 Brighton A-217 750 - - Mianus A-215 700 Downtown A-101 500 Redwood - A-222 700 - A-110 600 3.2. Mẫu tin có chiều dài động (tt) Hệ quản trị Cơ sở dữ liệu 27 • Fixed-Length Representation • Sử dụng 1 hay nhiều mẫu tin có chiều dài cố định biểu diễn cho những mẫu tin có chiều dài động • Có 2 kỹ thuật • Reserved space • Point 3.2. Mẫu tin có chiều dài động (tt) Hệ quản trị Cơ sở dữ liệu 28 • Fixed-Length Representation • Reserved space • Sử dùng độ dài lớn nhất của 1 mẫu tin nào đó cài đặt cho tất cả các mẫu tin còn lại • Độ dài này phải đảm bảo không bao giờ dài thêm được nữa Perryridge A-102 400 A-305Round Hill 350 Mianus A-215 700 Downtown A-101 500 Redwood A-222 700 A-201 900 Brighton A-217 750 A-110 600 A-218 700 8/25/2017 8 3.2. Mẫu tin có chiều dài động (tt) Hệ quản trị Cơ sở dữ liệu 29 • Fixed-Length Representation • Pointer • Các mẫu tin có chiều dài động móc xích với nhau thông qua danh sách các mẫu tin có chiều dài cố định • Có 2 loại blocks trong tập tin • Anchor block – Chứa mẫu tin đầu tiên của mảng account- info • Overflow block – Chứa các mẫu tin tiếp theo của mảng account-info Perryridge A-102 400 A-305Round Hill 350 Mianus A-215 700 Downtown A-101 500 Redwood A-222 700 Brighton A-217 750 A-201 900 A-110 600 A-218 700 Anchor block Overflow block 4. Sắp xếp các mẫu tin vào block Hệ quản trị Cơ sở dữ liệu 30 Kích thước cố định Giả sử chỉ có 1 filea file blocks records 5. Tổ chức mẫu tin trên tập tin Hệ quản trị Cơ sở dữ liệu 31 • Cho 1 tập các mẫu tin • Tổ chức các mẫu tin trên tập tin như thế nào? • Sequential • Clustering • Indexing • Hashing • B-Tree 5.1. Tuần tự (Sequential) Hệ quản trị Cơ sở dữ liệu 32 • Các mẫu tin được tổ chức lưu trữ tuần tự theo 1 thứ tự nào đó, thông thường theo trường khóa tìm kiếm (search- key) • Khóa tìm kiếm không nhất thiết là khóa chính hay siêu khóa 8/25/2017 9 5.1. Tuần tự (Sequential) (tt) Hệ quản trị Cơ sở dữ liệu 33 • Các mẫu tin được tổ chức lưu trữ tuần tự theo 1 thứ tự nào đó, thông thường theo trường khóa tìm kiếm (search- key) • Khóa tìm kiếm không nhất thiết là khóa chính hay siêu khóa 5.1. Tuần tự (Sequential) (tt) Hệ quản trị Cơ sở dữ liệu 34 • Xóa mẫu tin • Sử dụng danh sách các con trỏ trỏ đến vùng trống • Thêm mẫu tin  Tìm vị trí thích hợp trên tập tin  Nếu có vị trí trống trong cùng 1 block thì thêm vào  Ngược lại sẽ thêm vào vùng overflow block  Cập nhật lại con trỏ theo đúng thứ tự của khóa tìm kiếm 5.1. Tuần tự (Sequential) (tt) Hệ quản trị Cơ sở dữ liệu 35 • Nhận xét • Giảm tối thiểu khối lượng block cần đọc khi truy xuất tập tin • Tốn nhiều chi phí di chuyển các mẫu tin sau khi thêm hoặc xóa 1 mẫu tin 5.2. Clustering Hệ quản trị Cơ sở dữ liệu 36 • Xét 2 quan hệ depositor và customer • Thực hiện câu truy vấn • Nếu các bộ của quan hệ depositor và customer nằm gần nhau trong tập tin thì câu truy vấn sẽ được thực hiện 1 cách hiệu quả • Khi 1 bộ của customer được đọc thì nguyên cả khối chứa bộ này cũng được đưa vào bộ nhớ chính • Lúc đó các bộ của depositor có liên quan đến customer đã có sẳn và được xử lý ngay select account-number, customer-name, customer-street from depositor, customer where depositor.customer-name=customer.customer-name 8/25/2017 10 5.2. Clustering (tt) Hệ quản trị Cơ sở dữ liệu 37 • Tổ chức clustering lưu trữ các mẫu tin tương ứng của 2 hay nhiều quan hệ trong cùng 1 block • Nhận xét  Có hiệu quả khi truy vấn có phép kết  Chưa thật sự tốt nếu truy vấn trên 1 quan hệ  Một block có nhiều loại mẫu tin Chỉ mục Hệ quản trị Cơ sở dữ liệu 38 • Chỉ mục được dùng để truy xuất dữ liệu nhanh hơn • Một tập tin dữ liệu sẽ có 1 hoặc nhiều tập tin chỉ mục kèm theo • Tập tin chỉ mục gồm • Tập tin chỉ mục sẽ nhỏ hơn rất nhiều so với tập tin dữ liệu ban đầu • Tập tin chỉ mục được sắp xếp thứ tự theo khóa tìm kiếm pointersearch-key Chỉ mục (tt) Hệ quản trị Cơ sở dữ liệu 39 • Nếu 1 tập tin chứa các mẫu tin đã được sắp thứ tự • Chỉ mục sơ cấp (Primary index) • Là chỉ mục có khóa tìm kiếm định nghĩa ra thứ tự sắp xếp các mẫu tin của tập tin gốc • Còn được gọi là clustering index • Chỉ mục thứ cấp (Secondary index) • Là chỉ mục có khóa tìm kiếm đưa ra 1 thứ tự sắp xếp khác với thứ tự tuần tự của tập tin gốc • Còn được gọi là nonclustering index Chỉ mục (tt) Hệ quản trị Cơ sở dữ liệu 40 • Chỉ mục dày (Dense index) • Tập tin gốc có bao nhiêu mẫu tin thì tập tin chỉ mục có bấy nhiêu 8/25/2017 11 Chỉ mục (tt) Hệ quản trị Cơ sở dữ liệu 41 • Chỉ mục thưa (Sparse index) • Tập tin chỉ mục chỉ lưu lại 1 số khóa của tập tin gốc • Để xác định vị trí của 1 khóa k • Tìm trong tập tin chỉ mục khóa lớn nhất nhưng vẫn bé hơn k • Tìm trong tập tin gốc bắt đầu từ địa chỉ vừa xác định trong tập tin chỉ mục Chỉ mục (tt) • Cú pháp: CREATE INDEX ON (,,) • Ví dụ: CREATE INDEX ON MonHoc(TenMH) Hệ quản trị Cơ sở dữ liệu 42 Chỉ mục (tt) Hệ quản trị Cơ sở dữ liệu 43 • Nhận xét • Tìm kiếm nhanh trong trường hợp so sánh với hằng số và phép kết • Làm chậm đi các thao tác thêm, xóa và sửa • Tốn chi phí • Lưu trữ chỉ mục • Truy xuất đĩa nhiều • Chọn lựa cài đặt chỉ mục hợp lý??? Hệ quản trị Cơ sở dữ liệu 44