Bx-дерево - Bx-tree

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

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

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

Использование дерева 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) - местоположение и скорость объекта в данный момент времени т, то есть время последнего обновления. B + tree - это структура для индексации одномерных данных. Чтобы использовать дерево B + в качестве индекса движущегося объекта, B^Икс-tree использует линеаризация техника, которая помогает интегрировать местоположение объектов во времени т в одномерную стоимость. В частности, объекты сначала разделяются по времени их обновления. Для объектов в одном разделе B^Икс-tree хранит свои местоположения в заданное время, которые оцениваются линейная интерполяция. Таким образом, B^Икс-tree сохраняет согласованный вид всех объектов в одном разделе без сохранения времени обновления объектов.

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

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

${displaystyle B^{x}valueleft(O,tight)=left[indexpartitionight]_{2}+left[xrepight]_{2}}$

Здесь index-partition - это индексный раздел, определяемый временем обновления, а xrep - это значение кривой заполнения пространства позиции объекта в индексируемое время, ${displaystyle left[Xight]_{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 +. Обновление состоит из удаления с последующей вставкой. Вспомогательная структура используется для сохранения последнего ключа каждого индекса, чтобы объект можно было удалить путем поиска ключа. Ключ индексации вычисляется перед воздействием на дерево. Таким образом, B^Икс-tree напрямую наследует хорошие свойства дерева B + и обеспечивает эффективное обновление.

Запросы

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

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

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

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

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

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

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

Другие вопросы

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

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

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

ЛОПАТА^[4] система управления перемещаемыми объектами, построенная на основе популярной системы реляционных баз данных MySQL, который использует B^Икс-дерево для индексации объектов. В этой реализации данные движущихся объектов преобразуются и хранятся непосредственно в MySQL, а запросы преобразуются в стандартные операторы SQL, которые эффективно обрабатываются в реляционном механизме. Самое главное, все это достигается аккуратно и независимо, без проникновения в ядро ​​MySQL.

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

Возможная проблема с перекосом данных

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

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

СТ²B-дерево ^[5] вводит самонастраивающийся фреймворк для настройки производительности B^Икс-дерево при работе с перекосом данных в пространстве и изменением данных со временем. Чтобы справиться с перекосом данных в пространстве, ST²B-дерево разбивает все пространство на области с разной плотностью объектов, используя набор опорных точек. Каждая область использует отдельную сетку, размер ячейки которой определяется плотностью объекта внутри нее.

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

Смотрите также

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

Рекомендации

1. Кристиан С. Дженсен, Дэн Линь и Бэн Чин Оои. Запрос и обновление Эффективное индексирование движущихся объектов на основе дерева B +. В материалах 30-й Международной конференции по очень большим базам данных (VLDB), страницы 768-779, 2004.
2. Дэн Линь. Индексирование и запросы к базам данных движущихся объектов, Докторская диссертация, Национальный университет Сингапура, 2006 г.
3. Йенсен, К.С., Д. Тиесите, Н. Традисаускас, Надежное индексирование движущихся объектов на основе B + -дерева, в материалах Седьмой Международной конференции по управлению мобильными данными, Нара, Япония, 9 страниц, 9–12 мая 2006 г.
4. ЛОПАТА В архиве 2009-01-02 в Wayback Machine: Пространственно-временное ядро ​​автономной базы данных для служб с учетом местоположения.
5. Су Чен, Бэн Чин Оои, Кан-Ли. Тан и Марио А. Насисменто, ST2B-дерево: самонастраиваемое пространственно-временное B + -дерево для движущихся объектов В архиве 2011-06-11 на Wayback Machine. В материалах Международной конференции по управлению данными ACM SIGMOD (SIGMOD), стр. 29-42, 2008 г.