Б х -дерево

По информатике B ​ ^х Tree — это запрос, который используется для обновления эффективных структур индексов на основе дерева B+ для перемещения объектов.

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

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

Использование дерева B+ для перемещения объектов

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

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

Во-вторых, пространство разбивается сеткой, а расположение объекта внутри перегородок линеаризуется в соответствии с кривой заполнения пространства, например, кривыми Пеано или Гильберта .

Наконец, благодаря сочетанию номера раздела (информации о времени) и линейного порядка (информации о местоположении) объект индексируется в B. ^х -дерево с одномерным индексным ключом B ^х ценить:

$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 ^х значение O можно вычислить следующим образом:

1. O индексируется в разделе 0, как уже упоминалось. Следовательно, indexpartition = (00) ₂ .
2. Позиция O в метке времени метки раздела 0 равна (1,5).
3. Используя Z-кривую с порядком = 3, Z-значение O, т. е. xrep, равно (010011) ₂ .
4. Объединение indexpartition и xrep, B ^х значение (00010011) ₂ =19.
5. Пример O ((0,6), (0,2, -0,3), 10) и tmu=120, затем позиция O в метке времени раздела: ???

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

Для нового объекта вычисляется его индексный ключ, а затем объект вставляется в B. ^х -дерево, как в дереве B+. Обновление состоит из удаления с последующей вставкой. Вспомогательная структура используется для хранения последнего ключа каждого индекса, чтобы объект можно было удалить путем поиска ключа. Ключ индексирования вычисляется до воздействия на дерево. Таким образом, Б ^х -tree напрямую наследует хорошие свойства дерева B+ и обеспечивает эффективную производительность обновления.

Запросы

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

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

Б ^х -tree использует технику увеличения окна запроса для ответа на запросы. Поскольку Б ^х -tree хранит местоположение объекта по состоянию на какое-то время после его обновления, увеличение включает два случая: местоположение должно быть либо возвращено в более раннее время, либо перенесено в более позднее время. Основная идея состоит в том, чтобы увеличить окно запроса так, чтобы оно охватывало все объекты, чьи позиции не находятся в окне запроса по метке времени его метки, но будут входить в окно запроса по метке времени запроса.

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

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

K запрос ближайшего соседа

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

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

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

механизмов реляционных баз данных для размещения

Поскольку Б ^х -tree — это индекс, построенный на основе индекса дерева B+, все операции в дереве B+ ^х -дерево, включая вставку, удаление и поиск, такие же, как и в дереве B+. Нет необходимости менять реализацию этих операций. Разница лишь в том, что процедуру получения ключа индексации можно реализовать как хранимую процедуру в существующей СУБД . Следовательно, Б ^х -tree можно легко интегрировать в существующие СУБД, не затрагивая ядро .

СПЭЙД — это система управления движущимися объектами, построенная на основе популярной системы реляционных баз данных MySQL , которая использует класс B. ^х -дерево для индексации объектов. При реализации данные движущегося объекта преобразуются и сохраняются непосредственно в MySQL, а запросы преобразуются в стандартные операторы SQL, которые эффективно обрабатываются в реляционном механизме. Самое главное, что все это достигается аккуратно и независимо, без проникновения в ядро ​​MySQL.

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

Потенциальная проблема с искажением данных

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

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

СТ ² B-дерево представляет систему самонастройки для настройки производительности B ^х -tree при работе с неравномерностью данных в пространстве и изменением данных со временем. Чтобы справиться с неравномерностью данных в пространстве, ST ² B-дерево разбивает все пространство на области с разной плотностью объектов, используя набор опорных точек. В каждом регионе используется отдельная сетка, размер ячейки которой определяется плотностью объектов внутри нее.

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

См. также

• B+ дерево
• Кривая Гильберта
• Z-порядок (кривая)