Tổ chức dữ liệu vật lý

Quản lí lưu trữ trên thiết bị nhớ ngoài

Tổ chức tệp: sắp xếp các bản ghi trên thiết bị nhớ ngoài, với:
- RID - record id: địa chỉ vật lí của các bản ghi
- Chỉ số: cấu trúc dữ liệu xác định sự tương ứng giữa RID và giá trị của trường (khóa) của bản ghi
Vùng nhớ đệm (cache): trung gian giữa thiết bị nhớ ngoài và bộ nhớ trong, có thể được sử dụng cho dữ liệu và chỉ số
Do việc truy xuất đến bộ nhớ ngoài có tốc độ tương đối chậm so với bộ nhớ trong, việc tổ chức bộ nhớ ngoài được thực hiện nhằm giảm thiểu truy xuất không cần thiết, cần quan tâm đến:
- Cấu trúc lưu trữ
- Các phép toán (thêm, tìm kiếm, sửa, xóa)

Tổ chức tệp dữ liệu:
- Các bản ghi được phân vào các cụm
- Mỗi cụm gồm một hoặc nhiều khối
- Mỗi khối chỉ chứa một số lượng bản ghi nhất định
- Tổ chức lưu trữ dữ liệu trong mỗi cụm theo tổ chức đống
Ánh xạ giữa giá trị khóa và chỉ số cụm bằng hàm băm, được chọn nhằm phân bố bản ghi tương đối đồng đều theo cụm
Phép Tìm kiếm:
- Tính giá trị hàm băm và đi đến cụm đó
- Duyệt toàn bộ để lấy bản ghi cần thiết
Phép Thêm:
- Tính giá trị hàm băm, đi đến cụm đó
- Tìm khối có chỗ trống đầu tiên trong cụm và ghi lại bản ghi
- Nếu cụm không còn khối trống, thêm khối mới vào cuối cụm và ghi vào khối này
Phép Xóa:
- Tìm kiếm và xóa nếu tồn tại
- Giải phóng khối nếu việc xóa khiến khối thành khối trống
Phép Sửa:
- Sửa trên trường khóa: tìm kiếm, xóa và thêm bản ghi mới
- Sửa trên trường không khóa: tìm kiếm, cập nhật lại giá trị

Tệp chỉ dẫn được xây dựng theo một khóa chọn trên các bản ghi
Tệp chỉ dẫn gồm các cặp $(k, d)$ với $k$ là giá trị khóa của bản ghi đàu tiên, $d$ là địa chỉ của khối
Giả sử dữ liệu được sắp xếp theo khóa
Tệp chỉ dẫn được sắp xếp theo giá trị của khóa
Phép Tìm kiếm: có thể sử dụng tìm kiếm tuần tự hoặc tìm kiếm nhị phân
- Tìm kiếm trên tệp chỉ dẫn
- Tìm kiếm trên khối
Phép Thêm:
- Tìm trên tệp chỉ dẫn khối sẽ chứa bản ghi
- Nếu tìm được khối có thẻ chèn vào, chèn bản ghi theo thứ tự sắp xếp của khóa
  - Nếu chèn vào đầu, cần cập nhật lại chỉ số trong phải chỉ dẫn
  - Nếu khối hết chỗ, dịch bản ghi cuối của khối hiện tại sang đầu khối tiếp theo và cập nhật tệp chỉ dẫn
- Nếu không tìm được, tạo khối mới và thêm vào tệp chỉ dẫn
Phép Xóa:
- Tìm đến bản ghi cần xóa
- Xóa bản ghi
  - Nếu là bản ghi ở đầu, cần cập nhật lại tệp chỉ dẫn
  - Nếu việc xóa làm khối trống, cần giải phóng khối và cập nhật tệp chỉ dẫn
Phép Sửa:
- Tìm kiếm bản ghi
- Nếu trường sửa là trường khóa, xóa và thêm mới
- Nếu trường sửa không phải trường khóa, cập nhật giá trị trong bản ghi

Mỗi bản ghi là một nút lá của cây cân bằng B-Tree
Cây cân bằng B-tree tổ chức theo cấp $m$ có các tính chất:
- Gốc của cây là một nút lá hoặc có ít nhất 2 nút con
- Mỗi nút (trừ nút gốc và nút lá) có từ $⌈ \frac{m}{2} ⌉$ đến $m$ con
- Mỗi đường đi từ nút gốc đến nút lá bất kỳ nào đều có độ dài như nhau
Các khóa trong một nút được sắp xếp theo thứ tự
Phép Tìm kiếm: Duyệt từ nút gốc đến nút lá
Phép Thêm:
- Xác định vị trí chứa bản ghi là nút lá $L$
- Nếu còn chỗ, thêm bản ghi dưới dạng nút lá
- Nếu hết chỗ, tạo nút lá $L^{'}$ , chuyển nửa cuối dữ liệu của $L$ sang $L^{'}$ , chèn bản ghi mới vào $L$ hoặc $L^{'}$ tùy theo giá trị khóa
Phép Xóa:
- Tìm kiếm nút lá $L$ chứa bản ghi
- Loại bỏ bản ghi khỏi $L$
- Nếu đây là bản ghi đầu tiên, chỉnh sửa khóa ở các nút trên cho tới gốc
- Nếu việc xóa làm nút $L$ chứa số bản ghi ít hơn $⌈ \frac{m}{2} ⌉$ thì thực hiện điều chỉnh, có thẻ gộp 2 nút