Khái niệm cơ bản
Trong xử lý dữ liệu, R*-tree là biến thể của R-tree dùng để lập chỉ mục thông tin không gian.
R*-tree có chi phí xây dựng cao hơn R-tree tiêu chuẩn chút ít, do dữ liệu có thể cần chèn lại; nhưng cây kết quả thường có hiệu năng truy vấn tốt hơn. Giống R-tree tiêu chuẩn, nó lưu trữ cả dữ liệu điểm và không gian. Khái niệm R*-tree được đề xuất bởi Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger năm 1990.
Sự khác biệt giữa R*-tree và R-tree
R*-tree được xây dựng bằng chèn lặp lại. Có rất ít (gần như không) chồng lấp (overlap) trong cây này, dẫn đến hiệu năng truy vấn tốt. Tối thiểu hóa cả bao phủ (coverage) và chồng lấp rất quan trọng đối với hiệu năng R-tree. Ý nghĩa của chồng lấp: khi chèn hoặc truy vấn dữ liệu, nhiều nhánh cây hơn phải được mở rộng (do cách dữ liệu được chia thành các vùng có thể chồng lấp). Bao phủ tối thiểu tăng cường hiệu năng cắt tỉa (pruning), cho phép loại bỏ toàn bộ trang khỏi tìm kiếm thường xuyên, đặc biệt cho truy vấn phạm vi âm. R*-tree cố gắng giảm cả hai, dùng thuật toán tách nút (node split) cải tiến và khái niệm chèn lại ép buộc (forced reinsertion) khi tràn nút. Khái niệm này dựa trên quan sát: cấu trúc R-tree rất nhạy cảm với thứ tự chèn các mục, nên cấu trúc xây dựng bằng chèn (thay vì tải hàng loạt - bulk-loaded) có khả năng không tối ưu. Xóa và chèn lại các mục cho phép chúng "tìm" vị trí phù hợp hơn trong cây.
Thuật toán và độ phức tạp
- R*-tree dùng thuật toán tương tự R-tree thông thường cho truy vấn và xóa.
- Khi chèn, R*-tree dùng chiến lược kết hợp: với nút lá, tối thiểu hóa chồng lấp; với nút nội bộ, tối thiểu hóa mở rộng và diện tích.
- Khi tách, R*-tree dùng tách topo (topological split) chọn trục tách dựa trên chu vi, sau đó tối thiểu hóa chồng lấp.
- Ngoài chiến lược tách cải tiến, R*-tree cũng cố gắng bỏ qua tách bằng cách chèn lại đối tượng và cây con vào cây, lấy cảm hứng từ cân bằng B-tree.
Độ phức tạp truy vấn và xóa trường hợp xấu nhất tương tự R-Tree. Chiến lược chèn của R*-tree phức tạp O(M log M) hơn chiến lược tách tuyến tính O(M) của R-tree, nhưng kém phức tạp hơn chiến lược tách bậc hai O(M²) cho kích thước trang M đối tượng, và ảnh hưởng ít đến tổng độ phức tạp. Tổng độ phức tạp chèn vẫn tương đương R-tree: chèn lại chỉ ảnh hưởng tối đa một nhánh cây, do đó O(log n) lần chèn lại, tương đương thực hiện phép chia trên R-tree thông thường. Vậy tổng thể, độ phức tạp R*-tree tương đương R-tree thông thường.