Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Структура индекса [ править ]

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

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

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

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

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

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

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

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

Вставка, обновление и удаление [ править ]

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

Запросы [ править ]

Запрос диапазона [ править ]

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

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

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

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

K запрос ближайшего соседа [ править ]

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

Другие вопросы [ править ]

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

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

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

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

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

Возможная проблема с перекосом данных [ править ]

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

Настройка индекса [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]

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