М-дерево

Вставка алгоритма Вход: Узел N М-дерева 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}^{*})\gets d(O_{r}^{*},O_{n})}$ } / * Продолжаем вставку на следующем уровне * / return insert ( ); ${\displaystyle T(O_{r}^{*}),O_{n}}$ еще { / * Если узел имеет емкость, просто вставьте новый объект * / если  N не заполнено, то { store ( )${\displaystyle N,O_{n}}$ } / * Узел загружен на полную мощность, тогда необходимо сделать новое разбиение на этом уровне * / еще { split ( )${\displaystyle N,O_{n}}$ } }

• «←» обозначает присвоение . Например, « самый большой ← элемент » означает, что значение самого большого элемента изменяется на значение элемента .
• « return » завершает алгоритм и выводит следующее значение.

Алгоритм разделения Вход: узел N M-Tree MT , входной${\displaystyle O_{n}}$ выход: новый экземпляр MT, содержащий новый раздел.

 / * Новые объекты маршрутизации теперь все те, что находятся в узле, плюс новый объект маршрутизации * / пусть будет NN записей, если N не является корнем, то${\displaystyle N\cup O}$   { / * Получить родительский узел и родительский объект маршрутизации * / пусть будет родительским объектом маршрутизации N,${\displaystyle O_{p}}$  пусть будет родительским узлом N${\displaystyle N_{p}}$ } / * Этот узел будет содержать часть объектов разделяемого узла * / Создайте новый узел N ' / * Продвигает два объекта маршрутизации из узла, который нужно разделить, в новые объекты маршрутизации * / Создавайте новые объекты и .  Продвигать ( )${\displaystyle O_{p1}}$${\displaystyle O_{p2}}$${\displaystyle N,O_{p1},O_{p2}}$ / * Выбираем, какие объекты из разделяемого узла будут действовать как новые объекты маршрутизации * / Раздел ( )${\displaystyle N,O_{p1},O_{p2},N_{1},N_{2}}$ / * Сохранение записей в каждом новом объекте маршрутизации * / Сохранять записи в N и записи в N,${\displaystyle N_{1}}$${\displaystyle N_{2}}$  если  N - текущий корень, тогда { / * Создаем новый узел и устанавливаем его как новый корень и сохраняем новые объекты маршрутизации * / Создайте новый корневой узел ${\displaystyle N_{p}}$ Store и в${\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}}$ } }

• «←» обозначает присвоение . Например, « самый большой ← элемент » означает, что значение самого большого элемента изменяется на значение элемента .
• « return » завершает алгоритм и выводит следующее значение.

Алгоритм RangeSearchВход: узел N M-Tree MT, Q : объект запроса,: радиус поиска${\displaystyle r(Q)}$

Вывод: все объекты БД, такие что${\displaystyle d(Oj,Q)\leq r(Q)}$

{ пусть  будет родительским объектом узла N ;${\displaystyle O_{p}}$  если  N  не является листом, то { для каждой  записи ( ) в N${\displaystyle O_{r}}$   выполните { if ${\displaystyle |d(O_{p},Q)-d(O_{r},O_{p})|\leq r(Q)+r(O_{r})}$  then { Вычислить ; ${\displaystyle d(O_{r},Q)}$ если ${\displaystyle d(O_{r},Q)\leq r(Q)+r(O_{r})}$  тогда  RangeSearch (* ptr ( )), Q , );${\displaystyle T(O_{r}}$${\displaystyle r(Q)}$  } } } else { для каждой  записи ( ) в N${\displaystyle O_{j}}$   do { if ${\displaystyle |d(O_{p},Q)-d(O_{j},O_{p})|\leq r(Q)}$  then { Compute ; ${\displaystyle d(O_{j},Q)}$ если ≤, ${\displaystyle d(O_{j},Q)}$${\displaystyle r(Q)}$ то  прибавить к результату;${\displaystyle oid(O_{j})}$ } } }}

• «←» обозначает присвоение . Например, « самый большой ← элемент » означает, что значение самого большого элемента изменяется на значение элемента .
• « return » завершает алгоритм и выводит следующее значение.