แนวคิดพื้นฐาน
ในกรณีของการประมวลผลข้อมูล R*-tree ถูกกำหนดให้เป็นตัวแปรของ R-tree ที่ใช้สำหรับสร้างดัชนีข้อมูลเชิงพื้นที่
R*-trees มีค่าใช้จ่ายในการก่อสร้างมากกว่า R-tree มาตรฐานเล็กน้อย เนื่องจากอาจจำเป็นต้องใส่ข้อมูลเข้าไปใหม่ แต่ทรีผลลัพธ์โดยทั่วไปจะมีประสิทธิภาพการสืบค้นที่ดีขึ้น เช่นเดียวกับ R-tree มาตรฐาน สามารถจัดเก็บทั้งข้อมูลจุดและเชิงพื้นที่ แนวคิดของ R*-tree เสนอโดย Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider และ Bernhard Seeger ในปี 1990
ความแตกต่างระหว่าง R*-tree และ R-trees
R*-Tree ถูกสร้างขึ้นโดยการใส่ซ้ำๆ มีการทับซ้อนกันเล็กน้อย (นั่นคือแทบไม่มี) ในแผนผังนี้ ส่งผลให้ประสิทธิภาพการสืบค้นที่ดี การลดขนาดความครอบคลุมและการทับซ้อนกันมีความสำคัญมากต่อประสิทธิภาพของ R-tree ความหมายของการทับซ้อนในการแทรกข้อมูลหรือคิวรีคือต้องมีการขยายสาขามากกว่าหนึ่งสาขา (เนื่องจากวิธีการแบ่งข้อมูลในภูมิภาคที่อาจทับซ้อนกัน) ความครอบคลุมที่น้อยที่สุดช่วยเพิ่มประสิทธิภาพการตัดแต่ง อนุญาตให้แยกทั้งหน้าออกจากการค้นหาบ่อยครั้ง โดยเฉพาะอย่างยิ่งสำหรับการค้นหาช่วงเชิงลบ R*-tree พยายามลดทั้งสองอย่าง โดยนำคอลเล็กชันของอัลกอริธึมการแยกโหนดที่แก้ไขแล้วมาใช้และแนวคิดของการบังคับให้ใส่ซ้ำที่โหนดล้น แนวคิดนี้อิงจากการสังเกตว่าโครงสร้าง R-tree มีความอ่อนไหวสูงต่อลำดับการแทรกรายการ ดังนั้นโครงสร้างแบบแทรก (แทนที่จะเป็นแบบจำนวนมาก) จึงมีแนวโน้มต่ำกว่าที่เหมาะสม การลบและการแทรกรายการใหม่ช่วยให้พวกเขา "ค้นหา" สถานที่ในแผนผังที่อาจเหมาะสมกว่าตำแหน่งจริงได้
อัลกอริทึมและความซับซ้อน
- R*-tree ใช้อัลกอริทึมที่คล้ายคลึงกันกับ R-tree ปกติสำหรับการดำเนินการค้นหาและลบ
- ในขณะที่ทำการแทรก R*-tree ใช้กลยุทธ์แบบผสมผสาน สำหรับโหนดปลายสุด การทับซ้อนกันจะถูกย่อให้เล็กสุด ในขณะที่สำหรับโหนดภายใน การขยายและพื้นที่จะลดลง
- ในช่วงเวลาของการแยก R*-tree จะใช้การแยกทอพอโลยีที่เลือกแกนแยกตามขอบเขต จากนั้นลดการทับซ้อนกัน
- นอกเหนือจากกลยุทธ์การแยกที่ปรับปรุงแล้ว R*-tree ยังพยายามข้ามการแยกด้วยการแทรกออบเจ็กต์และทรีย่อยเข้าไปในทรีอีกครั้ง โดยได้รับแรงบันดาลใจจากแนวคิดเรื่องการทรงตัวของ B-tree
การสอบถามกรณีที่เลวร้ายที่สุดและการลบความซับซ้อนจึงคล้ายกับ R-Tree กลยุทธ์การแทรกไปยัง R*-tree โดย O(M log M) ซับซ้อนกว่ากลยุทธ์การแยกเชิงเส้น (O(M)) ของ R-tree แต่ซับซ้อนน้อยกว่ากลยุทธ์การแยกกำลังสอง (O(M
