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-дереве, длина пути к листьям дерева одинакова для всех запросов.
Регионы, составляющие страницу региона, не пересекаются.
Если корнем является страница региона, объединение ее регионов представляет собой все пространство поиска.
Когда дочерний элемент пары (регион, дочерний элемент) на странице региона также является страницей региона, объединением всех регионов в дочернем элементе является регион .
И наоборот, в приведенном выше случае, если дочерняя страница является страницей точек, все точки дочерней страницы должны содержаться в регионе .

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

Запросы

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

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

Алгоритм

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

Вставки

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

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

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

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

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

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

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

Если корневая страница имеет значение null, просто сделайте корневую страницу новой страницей точек, содержащей (точку, местоположение)
Если выполняется запрос точного соответствия по точке , чтобы найти страницу, эту точку на которую следует добавить . Если он уже существует на странице, завершите работу.
Добавить (точку, местоположение) на страницу. Если страница переполняется, пусть 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, чтобы оно соответствовало некоторым минимальным критериям использования хранилища. Алгоритм реорганизации, который следует использовать, когда страница содержит слишком мало данных, следующий:

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

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

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

Дерево БКД

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

Ссылки

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

[1] Робинсон, Джон (1981). «КДБ-дерево». Материалы международной конференции ACM SIGMOD 1981 года по управлению данными - SIGMOD '81 . Сигмод '81. стр. 10–18. дои : 10.1145/582318.582321 . ISBN 978-0897910408 . S2CID 27482172 . Проверено 8 апреля 2014 г.

[2] Ломет, Дэвид; Бетти Зальцберг (декабрь 1990 г.). «HB-дерево: метод многоатрибутной индексации с хорошей гарантированной производительностью». Транзакции ACM в системах баз данных . 15 (4): 625–658. CiteSeerX 10.1.1.63.2056 . дои : 10.1145/99935.99949 . S2CID 15333693 .

[3] Прокопюк, Октавиан; Агарвал, Панкадж ; Арге, Ларс ; Виттер, Джеффри Скотт (2003). «BKD-дерево: динамическое масштабируемое kd-дерево» . Достижения в области пространственных и временных баз данных . Конспекты лекций по информатике. Том. 2750. стр. 46–65 . CiteSeerX 10.1.1.134.3206 . дои : 10.1007/978-3-540-45072-6_4 . ISBN 978-3-540-40535-1 . S2CID 12784232 .

[1]

[2]

[3]

v т и Структуры данных
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

v т и Древовидные структуры данных
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic Palindrome (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal d-ary Fibonacci Leftist Pairing Skew binomial Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top