В информатике Bx дерево — это эффективная для запросов и обновления структура индексирования для движущихся объектов, основанная на B+-деревьях.
Структура индекса
Основой структуры Bx-дерева является B+-дерево, в котором внутренние узлы обрабатываются как каталоги, содержащие указатели на правый соседний узел (с тем же родителем). В ранних версиях Bx-дерева[1] листья содержали положение индексируемых движущихся объектов и соответствующее время индексирования. В оптимизированной версии[2] каждый лист содержит id, скорость, одномерное (скалярное) значение функции положения и последнее время обновления объекта. Различие увеличивается отсутствием хранения положения движущихся объектов, поскольку оно может быть получено из значения функции.
Использование B+-деревьев для движущихся объектов
Как и при многих других индексациях движущихся объектов, двумерный движущийся объект моделируется линейной функцией O = ((x, y), (vx, vy), t), где (x, y) и (vx, vy) являются положением и скоростью объекта в момент времени t, то есть в момент последнего обновления. B+-дерево является структурой для индексации одномерных данных. Чтобы приспособить B+-дерево для индексации движущихся объектов, Bx-дерево использует технику линеаризации, которая помогает преобразовать положение объекта в момент t в одномерное значение. В частности, объекты сначала разбиваются по времени обновления. Для объектов внутри разбиения по времени Bx-дерево запоминает положение объекта в данный момент времени, полученное линейной интерполяцией. Делая так, Bx-дерево сохраняет согласованное изображение всех объектов внутри элемента разбиения без изменения времени обновления объектов.
Далее пространство разбивается решёткой и положение объектов линеаризуется для элемента разбиения по времени согласно заполняющей пространство кривой, например, кривых Пеано или кривых Гильберта.
Затем, комбинируя с номером элемента разбиения (информация о времени) и линейным порядком (информация о положении), объект индексируется в Bx-дереве с одномерным значением ключа (Bxvalue):
![{\displaystyle B^{x}value\left(O,t\right)=\left[indexpartition\right]_{2}+\left[xrep\right]_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/941a986f366e05746cfc72b2a6fc697a1911bda8)
Здесь index-partition — это индекс элемента разбиения, определённого временем обновления, а xrep — значение положения объекта на заполняющей пространство кривой в момент индексирования, означает двоичное значение x, «+» означает конкатенацию строк.
![{\displaystyle \left[X\right]_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25d43f0cc5c6e1d4422225a868cb80fffcf26c6c)
Если задан объект O ((7, 2), (-0.1,0.05), 10), tmu = 120, значение Bx для O можно вычислить следующим образом.
- O индексируется в элементе 0 разбиения по времени, как описано выше. Таким образом, indexpartition = (00)2.
- Положение объекта O в момент установки времени для раздела 0 равно (1,5).
- Используем Z-кривую порядка 3, Z-значение объекта O, xrep, равно (010011)2.
- Соединяем строки indexpartition и xrep, получаем значение Bx (00010011)2=19.
Вставка, обновление и удаление
Если дан новый объект, вычисляется его ключ индексирования и объект вставляется в Bx-дерево как в B+-дерево. Обновление состоит из удаления с последующей вставкой. Используются дополнительные структуры для хранения последнего ключа каждого индекса, чтобы иметь возможность удалить объект при поиске ключа. Ключ индексирования вычисляется до включения в дерево. Таким образом, Bx-дерево напрямую наследует хорошие свойства B+-дерева и позволяет достичь хорошей производительности при обновлении.
Запросы
Запрос по диапазону
Запрос по диапазону извлекает все объекты, расположение которых попадает в прямоугольную область в момент времени не ранее текущего времени.
![{\displaystyle q=\left(\left[qx1,qy1\right];\left[qx2;qy2\right]\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b3c2cb772ac0f84f02c690ef669c2218674ac836)
Bx-дерево использует технику расширения окна запроса, чтобы ответить на этот запрос. Расширение имеет два случая — расположение либо должно вычисляться в некоторый предыдущий момент времени, либо в более поздний момент. Основная идея заключается в том, чтобы расширить окно запроса таким образом, что оно будет включать все объекты, не входящие в окно запроса в момент, указанный в ключе объекта, но попадают в него для момента времени запроса.
После расширения нужно просмотреть разделы Bx-дерева, чтобы найти объекты, попадающие в расширенное окно. В каждом разделе применение заполняющей пространство кривой означает, что диапазон запроса в естественном двумерном пространстве становится множеством запросов по диапазону в одномерном пространстве [1].
Во избежание чересчур больших запросов по диапазону после расширения окна запроса в асимметричных данных существует алгоритм оптимизации[3], который улучшает эффективность запроса путём исключения излишних расширений.
Запрос K ближайших соседей
Запрос K ближайших соседей выполняется итеративным выполнением запросов по диапазону с увеличением области поиска, пока не получим k ответов. Другая возможность — использовать аналогичные идеи вместе с техникой iDistance[en].
Другие запросы
Алгоритмы запроса по диапазону и запроса K ближайших соседей можно легко расширить для поддержки интервальных запросов, непрерывных запросов, и т. д.[2].
Адаптация реляционных баз данных для размещения движущихся объектов
Поскольку Bx-дерево является индексом, построенным на основе B+-дерева, все операции в Bx-дереве, включая вставку, удаление и поиск, являются теми же, что и в B+-дереве. Нет необходимости изменять реализацию этих операций. Единственное отличие в реализации заключается в имплементации процедуры получения ключа индексирования в виде хранимой процедуры существующей базе данных. Таким образом, Bx-дерево можно легко интегрировать в существующую базу данных, не затрагивая ядра[en].
SpADE[4] — это система управления движущимися объектами, построенная поверх популярной базы данных MySQL, использующая Bx-дерево для индексирования объектов. В реализации данные движущихся объектов преобразуются и запоминаются прямо в MySQL, а запросы трансформируются в стандартные SQL-запросы, которые эффективно обрабатываются исполняющей системой реляционной базы данных. Что наиболее важно, всё это делается аккуратно и независимо без вмешательства в ядро MySQL.
Настройка производительности
Потенциальные проблемы с расфазировкой данных
Bx-дерево использует решётку для распределения пространства, чтобы преобразовать двумерное положение в одномерный ключ. Это может привести к деградации производительности как в запросах, так и в операциях обновления, если работают с асимметричными данными. Если ячейка решётки имеет большой размер, в ячейке содержатся много объектов. Поскольку объекты в ячейке неразличимы по индексу, будет некоторое переполнение узлов в низлежащем B+-дереве. Существование страниц переполнения не только разрушает балансировку дерева, но и увеличивает стоимость обновления. Как и для обычных запросов, для запроса по диапазону, большие ячейки приводят к большему числу ложных выборок и увеличивает время выполнения. С другой стороны, если пространство разбить на более мелкую решётку, то есть на более мелкие ячейки, каждая ячейка содержит меньше объектов. Вряд ли в этом случае будет достигнуто переполнение страниц, а также будет меньше ложных выборок, однако нужно будет просматривать большее число ячеек. Увеличение числа просматриваемых ячеек также увеличивает трудоёмкость запроса.
Настройка индекса
ST2B-дерево[5] вводит самонастраивающуюся схему для настройки производительности Bx-дерева при работе с несимметричными данными в пространстве и во времени. Для работы с асимметричными данными в пространстве ST2B-дерево разбивает всё пространство на области с различной плотностью объектов при помощи множества контрольных точек. Каждая область использует индивидуальную решётку, величина ячеек которой определяется плотностью объектов внутри области.
Bx-дерево имеет несколько разбиений для различных интервалов времени. ST2B-дерево использует увеличение или сокращение интервала для настройки индексации, чтобы согласовываться с разбиением пространства и приспособиться к изменению времени. В частности, когда разбиение опустошается и начинает расти, выбирается новое множество контрольных точек и новая решётка для каждой точки согласно последней плотности данных. Настройка основывается на статистике, собранной за данный период времени, так что разбиение пространства лучше соответствует самому последнему распределению данных. В этом смысле ожидается, что ST2B-дерево минимизирует эффект, вызванный несимметричностью данных в пространстве и изменениям данных по времени.
См. также
Примечания
- 1 2 Jensen, Lin, Ooi, 2004, с. 768-779.
- 1 2 Dan Lin, 2006.
- ↑ Jensen, Tiesyte, Tradisauskas, 2006.
- ↑ SpADE Архивировано 2 января 2009 года.: A SPatio-temporal Autonomic Database Engine for location-aware services.
- ↑ 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. Архивировано 11 июня 2011 года.
 | Для улучшения этой статьи желательно: |
 | |
|---|---|
| Двоичные деревья | |
| Самобалансирующиеся двоичные деревья | |
| B-деревья | |
| Префиксные деревья | |
| Двоичное разбиение пространства | |
| Недвоичные деревья | |
| Разбиение пространства | |
| Другие деревья | |
| Алгоритмы | |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .