Bx-дерево

В информатике B^x дерево — это эффективная для запросов и обновления структура индексирования для движущихся объектов, основанная на B+‍‍-деревьях.

Структура индекса

Основой структуры B^x-дерева является B+‍‍-дерево, в котором внутренние узлы обрабатываются как каталоги, содержащие указатели на правый соседний узел (с тем же родителем). В ранних версиях B^x-дерева листья содержали положение индексируемых движущихся объектов и соответствующее время индексирования. В оптимизированной версии каждый лист содержит id, скорость, одномерное (скалярное) значение функции положения и последнее время обновления объекта. Различие увеличивается отсутствием хранения положения движущихся объектов, поскольку оно может быть получено из значения функции.

Использование B+‍‍-деревьев для движущихся объектов

Пример B^x-дерева с числом индексированных разбиений, равным 2 с одним максимальным интервалом обновления tmu. В этом примере существует максимум три разбиения, существующие в одно и то же время. После линеаризации положение объекта, вставленное в момент 0, индексируется в раздел 0 с меткой времени 0.5 tmu, положение объекта, обновлённое в момент времени от 0 до 0.5 tmu, индексируется в раздел 1 с меткой времени 1.0 tmu, и так далее. По истечении интервала времени первый период завершается (закрашенная область) и новый период добавляется (пунктирная линия).

Как и при многих других индексациях движущихся объектов, двумерный движущийся объект моделируется линейной функцией O = ((x, y), (vx, vy), t), где (x, y) и (vx, vy) являются положением и скоростью объекта в момент времени t, то есть в момент последнего обновления. B+‍‍-дерево является структурой для индексации одномерных данных. Чтобы приспособить B+‍‍-дерево для индексации движущихся объектов, B^x-дерево использует технику линеаризации, которая помогает преобразовать положение объекта в момент t в одномерное значение. В частности, объекты сначала разбиваются по времени обновления. Для объектов внутри разбиения по времени B^x-дерево запоминает положение объекта в данный момент времени, полученное линейной интерполяцией. Делая так, B^x-дерево сохраняет согласованное изображение всех объектов внутри элемента разбиения без изменения времени обновления объектов.

Далее пространство разбивается решёткой и положение объектов линеаризуется для элемента разбиения по времени согласно заполняющей пространство кривой, например, кривых Пеано или кривых Гильберта.

Затем, комбинируя с номером элемента разбиения (информация о времени) и линейным порядком (информация о положении), объект индексируется в B^x-дереве с одномерным значением ключа (B^xvalue):

$B^{x}value\left(O,t\right)=\left[indexpartition\right]_{2}+\left[xrep\right]_{2}$

Здесь index-partition — это индекс элемента разбиения, определённого временем обновления, а xrep — значение положения объекта на заполняющей пространство кривой в момент индексирования, $\left[X\right]_{2}$ означает двоичное значение x, «+» означает конкатенацию строк.

Если задан объект O ((7, 2), (-0.1,0.05), 10), tmu = 120, значение B^x для O можно вычислить следующим образом.

1. O индексируется в элементе 0 разбиения по времени, как описано выше. Таким образом, indexpartition = (00)₂.
2. Положение объекта O в момент установки времени для раздела 0 равно (1,5).
3. Используем Z-кривую порядка 3, Z-значение объекта O, xrep, равно (010011)₂.
4. Соединяем строки indexpartition и xrep, получаем значение B^x (00010011)₂=19.

Вставка, обновление и удаление

Если дан новый объект, вычисляется его ключ индексирования и объект вставляется в B^x-дерево как в B+‍‍-дерево. Обновление состоит из удаления с последующей вставкой. Используются дополнительные структуры для хранения последнего ключа каждого индекса, чтобы иметь возможность удалить объект при поиске ключа. Ключ индексирования вычисляется до включения в дерево. Таким образом, B^x-дерево напрямую наследует хорошие свойства B+‍‍-дерева и позволяет достичь хорошей производительности при обновлении.

Запросы

Запрос по диапазону

Запрос по диапазону извлекает все объекты, расположение которых попадает в прямоугольную область $q=\left(\left[qx1,qy1\right];\left[qx2;qy2\right]\right)$ в момент времени $tq$ не ранее текущего времени.

B^x-дерево использует технику расширения окна запроса, чтобы ответить на этот запрос. Расширение имеет два случая — расположение либо должно вычисляться в некоторый предыдущий момент времени, либо в более поздний момент. Основная идея заключается в том, чтобы расширить окно запроса таким образом, что оно будет включать все объекты, не входящие в окно запроса в момент, указанный в ключе объекта, но попадают в него для момента времени запроса.

После расширения нужно просмотреть разделы B^x-дерева, чтобы найти объекты, попадающие в расширенное окно. В каждом разделе применение заполняющей пространство кривой означает, что диапазон запроса в естественном двумерном пространстве становится множеством запросов по диапазону в одномерном пространстве .

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

Запрос K ближайших соседей

Запрос K ближайших соседей выполняется итеративным выполнением запросов по диапазону с увеличением области поиска, пока не получим k ответов. Другая возможность — использовать аналогичные идеи вместе с техникой iDistance.

Другие запросы

Алгоритмы запроса по диапазону и запроса K ближайших соседей можно легко расширить для поддержки интервальных запросов, непрерывных запросов, и т. д..

Адаптация реляционных баз данных для размещения движущихся объектов

Поскольку B^x-дерево является индексом, построенным на основе B+‍‍-дерева, все операции в B^x-дереве, включая вставку, удаление и поиск, являются теми же, что и в B+‍‍-дереве. Нет необходимости изменять реализацию этих операций. Единственное отличие в реализации заключается в имплементации процедуры получения ключа индексирования в виде хранимой процедуры существующей базе данных. Таким образом, B^x-дерево можно легко интегрировать в существующую базу данных, не затрагивая ядра.

SpADE — это система управления движущимися объектами, построенная поверх популярной базы данных MySQL, использующая B^x-дерево для индексирования объектов. В реализации данные движущихся объектов преобразуются и запоминаются прямо в MySQL, а запросы трансформируются в стандартные SQL-запросы, которые эффективно обрабатываются исполняющей системой реляционной базы данных. Что наиболее важно, всё это делается аккуратно и независимо без вмешательства в ядро MySQL.

Настройка производительности

Потенциальные проблемы с расфазировкой данных

B^x-дерево использует решётку для распределения пространства, чтобы преобразовать двумерное положение в одномерный ключ. Это может привести к деградации производительности как в запросах, так и в операциях обновления, если работают с асимметричными данными. Если ячейка решётки имеет большой размер, в ячейке содержатся много объектов. Поскольку объекты в ячейке неразличимы по индексу, будет некоторое переполнение узлов в низлежащем B+‍‍-дереве. Существование страниц переполнения не только разрушает балансировку дерева, но и увеличивает стоимость обновления. Как и для обычных запросов, для запроса по диапазону, большие ячейки приводят к большему числу ложных выборок и увеличивает время выполнения. С другой стороны, если пространство разбить на более мелкую решётку, то есть на более мелкие ячейки, каждая ячейка содержит меньше объектов. Вряд ли в этом случае будет достигнуто переполнение страниц, а также будет меньше ложных выборок, однако нужно будет просматривать большее число ячеек. Увеличение числа просматриваемых ячеек также увеличивает трудоёмкость запроса.

Настройка индекса

ST²B-дерево вводит самонастраивающуюся схему для настройки производительности B^x-дерева при работе с несимметричными данными в пространстве и во времени. Для работы с асимметричными данными в пространстве ST²B-дерево разбивает всё пространство на области с различной плотностью объектов при помощи множества контрольных точек. Каждая область использует индивидуальную решётку, величина ячеек которой определяется плотностью объектов внутри области.

B^x-дерево имеет несколько разбиений для различных интервалов времени. ST²B-дерево использует увеличение или сокращение интервала для настройки индексации, чтобы согласовываться с разбиением пространства и приспособиться к изменению времени. В частности, когда разбиение опустошается и начинает расти, выбирается новое множество контрольных точек и новая решётка для каждой точки согласно последней плотности данных. Настройка основывается на статистике, собранной за данный период времени, так что разбиение пространства лучше соответствует самому последнему распределению данных. В этом смысле ожидается, что ST²B-дерево минимизирует эффект, вызванный несимметричностью данных в пространстве и изменениям данных по времени.

См. также

• B+-дерево
• Кривая Гильберта
• Z-кривая
• Список структур данных (деревья)

Литература

• Christian S. Jensen, Dan Lin, Beng Chin Ooi. Proceedings of 30th International Conference on Very Large Data Bases (VLDB). — 2004.
• C.S. Jensen, D. Tiesyte, N. Tradisauskas. Proceedings of the Seventh International Conference on Mobile Data Management. — Nara, Japan, 2006.
• Dan Lin. Indexing and Querying Moving Objects Databases. — National University of Singapore, 2006. — (PhD thesis).
• Su Chen, Beng Chin Ooi, Kan-Lee Tan, Mario A. Nacismento. Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD). — 2008.