Hilbert R-tree ซึ่งเป็นตัวแปร R-tree ถูกกำหนดให้เป็นดัชนีสำหรับออบเจ็กต์หลายมิติ เช่น เส้น ขอบเขต ออบเจ็กต์สามมิติ หรือออบเจ็กต์พารามิเตอร์ตามคุณลักษณะที่มีมิติสูง สามารถจินตนาการได้ว่าเป็นส่วนขยายของ B+-tree สำหรับวัตถุหลายมิติ
ประสิทธิภาพของ R-trees ขึ้นอยู่กับคุณภาพของอัลกอริทึมที่จัดกลุ่มสี่เหลี่ยมข้อมูลบนโหนด ต้นไม้ Hilbert R ใช้เส้นโค้งเติมช่องว่าง และโดยเฉพาะเส้นโค้ง Hilbert สำหรับการจัดลำดับเชิงเส้นบนสี่เหลี่ยมข้อมูล
Hilbert R-trees มีสองประเภท:แบบหนึ่งสำหรับฐานข้อมูลแบบสแตติก และอีกแบบสำหรับฐานข้อมูลไดนามิก ในทั้งสองกรณี มีการใช้เส้นโค้งเติมช่องว่างของฮิลเบิร์ตเพื่อให้การจัดลำดับวัตถุหลายมิติในโหนดดีขึ้น การจัดลำดับนี้จะต้องถือว่าเป็น "ดี" ในแง่นั้นควรจัดกลุ่มสี่เหลี่ยมข้อมูลที่ 'คล้ายคลึงกัน' ไว้ด้วยกัน เพื่อลดพื้นที่และปริมณฑลของผลลัพธ์สี่เหลี่ยมที่มีขอบต่ำสุด (MBR) Packed Hilbert R-trees มีประโยชน์สำหรับฐานข้อมูลแบบสแตติกซึ่งมีการอัปเดตน้อยมากหรือไม่มีการอัพเดตเลย
แนวคิดพื้นฐาน
แม้ว่าตัวอย่างต่อไปนี้มีไว้สำหรับสภาพแวดล้อมแบบคงที่ แต่จะกล่าวถึงหลักการที่ใช้งานง่ายสำหรับการออกแบบ R-tree ที่ดี หลักการเหล่านี้ถูกกฎหมายสำหรับฐานข้อมูลทั้งแบบสแตติกและไดนามิก
Roussopoulos และ Leifker เสนอเทคนิคสำหรับการสร้าง R-tree ที่อัดแน่นซึ่งใช้พื้นที่ได้เกือบ 100%
แนวคิดนี้พัฒนาขึ้นเพื่อจัดเรียงข้อมูลบนพิกัด x หรือ y ของมุมใดมุมหนึ่งของสี่เหลี่ยม การเรียงลำดับจากสี่พิกัดใด ๆ ให้ผลลัพธ์เหมือนกัน ในการอภิปรายนี้ จุดหรือสี่เหลี่ยมผืนผ้าจะถูกจัดเรียงบนพิกัด x ของมุมล่างซ้ายของสี่เหลี่ยม ซึ่งแสดงว่าเป็น "ต้นไม้ R ที่อัดแน่นต่ำ" รายการที่จัดเรียงของสี่เหลี่ยมผืนผ้าถูกสแกน สี่เหลี่ยมต่อเนื่องถูกกำหนดให้กับโหนดลีฟ R-tree ที่คล้ายกันจนกระทั่งและยกเว้นว่าโหนดนั้นเต็ม โหนดปลายสุดใหม่จะถูกสร้างขึ้น และการสแกนรายการที่เรียงลำดับจะดำเนินต่อไป ดังนั้น โหนดของ R-tree ที่ได้จะถูกแพ็กอย่างสมบูรณ์ ยกเว้นโหนดสุดท้ายในแต่ละระดับที่เป็นไปได้ สิ่งนี้นำไปสู่เหตุการณ์เพื่อให้การใช้พื้นที่ ≈100% ระดับที่สูงขึ้นของต้นไม้ถูกสร้างขึ้นในลักษณะเดียวกัน
Algorithm Hilbert-Pack
(บรรจุสี่เหลี่ยมลงใน R-tree)
ขั้นตอนที่ 1 คำนวณค่า Hilbert สำหรับสี่เหลี่ยมข้อมูลแต่ละอัน
ขั้นตอนที่ 2 สี่เหลี่ยมข้อมูลบนค่า Hilbert จากน้อยไปมากจะถูกจัดเรียง
ขั้นตอนที่ 3 /* การสร้างโหนดปลายสุด (ระดับ l=0) */
- ในขณะที่ (มีสี่เหลี่ยมมากกว่า)
- มีการสร้างโหนด R-tree ใหม่
- กำหนดสี่เหลี่ยม C ถัดไปให้กับโหนดนี้
ขั้นตอนที่ 4 /* การสร้างโหนดในระดับที่สูงขึ้น (l + 1) */
- ในขณะที่ (มี> 1 โหนดที่ระดับ l)
- โหนดที่ระดับ l ≥ 0 ตามเวลาที่สร้างจากน้อยไปมากจะถูกจัดเรียง
- ขั้นตอนที่ 3 ซ้ำแล้วซ้ำอีก
สมมติฐานในที่นี้คือข้อมูลเป็นแบบคงที่หรือความถี่ของการแก้ไขต่ำ นี่เป็นฮิวริสติกอย่างง่ายสำหรับการสร้าง R-tree โดยใช้พื้นที่ ~100% ซึ่งในขณะเดียวกันจะมีเวลาตอบสนองที่ดี
