엠트리

알고리즘 삽입 입력: M-Tree MT의 노드 N, 엔트리 ${\displaystyle {On}_{}}$ ${\$ 출력$$:원본 MT + $O{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$의 모든 항목을 포함하는 MT의 새 인스턴스

${\displaystyle N_{e}\gets N}$'s routing objects or objects   if N is not a leaf then   {        /* Look for entries that the new object fits into */        let ${\displaystyle N_{in}}$ be routing objects from ${\displaystyle N_{e}}$'s set of routing objects ${\displaystyle N_{RO}}$ such that ${\displaystyle d(O_{r},O_{n})\leq r(O_{r})}$ if ${\displaystyle N_{in}}$ is not empty then        {           /* If there are one or more entry, then look for an entry such that is closer to the new object */           ${\displaystyle O_r^{\ast }\leftarrow \underset{O_r\in N_{in}}{min}d(O_r,}$${\displaystyle O_{r}^{*}\gets \min _{O_{r}\in N_{in}}d(O_{r},O_{n})}$        }        else        {           /* If there are no such entry, then look for an object with minimal distance from */            /* its covering radius's edge to the new object */           ${\displaystyle O_r^{\ast }\leftarrow \underset{O_r\in N_{in}}{min}d(O_r,O_n)}$${\displaystyle O_{r}^{*}\gets \min _{O_{r}\in N_{in}}d(O_{r},O_{n})-r(O_{r})}$           /* Upgrade the new radii of the entry */           ${\displaystyle r(O_{r}^{*})\gets d(O_{r}^{*},O_{n})}$        }        /* Continue inserting in the next level */        return insert($$${\$$O_{n}}$); else   {        /* If the node has capacity then just insert the new object */        if N is not full then        { store(${\displaystyle N,O_{n}}$) }        /* The node is at full capacity, then it is needed to do a new split in this level */        else        { split(${\displaystyle N,O_{n}}$) }}

• "직접"은 할당을 의미한다.예를 들어, "가장 큰 ←항목"은 가장 큰 값이 항목의 가치를 변화시킨다는 것을 의미한다.
• "return"은 알고리즘을 종료하고 다음 값을 출력한다.

알고리즘 분할 입력: M-Tree MT의 노드 N, 엔트리 ${\displaystyle {On}_{}}$ ${\$ 출력$$:새 파티션을 포함하는 MT의 새 인스턴스. 

/* 이제 새로운 라우팅 개체는 노드에 있는 모든 개체와 새로운 라우팅 개체 $*/$N이 루트가 아닌 경우$$ { /*${\displaystyle \mathrm{상위}}$노드와 상위 라우팅 개체 $가져오기$*/ $O$p {\$displaystyle$ $O_{p}$가 N의 상위 라우팅 개체인 경우 N${\displaystyle }$let O {\$displaystyle$ O_${$p}가 $N$의 상위 라우팅 개체로 $표시됨{\displaystyle {}_{}}$$yle N_{p}}$ be the parent node of N   }   /* This node will contain part of the objects of the node to be split */   Create a new node N'   /* Promote two routing objects from the node to be split, to be new routing objects */   Create new objects ${\displaystyle O_{p1}}$ and ${\displaystyle O_{p2}}$.   Promote(${\displaystyle }$${\displaystyle N,O_{p1},O_{p2}}$)   /* Choose which objects from the node being split will act as new routing objects */   Partition(${\displaystyle N,O_{p1},O_{p2},N_{1},N_{2}}$)   /* Store entries in each new routing object */   Store ${\displaystyle N_{$$1}}$'s entries in N and ${\displaystyle N_{2}}$'s entries in N' if N is the current root then   {       /* Create a new node and set it as new root and store the new routing objects */       Create a new root node ${\displaystyle N_{p}}$ Store ${\displaystyle O_{p1}}$ and ${\displaystyle O$$_{p2}}$ in ${\displaystyle N_{p}}$   }   else   {       /* Now use the parent routing object to store one of the new objects */       Replace entry ${\displaystyle O_{p}}$ with entry ${\displaystyle O_{p1}}$ in ${\displaystyle N_{p}}$ if ${\displaystyle N_{p}}$ is no full then{ /* 두 번째 라우팅 개체는 여유 용량이 있는 경우에만 상위 항목에 저장된다 */ N p ${\$에 O ${\displaystyle {\mathrm{p}}_{}}$ ${\displaystyle 2_{}}$ ${\$ $N$ ${\displaystyle p_{}}$ {\p} 다른 /*사용 가능한 용량이 없는 경우 레벨을 위로 분할*/$$ 분할(${\displaystyle N_{}}$ p${\displaystyle {}_{}}$, O ${\displaystyle {\mathrm{p}}_{}}$ ${\displaystyle 2_{}}$ ${\$)$tyle N_{p},O_{p2}}$ )$$}}

• "직접"은 할당을 의미한다.예를 들어, "가장 큰 ←항목"은 가장 큰 값이 항목의 가치를 변화시킨다는 것을 의미한다.
• "return"은 알고리즘을 종료하고 다음 값을 출력한다.

알고리즘 범위검색 입력: M-Tree MT의 노드 N, Q: 쿼리 개체, $r{\displaystyle }$( ${\displaystyle Q}$) ${\displaystyle$ r$(Q)}$: 검색 반지름

$출력{\displaystyle }$: d${\displaystyle }$( ${\displaystyle O}$ j${\displaystyle }$, ${\displaystyle Q}$) ${\displaystyle \le }$ ${\displaystyle r}$( ${\displaystyle Q}$) ${\displaystyle d(Oj,Q)\leq$ r$(Q)}$과 같은 모든 DB 개체

{    let ${\displaystyle O_{p}}$ be the parent object of node N; if N is not a leaf then {      for each entry(${\displaystyle O_{r}}$) in N do {           if ${\displaystyle  d(O_{p},Q)-d(O_{r},O_{p}) \leq r(Q)+r(O_{r})}$ then {Compute ${\displaystyle d(O_{r},Q)}$; if ${\displaystyle d(O_{r},Q)\leq r(Q)+r(O_{r})}$ then RangeSearch(*ptr(${\displaystyle T(O_{r}}$)),Q,${\displaystyle r(Q)}$);            }     }   }   else {      for each entry(${\displa$$ystyle O_{j}}$) in N do {           if ${\displaystyle  d(O_{p},Q)-d(O_{j},O_{p}) \leq r(Q)}$ then {              Compute ${\displaystyle d(O_{j},Q)}$; if ${\displaystyle d(O_{j},Q)}$ ≤ ${\displaystyle r(Q)}$ then add $$${\displaystyle o}$ ${\displaystyle id}$ ( ${\displaystyle O_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle oid(O_{j}})$ 결과: } } } }

• "직접"은 할당을 의미한다.예를 들어, "가장 큰 ←항목"은 가장 큰 값이 항목의 가치를 변화시킨다는 것을 의미한다.
• "return"은 알고리즘을 종료하고 다음 값을 출력한다.