Xem R-Tree. Dùng để lưu chỉ mục dữ liệu không gian hiệu quả. Hữu ích cho truy vấn và lưu trữ dữ liệu không gian. Ứng dụng thực tế:
- Chỉ mục thông tin đa chiều
- Xử lý dữ liệu game
- Lưu tọa độ địa lý
- Triển khai bản đồ ảo
Ví dụ R-Tree:
R-tree tương ứng:
Đặc tính R-Tree
- Gốc đơn, nút nội, nút lá.
- Gốc trỏ đến vùng lớn nhất miền không gian.
- Nút cha chứa nút con, vùng con hoàn toàn trong vùng cha.
- Nút lá giữ dữ liệu MBR của đối tượng.
- MBR (Minimum Bounding Region) – hộp bao tối thiểu bao quanh vùng.
Khác biệt với Quad-tree
| Quad Tree | R-Tree |
|---|---|
| Cần tối ưu hóa mức tiling | Không cần tối ưu hóa |
| Có thể xây trên B-tree | Không theo cấu trúc B-tree |
| Tạo chỉ mục không gian nhanh hơn | Tạo chỉ mục không gian chậm hơn |
| Truy vấn nearest neighbor chậm, window query nhanh | Nearest neighbor nhanh, window query chậm |