Cấu trúc lưu trữ và phương pháp truy xuất

Chương V. Cấu trúc lưu trữ và phương pháp truy xuất 1 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 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 Đĩa (Disk) 4 5 Quản lý đĩa 6  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. Lưu tập tin trên đĩa 7 Mục đích 8 Mẩu tin 9 Tập tin 10 Tập tin (tt) 11 Tập tin (tt) 12 Lưu mẩu tin vào block 13 Tổ chức file block trên đĩa 14 Thao tác trên file 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  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… type deposit = record account-number: char(10); branch-name: char(22); balance: real; end 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 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) Perryridg e 1 A-102 400 1 A-305 Round Hill 350 Mianus1 A-215 700 Downtow n 1 A-101 500 Redwood1 A-222 700 Perryridg e 1 A-201 900 Brighton1 A-217 750 Downtow n 1 A-110 600 Perryridg e 1 A-218 700 0 0 0 0 411 10 11 32 33 40 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 H Perryridg e 1 A-102 400 1 A-305 Round Hill 350 Mianus0 A-215 700 Downtow n 1 A-101 500 Redwood1 A-222 700 Perryridg e 1 A-201 900 Brighton0 A-217 750 Downtow n 1 A-110 600 Perryridg e 1 A-218 700 0 0 0 800A-111 Redwood 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  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 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-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 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-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 22 Mẫu tin có chiều dài động (tt) A-202 950  Byte-String Representation Tốn nhiều chi phí khi chiều dài mẫu tin thay đổi - 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 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 e A-102 400 A-305Round Hill 350 Mianus A-215 700 Downtow n A-101 500 Redwood A-222 700 A-201 900 Brighton A-217 750 A-110 600 A-218 700 24 Mẫu tin có chiều dài động (tt)  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 o Anchor block – Chứa mẫu tin đầu tiên của mảng account- info o 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 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 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 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 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 Clustering  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, customer-city from depositor, customer where depositor.customer-name=customer.customer-name 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 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  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 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 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 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 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 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 38 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 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 Cây cân bằng (tt) 41