KDB-дерево

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

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

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

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

Структура

Дерево KDB содержит два типа страниц:

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

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

При выполнении операций вставки/удаления KDB-дерево сохраняет определенный набор свойств:

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

Операции над KDB-деревом

Запросы

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

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

Алгоритм

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

Вставки

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

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

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

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

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

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

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

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

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

Удаления

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

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

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

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

Связанная работа

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

Дерево БКД

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

Ссылки

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