Árbol Bx

En informática , un árbol B x  es una estructura de indexación eficiente de consulta y actualización para mover objetos basada en árboles B+ ‍‍.

Estructura del índice

La base de la estructura de árbol B x es un árbol B+‍‍, en el que los nodos internos se tratan como directorios que contienen punteros al nodo vecino derecho (con el mismo padre). En las primeras versiones del árbol B x [ 1] , las hojas contenían la posición de los objetos en movimiento indexados y el tiempo de indexación correspondiente. En la versión optimizada [2] , cada hoja contiene una identificación, una velocidad, un valor unidimensional (escalar) de la función de posición y la hora de la última actualización del objeto. La diferencia se incrementa por la falta de almacenamiento de la posición de los objetos en movimiento, ya que se puede obtener del valor de la función .

Uso de árboles B+‍‍ para mover objetos

Al igual que con muchas otras indexaciones de objetos en movimiento, un objeto en movimiento bidimensional se modela mediante una función lineal O = ((x, y), (vx, vy), t), donde (x, y) y (vx, vy ) son la posición y la velocidad del objeto en el tiempo t , es decir, en el momento de la última actualización. B+‍‍-tree es una estructura para indexar datos unidimensionales. Para acomodar el árbol B+‍‍ para indexar objetos en movimiento, el árbol Bx utiliza una técnica de linealización que ayuda a convertir la posición del objeto en el momento t en un valor unidimensional. En particular, los objetos primero se desglosan por tiempo de actualización. Para objetos dentro de una partición de tiempo, el árbol B x recuerda la posición del objeto en un punto dado en el tiempo, obtenido por interpolación lineal . Al hacerlo, el árbol Bx mantiene una imagen consistente de todos los objetos dentro del elemento dividido sin cambiar el tiempo de actualización de los objetos.

A continuación, el espacio se divide mediante una celosía y la posición de los objetos se linealiza para el elemento de partición en el tiempo de acuerdo con la curva de llenado del espacio, por ejemplo, las curvas de Peano o las curvas de Hilbert .

Luego, combinado con el número de elemento dividido (información de tiempo) y el orden lineal (información de posición), el objeto se indexa en el árbol B x con un valor clave unidimensional (valor B x ):

Aquí index-partition es el índice del elemento de partición determinado por el tiempo de actualización, y xrep es el valor de la posición del objeto en la curva de llenado de espacio en el momento de la indexación, significa el valor binario de x, "+" significa cadena concatenación.

Dado un objeto O ((7, 2), (-0.1,0.05), 10), tmu = 120, el valor de B x para O se puede calcular de la siguiente manera.

  1. O está indexado en el elemento 0 de la partición de tiempo como se describe anteriormente. Entonces indexpartition = (00) 2 .
  2. La posición del objeto O en el momento de configurar el tiempo para la partición 0 es (1.5).
  3. Usando una curva Z de orden 3, el valor Z del objeto O, xrep, es (010011) 2 .
  4. Conectamos las líneas indexpartition y xrep, obtenemos el valor B x (00010011) 2 =19.

Inserción, actualización y borrado

Si se proporciona un objeto nuevo, se calcula su clave de índice y el objeto se inserta en el árbol Bx como en un árbol B+‍‍. Una actualización consiste en una eliminación seguida de una inserción. Se utilizan estructuras adicionales para almacenar la última clave de cada índice para que el objeto se pueda eliminar cuando se busca la clave. La clave de índice se calcula antes de incluirse en el árbol. Por lo tanto, un árbol B x hereda directamente las buenas propiedades de un árbol B+‍‍ y logra un buen rendimiento de actualización.

Solicitudes

Consulta por rango

La consulta de rango recupera todos los objetos cuya ubicación se encuentra dentro de la región rectangular en un momento no anterior al momento actual.

El árbol Bx utiliza una técnica de expansión de ventana de consulta para responder a esta consulta. La extensión tiene dos casos: la ubicación debe calcularse en algún momento anterior o en un momento posterior. La idea principal es expandir la ventana de consulta de tal manera que incluya todos los objetos que no están incluidos en la ventana de consulta en el momento especificado en la clave del objeto, pero que caen en ella en el momento de la solicitud.

Después de expandir, debe mirar a través de las secciones del árbol B x para encontrar objetos que caigan en la ventana expandida. En cada sección, la aplicación de una curva de relleno de espacio significa que el rango de consulta en el espacio 2D natural se convierte en el conjunto de consultas de rango en el espacio 1D [1] .

Para evitar consultas de rango demasiado grande después de expandir la ventana de consulta en datos asimétricos, existe un algoritmo de optimización [3] que mejora el rendimiento de la consulta al eliminar expansiones innecesarias.

Consulta de K vecinos más cercanos

La consulta de K vecinos más cercanos se realiza iterativamente realizando consultas de rango con un área de búsqueda creciente hasta obtener k respuestas. Otra posibilidad es utilizar ideas similares junto con la técnica iDistance .

Otras solicitudes

Los algoritmos de consulta de rango y consulta de K vecino más cercano se pueden ampliar fácilmente para admitir consultas de intervalo, consultas continuas, etc. [2] .

Adaptación de bases de datos relacionales para acomodar objetos en movimiento

Debido a que el árbol B x es un índice creado sobre un árbol B+‍‍, todas las operaciones en un árbol B x , incluidas la inserción, la eliminación y la búsqueda, son las mismas que en un árbol B+‍‍. No hay necesidad de cambiar la implementación de estas operaciones. La única diferencia en la implementación radica en la implementación del procedimiento para obtener la clave de indexación como un procedimiento almacenado en la base de datos existente . Por lo tanto, el árbol Bx se puede integrar fácilmente en una base de datos existente sin afectar el kernel .

SpADE [4]  es un sistema de gestión de objetos en movimiento construido sobre la popular base de datos MySQL que utiliza un árbol B x para indexar objetos. En la implementación, los datos de objetos en movimiento se convierten y almacenan directamente en MySQL, y las consultas se transforman en consultas SQL estándar que el tiempo de ejecución de la base de datos relacional procesa de manera eficiente. Lo más importante es que todo esto se hace de manera ordenada e independiente sin interferir con el kernel de MySQL.

Ajuste de rendimiento

Posibles problemas con el sesgo de datos

El árbol Bx utiliza una red de asignación de espacio para transformar una posición bidimensional en una clave unidimensional. Esto puede provocar una degradación del rendimiento tanto en las consultas como en las actualizaciones cuando se trabaja con datos asimétricos. Si la celda de la cuadrícula es grande, la celda contiene muchos objetos. Debido a que los objetos en una celda no se pueden distinguir por índice, habrá un desbordamiento de nodos en el árbol B+‍‍ subyacente. La existencia de páginas desbordadas no solo destruye el equilibrio del árbol, sino que también aumenta el costo de actualización. Al igual que con las consultas normales, para una consulta de rango, las celdas más grandes generan más muestras falsas y aumentan el tiempo de ejecución. Por otro lado, si el espacio se divide en una cuadrícula más pequeña, es decir, en celdas más pequeñas, cada celda contiene menos objetos. Es poco probable que se logre el desbordamiento de la página en este caso, y también habrá menos muestras falsas, pero será necesario escanear más celdas. Aumentar el número de celdas para mirar también aumenta la complejidad de la consulta.

Configuración del índice

El árbol B ST 2 [5] introduce un esquema de autoajuste para ajustar el rendimiento de un árbol B x cuando se trata de datos no simétricos en el espacio y el tiempo. Para trabajar con datos asimétricos en el espacio ST 2 , el árbol B divide todo el espacio en regiones con diferente densidad de objetos utilizando un conjunto de puntos de control. Cada región utiliza una cuadrícula individual cuyo tamaño de celda está determinado por la densidad de objetos dentro de la región.

El árbol B x tiene varias particiones para diferentes intervalos de tiempo. El árbol B de ST 2 utiliza el aumento o disminución de intervalos para ajustar la indexación para adaptarse a la partición del espacio y adaptarse a los cambios de tiempo. En particular, cuando la partición se vacía y comienza a crecer, se selecciona un nuevo conjunto de puntos de control y se selecciona una nueva cuadrícula para cada punto de acuerdo con la última densidad de datos. El ajuste se basa en estadísticas recopiladas durante un período de tiempo determinado, de modo que la partición del espacio coincida mejor con la distribución de datos más reciente. En este sentido, se espera que el árbol B ST 2 minimice el efecto causado por la asimetría de datos en el espacio y los cambios de datos a lo largo del tiempo.

Véase también

Notas

  1. ↑ 1 2 Jensen, Lin, Ooi, 2004 , pág. 768-779.
  2. ↑ 12Dan Lin , 2006 .
  3. ↑ Jensen, Tiesyte, Tradisauskas, 2006 .
  4. ↑ SpADE Archivado desde el original el 2 de enero de 2009. : un motor de base de datos autónomo temporal SPatio para servicios con reconocimiento de ubicación.
  5. ↑ Chen, Ooi, Tan, Nacismento, 2008 , p. 29-42.

Literatura