עץ R

דוגמה לעץ R דו ממדי שנבנה על בסיס המלבנים R8-R19, מבוסס על דוגמה מתוך המאמר המקורי על עצי R של אנטונין גוטמן

ב מדעי המחשב, עץ R הוא מבנה נתונים בצורת עץ שנועד לשמש לגישה ל מידע מרחבי, כלומר לנתונים עם אופי רב ממדי. נתונים אלו יכולים להיות קואורדינטות גאוגרפיות, מלבנים ו צורות גאומטריות נוספות. עץ R הוצע לראשונה על ידי אנטונין גוטמן בשנת 1984, [1] ומאז נעשה בו שימוש תאורטי ומעשי נרחב. [2] האות R בשם של מבנה הנתונים היא קיצור למילה מלבן באנגלית - Rectangle.

סקירה

מבנה הנתונים של עץ R התבסס על עץ +B, והוא תוכנן כך ש חיפוש של מידע מרחבי באמצעותו יצריך מעט גישות לצמתים ויתבצע בצורה מהירה. עץ R הוא עץ חיפוש מאוזן, שבו כל צומתי העלים של העץ הם באותו גובה, והעלים מכילים רשומות אינדקס ומצביעים לערכים ב בסיס נתונים.

לכל הצמתים בעץ מוגדר סף מקסימום של ערכים שניתן לאחסן בהם, שמסומן כפרמטר . כמות הערכים שניתנים לאחסון בצומת היא למעשה כמות הבנים שיכולים להסתעף ממנו והיא מכונה גם רמת הסתעפות (branching factor). האחסון הקבוע של עץ R הוא לרוב בזיכרון חיצוני למחשב, כי האינדקס נוטה להיות גדול מדי לאחסון ב חוצץ בזיכרון הפנימי (שהקיבולת שלו קטנה יחסית). לכן נוח להגדיר גודל של צומת בעץ כך שיהיה זהה בקירוב לגודל של דף, ובכך בכל קריאה מהזיכרון החיצוני לפנימי יישלף צומת אחד. פרמטר המקסימום נקבע בפועל כך שניתן יהיה למלא דף בזיכרון בצורה מלאה ככל האפשר, וחישוב נתון זה מבוסס בעיקרו על גודל השדות ברשומת אינדקס וצורת ה דחיסה שלהם בצומתי העץ, גודל מצביע (מושפע מגודל כתובת בזיכרון), וגודל הדף.

בנוסף מוגדר סף מינימום של ערכים שיכול להיות בצומת כפרמטר שמקיים את התנאי . הגדרת סף מינימום זה מאפשרת לאכוף תפוסה מסוימת של ערכים בצמתים והיא משפיעה על האיזון של העץ. מצד אחד, אכיפה של תפוסה גבוהה מקטינה את כמות הצמתים ומשפיעה על גובה העץ להיות קטן, דבר שיוביל להקטנת כמות הקריאות של צמתים לזיכרון ולייעול הביצועים של חיפוש נתונים. מצד שני, אכיפה של תפוסה גבוהה מגדילה את כמות הצעדים הממוצעת שמבוצעת בכל פעולת הכנסה ומחיקה בעץ (כי נדרש לבצע פיצול צמתים ומחיקה שלהם בתדירות גבוהה יותר), ובכך מייקרת את עלות הביצועים שלהם.

בכל צומת שאינו השורש יש בין ל- ערכים. עבור עץ  R שמכיל רשומות אינדקס, מתקיים שגובה העץ הוא לכל היותר .‏ [3]

הרעיון העיקרי בעץ R הוא לקבץ עצמים שסמוכים זה לזה ב מרחב n-ממדי, ולייצג אותם ברמה גבוהה יותר בעץ על ידי ה מלבן ה-n ממדי הקטן ביותר שמקיף אותם ומקביל לצירים. מלבן זה מכונה גם מלבן חוסם מינימלי (Minimum Bounding Rectangle, MBR). מידע יאוחסן בעץ בצורה הבאה:

  • ערך שמאוחסן בצומת עלה הוא זוג סדור שיכיל שני נתונים - עצם שמייצג נקודה או מלבן חוסם מינימלי במרחב n-ממדי, ומזהה ייחודי לאותו עצם בבסיס הנתונים.
  • ערך שמאוחסן בצומת פנימי שאינו עלה הוא זוג סדור שיכיל שני נתונים - מלבן במרחב n-ממדי שמכסה את המלבנים של הערכים בצומתי הבנים שלו, ומצביע לצומת בן שלו בעץ.

מלבנים יכולים לחפוף בשטח שלהם זה לזה (כלומר יש חיתוך גאומטרי ביניהם), זאת בניגוד למבני נתונים כמו  עץ +B או עץ kd שם אין חפיפות בין ערכים שמייצגים תחום של נתונים שמאוחסנים בצמתים.

Other Languages
English: R-tree
čeština: R-strom
Deutsch: R-Baum
español: Árbol-R
hrvatski: R-stablo
italiano: R-tree
日本語: R木
한국어: R 트리
polski: R-drzewo
português: Árvores R
српски / srpski: Р-стабло
українська: R-дерево
中文: R树