Hilbert R-tree, một biến thể R-tree, được định nghĩa là một chỉ số cho các đối tượng đa chiều như đường, vùng, đối tượng 3-D hoặc đối tượng tham số dựa trên đặc điểm chiều cao. Nó có thể được hình dung như một phần mở rộng của B + -tree cho các đối tượng đa chiều.
Hiệu suất của R-tree phụ thuộc vào chất lượng của thuật toán gom các hình chữ nhật dữ liệu trên một nút. Hilbert R-tree triển khai các đường cong lấp đầy không gian và cụ thể là đường cong Hilbert, để áp đặt thứ tự tuyến tính trên các hình chữ nhật dữ liệu.
Hilbert R-tree có hai loại:một loại dành cho cơ sở dữ liệu tĩnh và một loại dành cho cơ sở dữ liệu động. Trong cả hai trường hợp, các đường cong lấp đầy không gian Hilbert được thực hiện để đạt được thứ tự tốt hơn của các đối tượng nhiều chiều trong nút. Thứ tự này phải được coi là "tốt", theo nghĩa là nó phải nhóm các hình chữ nhật dữ liệu "tương tự" lại với nhau, để giảm diện tích và chu vi của các hình chữ nhật có giới hạn tối thiểu thu được (MBR). Cây R-Hilbert đóng gói rất hữu ích cho cơ sở dữ liệu tĩnh trong đó các bản cập nhật rất hiếm hoặc không có bản cập nhật nào.
Ý tưởng cơ bản
Mặc dù ví dụ sau dành cho môi trường tĩnh, nhưng nó thảo luận về các nguyên tắc trực quan để thiết kế R-tree tốt. Những nguyên tắc này hợp pháp cho cả cơ sở dữ liệu tĩnh và động.
Roussopoulos và Leifker đã đề xuất một kỹ thuật xây dựng một cây R đóng gói để đạt được gần như 100% việc sử dụng không gian.
Ý tưởng được phát triển để sắp xếp dữ liệu theo tọa độ x hoặc y của một trong các góc của hình chữ nhật. Sắp xếp theo bất kỳ tọa độ nào trong bốn tọa độ sẽ cho kết quả giống nhau. Trong cuộc thảo luận này, các điểm hoặc hình chữ nhật được sắp xếp theo tọa độ x của góc dưới bên trái của hình chữ nhật, được biểu thị là "cây R đóng gói thấp". Danh sách đã sắp xếp của hình chữ nhật được quét; các hình chữ nhật liên tiếp được gán cho nút lá cây R tương tự cho đến khi và trừ khi nút đó đầy; một nút lá mới sau đó được xây dựng và quá trình quét danh sách đã sắp xếp tiếp tục. Do đó, kết quả là nút của cây R sẽ được đóng gói đầy đủ, ngoại trừ nút cuối cùng ở mỗi cấp. Điều này dẫn đến sự cố để sử dụng không gian ≈100%. Các tầng cao hơn của cây được xây dựng theo cách tương tự.
Thuật toán Hilbert-Pack
(đóng gói các hình chữ nhật thành một cây R)
Bước 1. Giá trị Hilbert cho mỗi hình chữ nhật dữ liệu được tính toán.
Bước 2. Dữ liệu hình chữ nhật về các giá trị Hilbert tăng dần được sắp xếp.
Bước 3. / * Tạo nút lá (mức l =0) * /
- Trong khi (có nhiều hình chữ nhật hơn)
- Một nút cây R mới được tạo
- Các hình chữ nhật C tiếp theo cho nút này được chỉ định
Bước 4. / * Tạo các nút ở cấp cao hơn (l + 1) * /
- Trong khi (có> 1 nút ở mức l)
- Các nút ở mức l ≥ 0 theo thời gian tạo tăng dần được sắp xếp
- Bước 3 được lặp lại
Giả định ở đây là dữ liệu tĩnh hoặc tần suất sửa đổi thấp. Đây là một phương pháp đơn giản để xây dựng một cây R với khả năng sử dụng ~ 100% không gian, đồng thời sẽ có thời gian phản hồi tốt.