Bx-дерево

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

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

[править | править код]

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

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

[править | править код]
Пример Bx-дерева с числом индексированных разбиений, равным 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+‍‍-дерево для индексации движущихся объектов, Bx-дерево использует технику линеаризации, которая помогает преобразовать положение объекта в момент t в одномерное значение. В частности, объекты сначала разбиваются по времени обновления. Для объектов внутри разбиения по времени Bx-дерево запоминает положение объекта в данный момент времени, полученное линейной интерполяцией. Делая так, Bx-дерево сохраняет согласованное изображение всех объектов внутри элемента разбиения без изменения времени обновления объектов.

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

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

Здесь index-partition — это индекс элемента разбиения, определённого временем обновления, а xrep — значение положения объекта на заполняющей пространство кривой в момент индексирования, означает двоичное значение x, «+» означает конкатенацию строк.

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

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

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

[править | править код]

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

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

[править | править код]

Запрос по диапазону извлекает все объекты, расположение которых попадает в прямоугольную область в момент времени не ранее текущего времени.

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

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

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

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

[править | править код]

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

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

[править | править код]

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

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

[править | править код]

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

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

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

[править | править код]

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

[править | править код]

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

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

[править | править код]

ST2B-дерево[5] вводит самонастраивающуюся схему для настройки производительности Bx-дерева при работе с несимметричными данными в пространстве и во времени. Для работы с асимметричными данными в пространстве ST2B-дерево разбивает всё пространство на области с различной плотностью объектов при помощи множества контрольных точек. Каждая область использует индивидуальную решётку, величина ячеек которой определяется плотностью объектов внутри области.

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

Примечания

[править | править код]
  1. 1 2 Jensen, Lin, Ooi, 2004, с. 768-779.
  2. 1 2 Dan Lin, 2006.
  3. Jensen, Tiesyte, Tradisauskas, 2006.
  4. SpADE Архивировано 2 января 2009 года.: A SPatio-temporal Autonomic Database Engine for location-aware services.
  5. Chen, Ooi, Tan, Nacismento, 2008, с. 29-42.

Литература

[править | править код]
  • 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.