แนวคิดพื้นฐาน
R*-tree เป็น Variant ของ R-tree สำหรับ Indexing Spatial Data (ข้อมูลเชิงพื้นที่) เสนอโดย Beckmann, Kriegel, Schneider, Seeger (1990)
Construction Cost สูงกว่า R-tree เล็กน้อย (ต้อง Reinsert) แต่ Query Performance ดีกว่า รองรับทั้ง Point และ Spatial Data
ความแตกต่าง R*-tree vs R-tree
| ลักษณะ | R-tree | R*-tree |
|---|---|---|
| Construction | Bulk-load หรือ Insert | Repeated Insertion + Forced Reinsertion |
| Overlap | มี Overwalk ค่อนข้างมาก | Overlap น้อยมาก (Minimize) |
| Coverage | ไม่ได้ Optimize โดยตรง | Minimize Coverage และ Overlap พร้อมกัน |
| Split Strategy | Linear/Quadratic Split | Topological Split (เลือก Axis จาก Perimeter) + Minimize Overlap |
| Reinsertion | ไม่มี | มี Forced Reinsertion เมื่อ Overflow (คล้าย B-tree Balancing) |
| Query Performance | ปานกลาง | ดีกว่ามาก (Pruning ดี, Negative Range Queries เร็ว) |
Algorithm และ Complexity
- Query/Delete: เหมือน R-tree
- Insert: Combined Strategy - Leaf Minimize Overlap, Inner Minimize Enlargement/Area
- Split: Topological Split (Axis จาก Perimeter) + Minimize Overlap
- Skip Splits: Reinsert Objects/Subtrees (คล้าย B-tree Balancing)
Complexity Analysis
- Worst-case Query/Delete: เหมือน R-tree
- Insert Strategy: O(M log M) - ระหว่าง Linear O(M) และ Quadratic O(M²)
- Reinsertions: สูงสุด 1 Branch → O(log n) Reinsertions
- Total Insert Complexity: เทียบเท่า R-tree
ข้อดีหลัก
- ลด Overlap → ลด Branch ที่ต้อง Visit ระหว่าง Query
- ลด Coverage → Pruning ดีขึ้น
- Forced Reinsertion → โครงสร้างไม่ขึ้นกับ Insertion Order
