แนวคิดพื้นฐาน
Hilbert R-tree เป็น Variant ของ R-tree ใช้เป็น Index สำหรับ Multidimensional Objects: เส้น, พื้นที่, วัตถุ 3D, High-dimensional Feature-based Objects สามารถมองได้ว่าเป็น Extension ของ B+-tree สำหรับข้อมูลหลายมิติ
ประสิทธิภาพ R-tree ขึ้นอยู่กับ Quality ของ Clustering Algorithm Hilbert R-tree ใช้ Space-filling Curves (เส้นเติมพื้นที่) โดยเฉพาะ Hilbert Curve เพื่อเรียงลำดับ Data Rectangles ให้เป็น Linear Order
2 ประเภท Hilbert R-trees
- Static Databases: Packed Hilbert R-trees - ใช้สำหรับ DB ที่ Update น้อย/ไม่มี
- Dynamic Databases: รองรับ Insert/Delete
ทั้งคู่ใช้ Hilbert Curve เพื่อ Ordering ที่ "Good" = จัดกลุ่ม Data Rectangles ที่ "คล้าย" กัน ให้ MBR (Minimum Bounding Rectangles) มี Area และ Perimeter น้อยที่สุด
แนวคิดหลัก: Packed R-tree Construction
Roussopoulos & Leifker: Sort ข้อมูลด้วย X หรือ Y ของมุมสี่เหลี่ยม → Scan เรียง → เติม Node จนเต็ม → สร้าง Node ใหม่ → ได้ Space Utilization ≈ 100%
Algorithm: Hilbert-Pack
- คำนวณ Hilbert Value สำหรับแต่ละ Data Rectangle
- Sort Rectangles ตาม Hilbert Value 昇序 (Ascending)
- สร้าง Leaf Nodes (Level l=0): While มี Rectangle เหลือ → สร้าง Node ใหม่ → Assign C Rectangles ถัดไป
- สร้าง Higher Levels (l+1): While มี >1 Node ที่ Level l → Sort Nodes ตาม Creation Time → Repeat Step 3
สมมติฐาน
ข้อมูลเป็น Static หรือ Modify น้อย → Heuristic เรียบง่าย สร้าง R-tree ~100% Space Utilization + Good Response Time
ทำไม Hilbert Curve?
- Preserve Locality: จุดที่ใกล้กันในพื้นที่ 2D → ใกล้กันใน 1D Order
- Clustering ดีกว่า Z-order (Morton Curve)
- MBR ที่ได้มี Area/Perimeter น้อย → Query เร็วขึ้น
