›
›

Bài giảng Hệ quản trị dữ liệu - Chương V: Cấu trúc lưu trữ và phương pháp truy xuất

pdf 41 trang hapham 2390
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Hệ quản trị dữ liệu - Chương V: Cấu trúc lưu trữ và phương pháp truy xuất", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_he_quan_tri_du_lieu_chuong_v_cau_truc_luu_tru_va_p.pdf

Nội dung text: Bài giảng Hệ quản trị dữ liệu - Chương V: Cấu trúc lưu trữ và phương pháp truy xuất

  1. Chương V. Cấu trúc lưu trữ và phương pháp truy xuất 1
  2. Nội dung  Giới thiệu  Đĩa (magnetic disk)  Mẫu tin (record)  Sắp xếp các mẫu tin vào block  Tổ chức mẫu tin trên tập tin 2
  3. Giới thiệu (tt)  Phân cấp lưu trữ Bộ nhớ chính Dữ liệu hiện hành Đĩa CSDL chính thức Băng từ (tape) hay đĩa quang (optical disk) Phiên bản cũ của CSDL 3
  4. Đĩa (Disk) 4
  5. Quản lý đĩa  Một mặt đĩa chia thành nhiều track, 1 track chia thành nhiều block(page). 1 cluster = n block.  Dùng đĩa từ (magnetic disk) để lưu CSDL vì:  Khối lương lưu trữ lớn.  Lưu một cách bền bỉ, lâu dài, phục vị truy cập và xử lý lặp lại.  Chi phí rẻ.  Dữ liệu trên đĩa phải được chép vào bộ nhớ chính khi cần xử lý. Nếu dữ liệu này có thay đổi thì sẽ được ghi trở lại vào đĩa.  Bộ điều khiển đĩa(Disk controller - DC): giao tiếp giữa ổ đĩa và máy tính, nhận lệnh I/O, định vị đầu đọc và làm cho hành động R/W diễn ra.  Block cũng là đơn vị để lưu trữ và chuyển dữ liệu. 6
  6. Lưu tập tin trên đĩa 7
  7. Mục đích 8
  8. Mẩu tin 9
  9. Tập tin 10
  10. Tập tin (tt) 11
  11. Tập tin (tt) 12
  12. Lưu mẩu tin vào block 13
  13. Tổ chức file block trên đĩa 14
  14. Thao tác trên file 15
  15. Mẫu tin có chiều dài cố định  Xét 1 tập tin gồm các mẫu tin account type deposit = record account-number: char(10); branch-name: char(22); balance: real; end  Giả sử  1 char : 1 byte  Real : 8 bytes  1 mẫu tin account : 40 bytes  40 bytes đầu tiên là mẫu tin thứ 1  40 bytes tiếp theo là mẫu tin thứ 2 16
  16. Mẫu tin có chiều dài cố định (tt)  Record header  Lược đồ của mẫu tin  Chiều dài của mẫu tin  Thời gian sau cùng cập nhật mẫu tin Không nhất thiết để các thông tin này ở record header  Block header  Con trỏ nối các block có liên quan với nhau  Thông tin về mối quan hệ giữa các mẫu tin trong block  Block ID  Thời gian sau cùng truy xuất block 17
  17. Mẫu tin có chiều dài cố định (tt)  Ví dụ  Mỗi mẫu tin có thêm 1 bit  =0: Xóa  =1: Đang dùng  Danh sách các mẫu tin trống (free list) 0 1 10 11 32 33 40 41 1 A-102 Perryridg 400 1 A-305 Round 350 1 A-215 Mianuse 700 1 A-101 DowntowHill 500 1 A-222 Redwood 700 1 A-201 Perryridgn 900 1 A-217 Brighton 750 1 A-110 Downtowe 600 1 A-218 Perryridg 700 0 n 0 e 0 18
  18. Mẫu tin có chiều dài cố định (tt)  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 F H1 A-102 Perryridg 400 1 A-305 Round 350 0 A-215 Mianuse 700 1 A-101 DowntowHill 500 1 A-222 Redwood 700 1 A-201 Perryridgn 900 0 A-217 Brighton 750 1 A-110 Downtowe 600 1 A-218 Perryridg 700 0 A-111 Redwoodn 800 0 e 0 19
  19. Mẫu tin có chiều dài cố định (tt)  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 FH 1 A-102 Perryridge 400 1 A-305 Round Hill 350 1 A-111 Downtown 700 1 A-101 Downtown 500 1 A-222 Redwood 700 1 A-201 Perryridge 900 0 A-217 Brighton 750 1 A-110 Downtown 600 1 A-218 Perryridge 700 0 0 0  Tìm kiếm  Quét tuần tự trên tập tin 20
  20. Mẫu tin có chiều dài động  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-201 900 A-218 700 - Round Hill A-305 350 - Brighton A-217 750 - Downtown A-101 500 A-110 600 - Mianus A-215 700 - Redwood A-222 700 - 21
  21. Mẫu tin có chiều dài động (tt)  Byte-String Representation  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-201 900 A-218 700 - Round Hill A-305 350 - Brighton A-217 750 - Downtown A-101 500 A-110 600 - Mianus A-215 700 - Redwood A-222 700 - 22
  22. Mẫu tin có chiều dài động (tt)  Byte-String Representation Tốn nhiều chi phí khi chiều dài mẫu tin thay đổi Perryridge A-102 400 A-201 900 A-218 700 - Round Hill A-305 350 -A-202 Brighton950 A-217 750 - Downtown A-101 500 A-110 600 - Mianus A-215 700 - Redwood A-222 700 - 23
  23. Mẫu tin có chiều dài động (tt)  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  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 Perryridg A-102 400 A-201 900 A-218 700 Rounde A-305 350 MianusHill A-215 700 Downtow A-101 500 A-110 600 Redwoodn A-222 700 24 Brighton A-217 750
  24. Mẫu tin có chiều dài động (tt)  Fixed-Length Representation  Pointer Anchor block  ẫ ề độ Các m u tin có chi u dài ng Perryridge A-102 400 móc xích với nhau thông qua Round Hill A-305 350 danh sách các mẫu tin có chiều Mianus A-215 700 dài cố định Downtown A-101 500  Có 2 loại blocks trong tập tin Redwood A-222 700 o Anchor block – Chứa mẫu tin Brighton A-217 750 đầu tiên của mảng account- info A-201 900 o Overflow block – Chứa các A-218 700 A-110 600 mẫu tin tiếp theo của mảng Overflow block account-info 25
  25. Tổ chức mẫu tin trên tập tin  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 26
  26. Tuần tự (Sequential)  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  Mỗi mẫu tin có 1 con trỏ trỏ đến mẫu tin khác theo thứ tự khóa tìm kiếm 27
  27. Tuần tự (tt)  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 28
  28. Tuần tự (tt)  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  Phải tổ chức lại tập tin theo thứ tự khóa tìm kiếm sau mỗi lần thêm hoặc xóa 29
  29. Clustering  Xét 2 quan hệ depositor và customer  Thực hiện câu truy vấn select account-number, customer-name, customer-street, customer-city from depositor, customer where depositor.customer-name=customer.customer-name  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ó 30 sẳn và được xử lý ngay
  30. Clustering (tt)  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 31
  31. Chỉ mục (Indexing)  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 search-key pointer  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 32
  32. Chỉ mục (tt)  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 33
  33. Chỉ mục (tt)  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 34
  34. Chỉ mục (tt)  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 35
  35. Băm (hashing)  Chia các mẫu tin trong tập tin thành từng vùng (bucket) tùy theo giá trị khóa của mẫu tin  Mẫu tin thuộc về vùng nào tùy thuộc vào hàm băm được áp dụng trên mẫu tin đó  Sử dụng hàm băm để xác định vị trí của mẫu tin  Các mẫu tin có khóa khác nhau có thể được băm vào cùng 1 vùng, vì vậy cần phải tìm tuần tự trên vùng để định vị mẫu tin 36
  36. Băm (tt)  Xét 1 tập tin gồm các mẫu tin account có trường branch-name là khóa  Giả sử  10 vùng  Thứ tự thứ i của các ký tự trong bảng chữ cái là các số nguyên i  Hàm băm sum(các ký tự) modulo 10  h(Perryridge) = 5  h(Round Hill) = 3  h(Brighton) = 3 37
  37. Băm (tt)  Các vùng có thể xãy ra hiện tượng tràn khi  Không đủ kích thước  Phân phối mẫu tin vào các vùng không cân xứng  Có nhiều mẫu tin trùng giá trị khóa  Hàm băm cho ra kết quả băm không tốt  Vấn đề tràn vùng được giải quyết bằng cách sử dụng thêm các vùng tràn (overflow buckets) 39
  38. Cây cân bằng (B-Tree)  B-Tree là 1 cây có gốc thỏa điều kiện  Tất cả các đường đi từ nút gốc đến đến nút là đều bằng nhau  Ngoại trừ nút gốc, mỗi nút có từ n/2 đến n cây con  n là bậc của cây  Nút lá có từ (n-1)/2 đến n-1 khóa  Cấu trúc 1 nút  Khóa tìm kiếm trên 1 nút được sắp thứ tự tăng dần K1 < K2 < K3 < . . . < Kn–1 40
  39. Cây cân bằng (tt) 41