בעץ R קלאסי ההיוריסטיקה היא בחירת המלבן שמצריך הרחבה מינימלית של השטח שלו כדי להכניס בתוכו את הערך הנוסף, ובמקרה של שוויון ההכרעה היא על ידי בחירת המלבן שמייצג תת-עץ עם שטח קטן יותר. קיימות וריאציות משופרות של עץ R בהן יש היוריסטיקות אחרות. בעץ *R למשל נעשה שימוש בהיוריסטיקה משולבת: ברמת העלים נעשה ניסיון למזער את השטחים החופפים בין המלבנים (ובמקרה של שוויון ההכרעה היא על ידי שימוש בהיוריסטיקה של עץ R קלאסי), ואילו ברמות של צמתים פנימיים יותר בעץ נעשה ישירות שימוש בהיוריסטיקה של עץ R קלאסי.
פיצול צומת מלא.
המטרה היא לצמצם את השטח המשותף ששני המלבנים בצמתים החדשים יכסו. מספר האפשרויות לחלוקה של ערכים מצומת אחד מלא לשני צמתים חדשים הוא אקספוננציאלי למספר הערכים שיש בצומת (סיבוכיות זמן ריצה של אלגוריתם נאיבי שממצה את כל האפשרויות יכולה להגיע ל- formula_10), ולכן צריך להשתמש בהיוריסטיקה כדי למצוא חלוקה מיטבית ככל שאפשר.
גוטמן הציע שתי היוריסטיקות לפיצול צומת בעץ R קלאסי: פיצול ריבועי (quadratic split), ופיצול ליניארי (linear split). בשתי שיטות אלו מוצאים בהתחלה גרעין מתאים לכל אחת משתי קבוצות הערכים, ולאחר מכן מחלקים את שאר הערכים בין שתי הקבוצות שנוצרו בהתבסס על קריטריונים מסוימים.
קיימות אסטרטגיות נוספות לפיצול צמתים מלאים - כמו שיטת הפיצול של גרין, היוריסטיקת הפיצול של *R שכוללת מחיקה של צמתים והכנסה מחדש שלהם, שיטת הפיצול של אנג וטן, ועוד.
עדכון.
אם מבוצע עדכון לעצם שמוצבע ידי העלים והוא מוביל לשינוי המלבן החוסם המינימלי שלו, צריך למחוק את רשומת האינדקס של אותו עצם מתוך העץ (ביצוע פעולת מחיקה), ולהכניס את האינדקס המעודכן מחדש (ביצוע פעולת הכנסה). המשמעות היא שביצוע פעולות עדכון על נתונים בצורה תכופה בעץ R זה דבר יקר יחסית (דבר כזה יכול להידרש למשל עבור עצם שנע במהירות במרחב).
מחיקה.
מחיקה של ערך מצומת בעץ R כרוכה תחילה במציאה של הצומת שמכיל את הערך שביקשו למחוק אותו (פעולת חיפוש), ואם נמצא צומת מתאים, מחיקה של הערך מאותו צומת. המחיקה עלולה לגרור צורך בעדכון של ערך מלבן בצומת האב.
במהלך המחיקה ייתכן שיהיה צורך למחוק ערך מצומת השורש. אם הערך היחיד שיש בצומת השורש הוא לא עלה, מתבצעת מחיקה של צומת השורש וסימון ערך הבן היחיד שלו כצומת שורש חדש. פעולה כזו מקטינה את הגובה של העץ.
בנוסף, על עץ R מוגדר תנאי לכמות מינימום של ערכים בצומת, לכן יש להתייחס גם אליו במהלך מחיקה. הטיפול בתנאי זה יתבצע בצורה שונה מזו שבה הוא מתבצע במבנה נתונים כמו עץ +B. בעץ +B, אם מגיעים למצב שבו רמת התפוסה של ערכים בצומת מסוים היא מתחת למינימום הנדרש (מצב של חמיקה - underflow), ניתן לפי הצורך להפעיל אלגוריתם מיזוג לשני צומתי אחים - מכיוון שהעץ מכיל אינדקס חד ממדי שהערכים ממוינים לפיו. לעומת זאת, במידע רב ממדי, התכונה הזאת לא מתקיימת בהכרח.
לכן, במקום זאת, גוטמן הציע לבצע הכנסה מחדש של כל הערכים שנותרו בצומת שהיה בתת-תפוסה, ולמחוק אותו לחלוטין מהעץ. שיטה זו מאפשרת מימוש פשוט יותר של האלגוריתם כי היא עושה שימוש באלגוריתם של פעולת ההכנסה ונמנעת מאלגוריתם מיזוג ייעודי. כמו כן יש לה יתרון בעבודה עם בסיסי נתונים, מאחר שהדפים שדרושים להכנסה מחדש היו צריכים להיטען לחוצץ בזיכרון הפנימי כבר במהלך החיפוש של הרשומה שביקשו למחוק. כמו כן, מחיקה של נתונים פוגעת באיכות המלבנים החוסמים בעץ (על ידי יצירת שטחים ריקים וחפיפות בין מלבנים שכבר לא הכרחיות), והכנסה של נתונים מחדש אמורה לצמצם תופעות אלו.
שאילתות חיפוש מרחביות.
חיפוש תחום.
החיפוש הסטנדרטי בעץ R הוא חיפוש תחום (range searching) בו מחפשים עצמים שנמצאים בתחום מסוים במרחב שניתן כקלט. בעץ R קלט של חיפוש כזה הוא מלבן (שמכונה בשמות 'תחום', 'חלון', ו'מלבן שאילתה'), והתוצאה הרצויה היא קבוצה של העצמים שמוצבעים מעלי העץ וחופפים לאותו מלבן או מוכלים בו. מקרה פרטי לחיפוש כזה הוא כשהקלט מייצג נקודה.
חיפוש תחום נעשה בצורה דומה לחיפוש בעץ +B. כל צומת פנימי בעץ מכיל קבוצת ערכים שמייצגים מלבנים וקבוצת מצביעים לצומתי בנים, וכל עלה מכיל מצביעים לעצמים עצמם במרחב. החיפוש מתחיל בצומת השורש של העץ, ונעשית בדיקה לכל מלבן בקבוצת המלבנים בצומת האם יש חפיפה כלשהי בינו לבין קלט החיפוש. אם יש חפיפה כזו צריך להמשיך לבצע את החיפוש בצומת הבן בצורה דומה. החיפוש ממשיך בצורה רקורסיבית כך שהאלגוריתם יבקר בכל הצמתים שבהם הייתה חפיפה כלשהי לקלט החיפוש.
כשמגיעים לעלה, ייתכן מצב של חפיפה שגויה (false overlap) שבו המלבן החוסם המינימלי חופף לקלט החיפוש, אבל העצם החסום (שהוא לא בהכרח מלבן) לא חופף אליו. בשל כך יש לבדוק את החפיפה גם עבור העצם שמוצבע מהעלה. כשנמצאת חפיפה בין עצם באחד העלים לקלט החיפוש, אותו עצם מתווסף לקבוצת הערכים של התוצאה. ייתכן שבחיפוש מסוים לא יימצא אף עצם מתאים.
חיפוש השכן הקרוב ביותר.
ישנן פעולות חיפוש נוספות שנפוצות בעץ R. למשל, חיפוש השכן הקרוב ביותר (nearest neighbor search), שמטרתו למצוא עצם שהוא השכן שקרוב ביותר במרחב ה-n ממדי לנקודה או למלבן מסוימים שניתנים כקלט.
אלגוריתם בצורה של הסתעף וחסום לביצוע חיפוש כזה בעץ R הוצע על ידי Roussopoulos, Kelley ו-Vincent בשנת 1995. לצורך האלגוריתם מוגדרות שתי מטריקות בין נקודה במרחב ה-n ממדי לנקודה אחרת במלבן n-ממדי באותו מרחב: מטריקת מרחק מינימלי, ומטריקת מרחק מינימקס. שיפור של האלגוריתם שמייעל את החישובים ומשתמש במטריקת מרחק מינימלי בלבד הוצג על ידי Cheung ו-Fu בשנת 1998.
צירוף מרחבי.
פעולות חיפוש מסוג אחר הן פעולות שמצריכות סריקה חוזרת של העצמים שבמרחב. פעולה נפוצה כזו היא פעולת חיפוש של צירוף מרחבי (spatial join) עם פרדיקט של חיתוך שמוגדרת בצורה הבאה: עבור שני יחסים שמכילים קבוצות של עצמים במרחב, הצירוף המרחבי שלהם הוא קבוצת כל העצמים שחופפים בין הקבוצות. פעולה זו היא למעשה הרחבה של חיפוש תחום, כך שקלט החיפוש שהכיל מלבן יחיד יכיל קבוצה של מלבנים.
אלגוריתם נאיבי לצירוף מרחבי כזה הוא אלגוריתם שעושה שימוש בלולאות מקוננות והוא לא יעיל במיוחד בסיבוכיות זמן ריצה שלו עבור קבוצות גדולות של עצמים. אלגוריתמים שונים שמבוססים על עץ R ועל וריאציות שלו הוצעו כדי לייעל את הפעולה.
אחד האלגוריתמים הראשונים שמטרתו לבצע צירוף מרחבי בין שני יחסים שמיוצגים בשני עצי R עם גבהים שונים הוצע על ידי Brinkhoff, Kriegel, ו-Seeger ב-1993. אלגוריתם זה מכונה לפעמים אלגוריתם RJ (R-tree Join) או אלגוריתם התאמת עץ, ופועל בצורה של חיפוש לעומק:
למצבים בהם רק אחד מהיחסים מיוצג בעץ R, הוצע אלגוריתם לבניית עץ מתאים ליחס השני על ידי Lo ו-Ravishankar בשנת 1994. מבנה הנתונים הנוסף שמוגדר עבור היחס השני הוא עץ שתול (seeded tree) והוא מתבסס על ערכים מהעץ R שכבר נתון. הרעיון בבנייה כזו הוא לצמצם את כמות החפיפות שיימצאו בין זוגות מלבנים בעצים השונים ובכך לבנות עץ שמתאים יותר לחיפוש של צירוף מרחבי מלחיפוש תחום.
וריאציות.
רוב המחקר בעצי R (נכון ל-2017) נעשה בתחומים הבאים:
וריאציות דינמיות.
הקושי בבניית עץ R הוא שמצד אחד צריך לבנות עץ שהוא מאוזן, ומצד שני צריך שמלבנים לא יחפפו יותר מדי, כך שבמהלך חיפוש נתונים לא יהיה צורך לבקר בתתי עצים רבים, וכן שמלבנים לא יכסו יותר מדי אזורים ריקים (אזורים שלא מכוסים על ידי שטח מלבני בנים) כי אז אזורי החפיפה גדלים. וריאציות שונות של עץ R הוצעו כדי לשפר את פעולות ההכנסה, העדכון והמחיקה של הנתונים.
מקביליות.
ניתן לאחסן עץ R בארכיטקטורת חומרה שמורכבת מכמה אמצעי זיכרון חיצוניים, למשל דיסקים קשיחים. יעילות של שיטת אחסון כזו נבחנת בהקטנת זמן התגובה של פעולות בעץ.
מידע מרחבי-זמני.
הרחבות שונות עוסקות במצבים שבהם יש עצמים רבים שנעים במרחב ומדווחים את נקודת המיקום העדכנית שלהם למשך זמן מסוים בתדירות גבוהה. שאילתות חיפוש נפוצות שמבוצעות על עצמים כאלו הן ביצוע חיפוש תחום עם קלט שנע במרחב בקטע מסוים של הזמן, ובפרט שאילתת חתך זמן (מיקום של עצמים במרחב בנקודת זמן מסוימת).
מידע מרחבי-טקסטואלי.
הרחבות שונות עוסקות בנקודות במרחב שלכל אחת מהן מוצמד מסמך טקסט עם מלל תיאורי:
ממדים מסדר גבוה.
הגדלת כמות הממדים בעץ R שמאחסן מידע מרחבי פוגעת ביעילות של השימוש באינדקס, ובמקרים מסוימים השימוש באינדקס עלול אפילו להיות גרוע יותר מסריקה סדרתית של הנתונים. תופעה כזו נצפתה גם בשיטות אחרות, והיא מכונה בצורה כללית גם קללת הממד. וריאציות שונות הוצעו בניסיון לזהות את הגורמים הספציפיים לתופעה בעץ R ולהימנע מהם.
הקרב בסואץ
חיל האוויר ה-24 של ארצות הברית
חיל האוויר ה-24 של ארצות הברית (באנגלית: Twenty-Fourth Air Force) שימש פיקוד הסייבר של חיל האוויר של ארצות הברית (בקיצור: AFCYBER). הפיקוד פעל תחת פיקוד החלל של חיל האוויר ומשרת את פיקוד הסייבר של ארצות הברית. באוקטובר 2019 מוזג הפיקוד לתוך חיל האוויר ה-16 של ארצות הברית.
היסטוריה.