K-D-B-дерево - K-D-B-tree - Wikipedia

В Информатика, а K-D-B-дерево (k-размерный B-дерево ) представляет собой древовидную структуру данных для разделения k-мерное пространство поиска. Цель K-D-B-дерево обеспечить эффективность поиска сбалансированной k-d дерево, обеспечивая блочно-ориентированное хранилище B-дерева для оптимизации доступа к внешней памяти.^[1]

Неформальное описание

Как и k-d дерево, K-D-B-дерево организует точки в k-мерное пространство, полезное для таких задач, как поиск по диапазонам и многомерные запросы к базе данных. K-D-B-деревья подразделяют пространство на два подпространства, сравнивая элементы в одной области. Используя в качестве примера 2-D-B-дерево (2-мерное K-D-B-дерево), пространство подразделяется таким же образом, как и k-d дерево: при использовании точки только в одном из доменов или осей в этом случае все другие значения либо меньше, либо больше текущего значения, и падают слева и справа от плоскости разделения соответственно.

В отличие от k-d дерево, каждое полупространство не является собственным узлом. Вместо этого, как и в B-дереве, узлы в K-D-B-дереве хранятся как страницы, а дерево хранит указатель на корневую страницу.

Структура

Базовая структура K-D-B-дерева.

K-D-B-дерево содержит два типа страниц:

• Страницы регионов: коллекция (регион, ребенок) пары, содержащие описание ограничивающей области вместе с указателем на дочернюю страницу, соответствующую этой области.
• Страницы точек: коллекция (точка, место) пары. В случае баз данных место расположения может указывать на индекс записи в базе данных, а для точек в k-мерное пространство, его можно рассматривать как координаты точки в этом пространстве.

Переполнение страницы происходит, когда вставка элемента в K-D-B-дерево приводит к тому, что размер узла превышает его оптимальный размер. Поскольку целью K-D-B-дерева является оптимизация доступа к внешней памяти, например, с жесткого диска, страница считается переполненной или переполненной, если размер узла превышает размер страницы внешней памяти.

Во время операций вставки / удаления K-D-B-дерево поддерживает определенный набор свойств:

• Граф представляет собой многостороннее дерево. Страницы регионов всегда указывают на дочерние страницы и не могут быть пустыми. Точечные страницы - это листовые узлы дерева.
• Как и в случае B-дерева, длина пути к листьям дерева одинакова для всех запросов.
• Регионы, составляющие страницу региона, не пересекаются.
• Если корнем является страница региона, то объединение его регионов составляет все пространство поиска.
• Когда ребенок из (регион, ребенок) пара на странице региона также является страницей региона, объединение всех регионов в дочернем область, край.
• Наоборот, в случае выше, если ребенок это страница точек, все точки в ребенок должен содержаться в область, край.

Операции над K-D-B-деревом

Запросы

Запросы на K-D-B-дереве - это поиск диапазона по интервалам во всех доменах или осях дерева. Этот набор интервалов называется область запроса. В k-пространство, область запроса можно визуализировать как ограничивающий объем вокруг некоторого подпространства во всем k-мерное пространство поиска. Запрос можно разделить на три категории:

• Некоторые интервалы охватывают весь домен или ось, что делает запрос частичный диапазон запрос.
• Некоторые интервалы являются точками, другие - полными доменами, поэтому запрос является частичное совпадение запрос.
• Все интервалы - это точки, поэтому ограничивающий объем также является точкой. Это полное совпадение запрос.

Алгоритм

1. Если корень дерева имеет значение null, завершение, в противном случае пусть страница быть корень.
2. Если страница это страница точек, возвращать каждые точка в (точка, место) пара, которая находится внутри область запроса.
3. Иначе, страница это страница региона, поэтому для всех (регион, ребенок) пары, где область, край и область запроса пересечь, установить страница быть ребенок и рекурсивно с шага 2.

Вставки

Поскольку вставка в K-D-B-дерево может потребовать разделения страницы в случае переполнения страницы, важно сначала определить операцию разделения.

Алгоритм разделения

Сначала страница региона разделяется по некоторой плоскости, чтобы создать две новые страницы региона, левую и правую. Эти страницы заполняются регионами со старой страницы региона, а старая страница региона удаляется. Тогда для каждого (область, край, ребенок) на исходной странице региона, запомнив ребенок это страница и область, край указывает фактическую ограничивающую область:

1. Если область, край лежит полностью слева от плоскости разделения, добавьте (регион, ребенок) на левую страницу.
2. Если область, край лежит полностью справа от плоскости разделения, добавьте (регион, ребенок) на правую страницу.
3. Иначе:
   1. Рекурсивно разделить ребенок плоскостью разделения, в результате чего страницы new_left_page и new_right_page
   2. Расколоть область, край плоскостью расщепления, в результате чего left_region и right_region
   3. Добавлять (left_region, new_left_page) на левую страницу и (правая_регион, новая_права_страница) на правую страницу.

Алгоритм вставки

Важность выбора правильного домена расщепления.

Используя алгоритм разделения, вставки нового (точка, место) пара может быть реализована следующим образом:

1. Если корневая страница имеет значение NULL, просто сделайте корневую страницу новой точечной страницей, содержащей (точка, место)
2. Если запрос точного соответствия на точка найти страницу, которая point 'следует добавить в. Если он уже существует на странице, прекратите.
3. Добавлять (точка, место) на страницу. Если страница переполняется, пусть страница обозначают эту страницу.
4. Позволять old_page быть равным страница. Выберите элемент и область / ось, чтобы определить плоскость для разделения страница это приводит к появлению двух страниц, что также не приведет к переполнению одной из страниц с добавлением новой точки. Расколоть страница самолетом сделать две новые страницы, new_left_page и new_right_page, и два новых региона left_region и right_region.
5. Если страница была корневой страницей, переходите к шагу 6. ​​В противном случае страница становится родителем страница. Заменять (регион, старая_страница) в страница с (left_region, new_left_page) и (правая_регион, новая_права_страница). Если страница переполнение, повторите шаг 4, в противном случае прекратите.
6. Позволять left_region - все пространство поиска слева от плоскости разделения, и right_region - пространство поиска справа, полученное в результате разделения на шаге 4. Установите корневую страницу как страницу, содержащую регионы left_region и right_region.

Важно позаботиться о домене и элементе, выбранном для разделения. страница на, поскольку желательно попытаться сбалансировать количество точек по обе стороны от плоскости разделения. В некоторых случаях неправильный выбор домена разделения может привести к нежелательному разделению. Также возможно, что страницу нельзя разделить по определенному домену.

Удаления

Удаление из K-D-B-дерева невероятно просто, если не предъявляются минимальные требования к использованию хранилища. Используя запрос точного соответствия, чтобы найти (точка, место) пара, мы просто удаляем запись из дерева, если она существует.

Алгоритм реорганизации

Поскольку в результате удаления могут появиться страницы, содержащие очень мало данных, может потребоваться реорганизация K-D-B-дерева для соответствия некоторым критериям минимального использования хранилища. Если на странице слишком мало данных, следует использовать следующий алгоритм реорганизации:

1. Позволять страница быть родителем п, содержащий (регион, P).
2. Найти регионы в страница такие, что области являются смежными и объединение которых образует прямоугольную область. Эти регионы считаются «присоединяемыми». Позволять р обозначим множество этих регионов.
3. Объединить набор р на одну страницу S, а если S переполнен, многократно разбивается, пока ни одна из результирующих страниц не будет переполнена.
4. Заменить набор р регионов в страница с полученными страницами от разделения S.

Связанных с работой

Как в k-d tree, обновления в K-D-B-дереве могут привести к требованию рекурсивного разделения нескольких узлов. Это невероятно неэффективно и может привести к неоптимальному использованию памяти, так как может привести к почти пустым листам. Ломет и Зальцберг предложили структуру, названную hB-дерево (дырявое кирпичное дерево) для повышения производительности K-D-B-деревьев за счет ограничения разбиения, которое происходит после вставки, только одним путем от корня к листу. Это было достигнуто за счет сохранения областей не только как прямоугольники, но и как прямоугольники с прямоугольником, удаленным из центра.^[2]

BKD дерево

Совсем недавно Bkd-дерево было предложено как средство для обеспечения быстрых запросов и почти 100% использования пространства статического K-D-B-дерева. Вместо поддержки одного дерева и повторной балансировки набор ${\displaystyle \log _{2}(N/M)}$ K-D-B-деревья регулярно обслуживаются и перестраиваются.^[3] В этом случае, ${\displaystyle M}$ - размер буфера памяти в точках.

Рекомендации

1. Робинсон, Джон (1981). K-D-B-Tree: структура поиска для больших многомерных динамических индексов. Материалы Международной конференции ACM SIGMOD 1981 года по управлению данными. Sigmod '81. С. 10–18. Дои:10.1145/582318.582321. ISBN  978-0897910408. Получено 8 апреля, 2014.
2. Ломет, Дэвид; Бетти Зальцберг (декабрь 1990 г.). «HB-tree: мультиатрибутный метод индексации с хорошей гарантированной производительностью». Транзакции ACM в системах баз данных. 15 (4): 625–658. CiteSeerX  10.1.1.63.2056. Дои:10.1145/99935.99949.
3. Прокопюк, Октавиан; Агарвал, Панкадж; Ардж, Ларс; Виттер, Джеффри Скотт (2003). Bkd-Tree: динамическое масштабируемое kd-дерево. Достижения в области пространственных и временных баз данных. Конспект лекций по информатике. 2750. стр.46–65. CiteSeerX  10.1.1.134.3206. Дои:10.1007/978-3-540-45072-6_4. ISBN  978-3-540-40535-1.