árbol Bx

En informática , el árbol B x es básicamente una consulta que se utiliza para actualizar estructuras de índice eficientes basadas en árboles B+ para objetos en movimiento.

La estructura base del árbol Bx es un árbol B+ en el que los nodos internos sirven como directorio, cada uno de los cuales contiene un puntero a su hermano derecho. En la versión anterior del árbol Bx , [1] los nodos hoja contenían las ubicaciones de los objetos en movimiento que se indexaban y el tiempo de indexación correspondiente. En la versión optimizada, [2] cada entrada de nodo de hoja contiene el id, la velocidad, el valor de mapeo unidimensional y el tiempo de actualización más reciente del objeto. El despliegue se incrementa al no almacenar las ubicaciones de los objetos en movimiento, ya que estos pueden derivarse de los valores de mapeo .

Como para muchos otros índices de objetos en movimiento, un objeto en movimiento bidimensional se modela como una función lineal como O = ((x, y), (vx, vy), t ), donde (x, y) y (vx, vy ) son la ubicación y la velocidad del objeto en un momento dado t , es decir, el momento de la última actualización. El árbol B+ es una estructura para indexar datos unidimensionales. Para adoptar el árbol B+ como un índice de objetos en movimiento, el árbol Bx utiliza una técnica de linealización que ayuda a integrar la ubicación de los objetos en el tiempo t en un valor dimensional único. Específicamente, los objetos primero se particionan según su tiempo de actualización. Para objetos dentro de la misma partición, la B x-tree almacena sus ubicaciones en un momento dado que se estiman mediante interpolación lineal . Al hacerlo, 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 un objeto.

En segundo lugar, el espacio se divide en una cuadrícula y la ubicación de un objeto se linealiza dentro de las particiones de acuerdo con una curva que llena el espacio, por ejemplo, las curvas de Peano o 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), se indexa un objeto en el árbol B x con una clave de índice unidimensional valor B x :

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.

Un ejemplo del árbol B x con el número de particiones de índice igual a 2 dentro de un intervalo máximo de actualización tmu. En este ejemplo, existen un máximo de tres particiones al mismo tiempo. Después de la linealización, las ubicaciones de objetos insertadas en el tiempo 0 se indexan en la partición 0 con la etiqueta de marca de tiempo 0,5 tmu, las ubicaciones de objetos actualizadas durante el tiempo 0 a 0,5 tmu se indexan en la partición 1 con la etiqueta de marca de tiempo tmu, y así sucesivamente (como indican las flechas). A medida que transcurre el tiempo, el primer rango caduca repetidamente (área sombreada) y se agrega un nuevo rango (línea discontinua).