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