М-дерево
-
Описание M-деревьев
- M-деревья — древовидные структуры данных, похожие на R-деревья и B-деревья.
- Используют метрику и неравенство треугольника для эффективного диапазона и запросов k-ближайшего соседа.
- Могут иметь большое перекрытие, что требует стратегии для его избежания.
- Подходят только для функций расстояния, удовлетворяющих неравенству треугольника.
-
Компоненты M-деревьев
- Набор объектов маршрутизации NRO.
- Указатель на родительский объект узла Op.
- Набор объектов НЕТ.
- Указатель на покрывающее дерево T(Или).
- Расстояние от родительского объекта d(Или,P(Или)).
- Идентификатор объекта oid(Oj).
- Расстояние Oj от родительского объекта d(Oj,P(Oj)).
-
Вставка и разделение
- Вставить: найти конечный узел N, присоединить объект O к N или вызвать метод split.
- Split: выбрать два объекта маршрутизации из N, создать новые узлы и сохранить их в новом корне или родительском узле.
-
Запросы к M-деревьям
- Запрос диапазона: выбрать все объекты Oj, такие что d(Oj, Q) ≤ r(Q).
- Запрос k-NN: выбрать k объектов, имеющих наименьшее расстояние от Q.
-
Дополнительные структуры данных
- Дерево сегментов: вырожденное R-дерево для одного измерения.
- Иерархия ограничивающих объемов.
- Пространственный индекс.
- Покровное дерево.