Hispanopedia WikiEn informática , el árbol B x es una consulta que se utiliza para actualizar estructuras de índices eficientes basadas en árboles B+ para el movimiento de objetos.
Estructura del índice
La estructura básica del árbol B x es un árbol B+ en el que los nodos internos funcionan como un directorio, cada uno conteniendo un puntero a su hermano derecho. En la versión anterior del árbol B x , [ 1 ] los nodos hoja contenían las ubicaciones de los objetos en movimiento que se estaban indexando y el tiempo de indexación correspondiente. En la versión optimizada, [ 2 ] cada entrada de nodo hoja contiene el ID, la velocidad, el valor de mapeo unidimensional y el tiempo de última actualización del objeto. El factor de ramificación aumenta al no almacenar las ubicaciones de los objetos en movimiento, ya que estas se pueden derivar de los valores de mapeo .
Utilización del árbol B+ para mover objetos
Al igual que muchos otros índices de objetos en movimiento, un objeto bidimensional en movimiento se modela como 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 un instante de tiempo t , es decir, el tiempo de la última actualización. El árbol B+ es una estructura para indexar datos unidimensionales. Para adoptar el árbol B+ como índice de objetos en movimiento, el árbol B x utiliza una técnica de linealización que ayuda a integrar la posición de los objetos en el tiempo t en un valor unidimensional. Específicamente, los objetos se particionan primero según su tiempo de actualización. Para los objetos dentro de la misma partición, el árbol B x almacena sus posiciones en un tiempo dado, que se estiman mediante interpolación lineal . De esta manera, el árbol B x mantiene una vista consistente de todos los objetos dentro de la misma partición sin almacenar el tiempo de actualización de cada objeto.
En segundo lugar, el espacio se divide mediante una cuadrícula y la ubicación de un objeto se linealiza dentro de las particiones según una curva que llena el espacio, por ejemplo, las curvas de Peano o de Hilbert .
Finalmente, con la combinación del número de partición (información de tiempo) y el orden lineal (información de ubicación), un objeto se indexa en un árbol B x con una clave de índice unidimensional B x valor:
![{\displaystyle B^{x}{\text{ valor}}\left(O,t\right)=\left[{\text{partición de índice}}\right]_{2}+\left[{\text{xrep}}\right]_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35a45ac6805a51f5e17b39ca54280aab3810f567)
Aquí, index-partition es una partición de índice determinada por el tiempo de actualización y xrep es el valor de la curva que llena el espacio de la posición del objeto en el tiempo indexado,denota el valor binario de x, y “+” significa concatenación.
![{\displaystyle \left[X\right]_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25d43f0cc5c6e1d4422225a868cb80fffcf26c6c)
Dado un objeto O ((7, 2), (-0.1,0.05), 10), tmu = 120, el valor B x para O se puede calcular de la siguiente manera:
- O está indexado en la partición 0 como se mencionó. Por lo tanto, indexpartition = (00) 2 .
- La posición de O en la marca de tiempo de la etiqueta de la partición 0 es (1,5).
- Utilizando la curva Z con orden = 3, el valor Z de O, es decir, xrep es (010011) 2 .
- Concatenando indexpartition y xrep, B x valor (00010011) 2 =19.
- Ejemplo O ((0,6), (0.2, -0.3 ),10) y tmu=120 entonces la posición de O en la marca de tiempo de la partición es: ???
Inserción, actualización y eliminación
Dado un nuevo objeto, se calcula su clave de índice y luego se inserta en el árbol B x, al igual que en el árbol B+. Una actualización consiste en una eliminación seguida de una inserción. Se utiliza una estructura auxiliar para almacenar la clave más reciente de cada índice, de modo que un objeto pueda eliminarse buscando dicha clave. La clave de indexación se calcula antes de afectar al árbol. De esta forma, el árbol B x hereda directamente las buenas propiedades del árbol B+ y logra un rendimiento de actualización eficiente.
Consultas
consulta de rango
Una consulta de rango recupera todos los objetos cuya ubicación se encuentra dentro del rango rectangular.en ese momentono antes del momento actual.
![{\displaystyle q=\left(\left[qx1,qy1\right];\left[qx2;qy2\right]\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b3c2cb772ac0f84f02c690ef669c2218674ac836)
El árbol B x utiliza la técnica de ampliación de la ventana de consulta para responder a las consultas. Dado que el árbol B x almacena la ubicación de un objeto en algún momento posterior a su actualización, la ampliación implica dos casos: una ubicación debe retroceder a un momento anterior o avanzar a un momento posterior. La idea principal es ampliar la ventana de consulta para que abarque todos los objetos cuyas posiciones no se encuentren dentro de la ventana de consulta en la marca de tiempo de su etiqueta, pero que entrarán en la ventana de consulta en la marca de tiempo de la consulta.
Tras la ampliación, es necesario recorrer las particiones del árbol B x para encontrar los objetos que caen dentro de la ventana de consulta ampliada. En cada partición, el uso de una curva que llena el espacio implica que una consulta de rango en el espacio nativo bidimensional se convierte en un conjunto de consultas de rango en el espacio transformado unidimensional. [ 1 ]
Para evitar regiones de consulta excesivamente grandes después de la expansión en conjuntos de datos sesgados, existe una optimización del algoritmo de consulta, [ 3 ] que mejora la eficiencia de la consulta al evitar el agrandamiento innecesario de la consulta.
Consulta del vecino más cercano K
La consulta de k vecinos más cercanos se calcula realizando iterativamente consultas de rango con una región de búsqueda que se amplía gradualmente hasta obtener k respuestas. Otra posibilidad es emplear ideas de consulta similares a las de la técnica iDistance .
Otras consultas
Los algoritmos de consulta de rango y de consulta de K vecinos más cercanos se pueden extender fácilmente para admitir consultas de intervalo, consultas continuas, etc. [ 2 ]
Adaptación de los motores de bases de datos relacionales para dar cabida a objetos en movimiento.
Dado que el árbol B x es un índice construido sobre un índice de árbol B+, todas las operaciones en el árbol B x , incluidas la inserción, la eliminación y la búsqueda, son idénticas a las del árbol B+. No es necesario modificar la implementación de estas operaciones. La única diferencia radica en implementar el procedimiento para derivar la clave de indexación como un procedimiento almacenado en un sistema de gestión de bases de datos (DBMS) existente . Por lo tanto, el árbol B x se puede integrar fácilmente en los DBMS existentes sin modificar el núcleo .
SpADE [ 4 ] es un sistema de gestión de objetos móviles construido sobre el popular sistema de base de datos relacional MySQL , que utiliza el árbol B x para indexar los objetos. En su implementación, los datos de los objetos móviles se transforman y almacenan directamente en MySQL, y las consultas se transforman en sentencias SQL estándar que se procesan eficientemente en el motor relacional. Lo más importante es que todo esto se logra de forma ordenada e independiente, sin afectar al núcleo de MySQL.
Ajuste del rendimiento
Problema potencial con la asimetría de los datos
El árbol B x utiliza una cuadrícula para la partición del espacio, mapeando ubicaciones bidimensionales a claves unidimensionales. Esto puede degradar el rendimiento tanto en las consultas como en las actualizaciones al trabajar con datos sesgados. Si una celda de la cuadrícula es demasiado grande, contiene muchos objetos. Dado que los objetos en una celda son indistinguibles para el índice, habrá nodos de desbordamiento en el árbol B+ subyacente. La existencia de páginas de desbordamiento no solo destruye el equilibrio del árbol, sino que también aumenta el costo de actualización. En cuanto a las consultas, para una región de consulta dada, una celda grande genera más falsos positivos y aumenta el tiempo de procesamiento. Por otro lado, si el espacio se particiona con una cuadrícula más fina, es decir, celdas más pequeñas, cada celda contiene pocos objetos. Apenas hay páginas de desbordamiento, por lo que el costo de actualización se minimiza. Se recuperan menos falsos positivos en una consulta. Sin embargo, se necesitan buscar más celdas. El aumento en el número de celdas buscadas también aumenta la carga de trabajo de una consulta.
Ajuste de índices
El árbol B ST 2 [ 5 ] introduce un marco de autoajuste para optimizar el rendimiento del árbol B x al lidiar con la asimetría de datos en el espacio y los cambios de datos en el tiempo. Para abordar la asimetría de datos en el espacio, el árbol B ST 2 divide todo el espacio en regiones con diferente densidad de objetos utilizando un conjunto de puntos de referencia. Cada región utiliza una cuadrícula individual cuyo tamaño de celda está determinado por la densidad de objetos en su interior.
El árbol B x tiene múltiples particiones correspondientes a diferentes intervalos de tiempo. Con el paso del tiempo, cada partición crece y se reduce alternativamente. El árbol B ST 2 utiliza esta característica para ajustar el índice en línea y adaptar la partición del espacio a los cambios de datos a lo largo del tiempo. En concreto, cuando una partición se vacía y comienza a crecer, selecciona un nuevo conjunto de puntos de referencia y una nueva cuadrícula para cada punto de referencia, según la densidad de datos más reciente. El ajuste se basa en las últimas estadísticas recopiladas durante un período determinado, de modo que la partición del espacio se ajuste mejor a la distribución de datos más reciente. De esta forma, 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
Referencias
- 1 2 Christian S. Jensen, Dan Lin y Beng Chin Ooi. Indexación eficiente de objetos móviles basada en árboles B+ para consultas y actualizaciones . En Actas de la 30.ª Conferencia Internacional sobre Bases de Datos Muy Grandes (VLDB), páginas 768-779, 2004.
- 1 2 Dan Lin. Indexación y consulta de bases de datos de objetos en movimiento , tesis doctoral, Universidad Nacional de Singapur, 2006.
- ↑ Jensen, CS, D. Tiesyte, N. Tradisauskas, Indexación robusta basada en árboles B+ de objetos en movimiento, en Actas de la Séptima Conferencia Internacional sobre Gestión de Datos Móviles , Nara, Japón, 9 páginas, 9-12 de mayo de 2006.
- ↑ SpADE Archivado el 2 de enero de 2009 en Wayback Machine : Un motor de base de datos autónomo espaciotemporal para servicios basados en la ubicación.
- ↑ Su Chen, Beng Chin Ooi, Kan-Lee Tan y Mario A. Nacismento, ST2B-tree: Un árbol B+ espaciotemporal autoajustable para objetos en movimiento. Archivado el 11 de junio de 2011 en Wayback Machine . En Actas de la Conferencia Internacional ACM SIGMOD sobre Gestión de Datos (SIGMOD), páginas 29-42, 2008.
- Árbol B