Hilbert R-tree, một biến thể của R-tree, được định nghĩa là chỉ mục cho các đối tượng đa chiều như đường, vùng, đối tượng 3D, hoặc đối tượng tham số dựa trên đặc trưng chiều cao. Có thể tưởng tượng như mở rộng B+-tree cho đối tượng đa chiều.
Hiệu năng R-tree phụ thuộc vào chất lượng thuật toán gom cụm các hình chữ nhật dữ liệu trên một nút. Hilbert R-tree sử dụng đường cong lấp đầy không gian, cụ thể là đường cong Hilbert, để áp đặt mộ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: cho cơ sở dữ liệu tĩnh và cho cơ sở dữ liệu động. Cả hai đều dùng đường cong Hilbert để đạt thứ tự tốt hơn của đối tượng đa chiều trong nút. Thứ tự này phải "tốt" بمعنى gom 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 hình chữ nhật bao tối thiểu (MBR). Hilbert R-tree đóng gói (Packed) hữu ích cho cơ sở dữ liệu tĩnh mà cập nhật hiếm hoặc không có cập nhật.
Ý tưởng cơ bản
Mặc dù ví dụ sau dành cho môi trường tĩnh, nó thảo luận các nguyên tắc trực quan cho thiết kế R-tree tốt. Các nguyên tắc này áp dụng cho cả cơ sở dữ liệu tĩnh và động.
Roussopoulos và Leifker đề xuất kỹ thuật xây dựng packed R-tree đạt gần 100% sử dụng không gian.
Ý tưởng là sắp xếp dữ liệu theo tọa độ x hoặc y của một góc của hình chữ nhật. Sắp xếp theo bất kỳ trong 4 tọa độ cho cùng kết quả. Ở đây sắp xếp theo tọa độ x của góc dưới bên trái hình chữ nhật, gọi là "lowx packed R-tree". Danh sách hình chữ nhật đã sắp xếp được quét; các hình chữ nhật liên tiếp được gán vào cùng nút lá R-tree cho đến khi nút đầy; nút lá mới được tạo, tiếp tục quét. Do đó, nút R-tree kết quả sẽ được đóng gói đầy đủ, trừ nút cuối cùng ở mỗi cấp. Điều này dẫn đến việc sử dụng không gian ≈ 100%. Các cấp 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 hình chữ nhật vào R-tree)
Bước 1. Tính giá trị Hilbert cho mỗi hình chữ nhật dữ liệu.
Bước 2. Sắp xếp hình chữ nhật dữ liệu theo giá trị Hilbert tăng dần.
Bước 3. /* Tạo nút lá (cấp l=0) */
- Khi (còn hình chữ nhật)
- Tạo nút R-tree mới
- Gán C hình chữ nhật tiếp theo cho nút này
Bước 4. /* Tạo nút ở cấp cao hơn (l + 1) */
- Khi (có > 1 nút ở cấp l)
- Sắp xếp nút ở cấp l ≥ 0 theo thời gian tạo tăng dần
- Lặp lại Bước 3
Giả định ở đây là dữ liệu tĩnh hoặc tần suất sửa đổi thấp. Đây là heuristic đơn giản để xây dựng R-tree với ~100% sử dụng không gian và thời gian phản hồi tốt.