М ағашы - M-tree - Wikipedia

Алгоритм Кірісті енгізу: түйін N M-Tree MT, Кіру ${ displaystyle O_ {n}}$  Шығарылым: жаңа данасы MT барлық жазбаларды түпнұсқада қамтиды MT плюс ${ displaystyle O_ {n}}$

  ${ displaystyle N_ {e}  алады N}$бағыттау объектілері немесе объектілері егер N жапырақ емес содан кейін  {/ * Жаңа нысанға сәйкес келетін жазбаларды іздеңіз * / рұқсат етіңіз ${ displaystyle N_ {in}}$ объектілерді бағыттау ${ displaystyle N_ {e}}$маршруттау объектілерінің жиынтығы ${ displaystyle N_ {RO}}$ осындай ${ displaystyle d (O_ {r}, O_ {n})  leq r (O_ {r})}$       егер ${ displaystyle N_ {in}}$ бос емес содан кейін       {/ * Егер бір немесе бірнеше жазба болса, жаңа нысанға жақын жазба іздеңіз * / ${ displaystyle O_ {r} ^ {*}  gets  min _ {O_ {r}  in N_ {in}} d (O_ {r}, O_ {n})}$       }       басқа       {/ * Егер мұндай жазба болмаса, онда * / / * оның радиусының шетінен жаңа объектіге дейінгі ең аз қашықтықтағы объектіні іздеңіз * / ${ displaystyle O_ {r} ^ {*}  gets  min _ {O_ {r}  in N_ {in}} d (O_ {r}, O_ {n}) - r (O_ {r})}$          / * Жазбаның жаңа радиустарын жаңартыңыз * / ${ displaystyle r (O_ {r} ^ {*})  d (O_ {r} ^ {*}, O_ {n})} алады$       } / * Келесі деңгейге енгізуді жалғастыру * / қайту кірістіру (${ displaystyle T (O_ {r} ^ {*}), O_ {n}}$);  басқа  {/ * Егер түйіннің сыйымдылығы болса, онда жаңа нысанды енгізіңіз * / егер N толық емес содан кейін       { дүкен (${ displaystyle N, O_ {n}}$) } / * Түйін толық қуатында, содан кейін осы деңгейде жаңа сплит жасау қажет * / басқа       { Сызат(${ displaystyle N, O_ {n}}$) }  }

• «←» дегенді білдіреді тапсырма. Мысалы, »ең үлкен ← элемент«деген мағынаны білдіреді ең үлкен мәніне өзгереді элемент.
• "қайту«алгоритмді тоқтатады және келесі мәнді шығарады.

Алгоритм Бөлуді енгізу: түйін N M-Tree MT, Кіру ${ displaystyle O_ {n}}$  Шығарылым: жаңа данасы MT құрамында жаңа бөлім бар.

  / * Жаңа маршруттау объектілері енді түйіндегі барлық және жаңа маршруттау объектісі болып табылады * / let NN жазбалары ${ displaystyle N  cup O}$  егер N түбір емес содан кейін  {/ * Ата-ана түйіні мен ата-аналық маршруттау нысанын алыңыз * / рұқсат етіңіз ${ displaystyle O_ {p}}$ ата-аналық маршруттау объектісі бол N     рұқсат етіңіз ${ displaystyle N_ {p}}$ ата-анасының түйіні болыңыз N  } / * Бұл түйінде бөлінетін түйін нысандарының бөлігі болады * / Жаңа түйін жасаңыз N '  / * Бөлінген түйіннен екі маршруттау нысанын алға жылжыту, жаңа маршруттау объектілері болу * * Жаңа объектілерді құру ${ displaystyle O_ {p1}}$ және ${ displaystyle O_ {p2}}$.  Жарнамалау (${ displaystyle N, O_ {p1}, O_ {p2}}$) * * Бөлінетін түйіннен қандай нысандар жаңа маршруттау объектілері болатынын таңдаңыз * / Бөлім (${ displaystyle N, O_ {p1}, O_ {p2}, N_ {1}, N_ {2}}$) / * Әр жаңа маршруттау объектісінде жазбаларды сақтау * / Дүкен ${ displaystyle N_ {1}}$жазбалар N және ${ displaystyle N_ {2}}$жазбалар N '  егер N ағымдағы түбір содан кейін  {/ * Жаңа түйін жасаңыз және оны жаңа түбір етіп орнатыңыз және жаңа бағыттау объектілерін сақтаңыз * / Жаңа түбір түйінін жасаңыз ${ displaystyle N_ {p}}$      Дүкен ${ displaystyle O_ {p1}}$ және ${ displaystyle O_ {p2}}$ жылы ${ displaystyle N_ {p}}$  }  басқа  {/ * Енді жаңа нысандардың бірін сақтау үшін ата-аналық маршруттау нысанын қолданыңыз * / Жазбаны ауыстырыңыз ${ displaystyle O_ {p}}$ кіруімен ${ displaystyle O_ {p1}}$ жылы ${ displaystyle N_ {p}}$      егер ${ displaystyle N_ {p}}$ толық емес содан кейін      {/ * Екінші маршруттау нысаны ата-анасында бос сыйымдылығы болған жағдайда ғана сақталады * / Дүкен ${ displaystyle O_ {p2}}$ жылы ${ displaystyle N_ {p}}$      }      басқа      {/ * Егер бос сыйымдылық болмаса, онда деңгейді бөліңіз * / Сызат(${ displaystyle N_ {p}, O_ {p2}}$)      }  }

• «←» дегенді білдіреді тапсырма. Мысалы, »ең үлкен ← элемент«деген мағынаны білдіреді ең үлкен мәніне өзгереді элемент.
• "қайту«алгоритмді тоқтатады және келесі мәнді шығарады.

Алгоритм RangeSearchInput: түйін N M-Tree MT, Q: сұрау нысаны, ${ displaystyle r (Q)}$: іздеу радиусы

Шығу: барлық ДБ нысандары осындай ${ displaystyle d (Oj, Q)  leq r (Q)}$

{   рұқсат етіңіз ${ displaystyle O_ {p}}$ болуы түйіннің негізгі нысаны N;  егер N емес жапырақ содан кейін {     әрқайсысы үшін кіру(${ displaystyle O_ {r}}$) жылы N істеу {          егер ${ displaystyle | d (O_ {p}, Q) -d (O_ {r}, O_ {p}) |  leq r (Q) + r (O_ {r})}$ содан кейін {             Есептеу ${ displaystyle d (O_ {r}, Q)}$;            егер ${ displaystyle d (O_ {r}, Q)  leq r (Q) + r (O_ {r})}$ содан кейін              RangeSearch(* ptr (${ displaystyle T (O_ {r}}$)),Q,${ displaystyle r (Q)}$);           }    }  }  басқа {     әрқайсысы үшін кіру(${ displaystyle O_ {j}}$) жылы N істеу {          егер ${ displaystyle | d (O_ {p}, Q) -d (O_ {j}, O_ {p}) |  leq r (Q)}$ содан кейін {             Есептеу ${ displaystyle d (O_ {j}, Q)}$;            егер ${ displaystyle d (O_ {j}, Q)}$ ≤ ${ displaystyle r (Q)}$ содан кейін              қосу ${ displaystyle oid (O_ {j})}$ нәтижеге;          }    }  }}

• «←» дегенді білдіреді тапсырма. Мысалы, »ең үлкен ← элемент«деген мағынаны білдіреді ең үлкен мәніне өзгереді элемент.
• "қайту«алгоритмді тоқтатады және келесі мәнді шығарады.