Árbol Q

Lo principal

El Árbol Q es un método de indexación dinámico diseñado para ser almacenado en memoria secundaria. Admite inserciones, modificaciones y borrado de elementos. La división del espacio se lleva a cabo utilizando hiperplanos iso-orientados que se representan mediante árboles kd.

Image
Imagen 1
Como su nombre indica, la estructura del Árbol Q es jerárquica y se crea de forma ascendente. A los nodos de esta estructura se les denomina Qnodos. Los Qnodos del nivel 0 (el nivel inferior) también llamados contenedores (o Qnodos de datos) almacenan secuencialmente un conjunto de puntos de la base de datos. En el resto de los niveles, los Qnodos (Qnodos Índices) almacenan árboles kd que representan las fronteras que separan las zonas del espacio controladas por los Qnodos del nivel inmediatamente inferior.
 
 
 
 
Image
Imagen 2
Cada vez que un Qnodo sufre una situación de sobrecarga debe ser dividido. Este proceso provoca la creación del un nuevo Qnodo, hermano del sobrecargado, así como el traslado, al Qnodo padre, de la información necesaria para controlar las nuevas fronteras creadas. 
 
Las zonas del espacio de datos que controlan los contenedores tienen la forma de un rectángulo multidimensional. Sin embargo, y al igual que ocurre con métodos de acceso como el hB-tree o el hB?-tree, la división de los árboles kd se realiza extrayendo el subárbol más adecuado y esto hace que la zona del espacio que controlan los Qnodos Índice tenga la forma de un rectángulo con agujeros. Los agujeros representan zonas que han sido extraídas de dicho Qnodo y que en ese momento están siendo controladas por otro Qnodo hermano. 
 
A pesar de que existen grandes similitudes entre el Árbol Q y el hB?-tree, el Árbol Q tiene una estructura más sencilla y homogénea. Desde nuestro punto de vista esta es una de las razones que explican su buen comportamiento y su alto grado de adaptación a diferentes contextos de trabajo.
 

Más Detalles

Para conocer con más exactitud cuales son las capacidades del Árbol Q indicaremos, en orden cronológico, los principales logros alcanzados en los últimos años:
 
  • La primera implementación del Árbol Q (1995) aportaba todos los algoritmos necesarios para crear y gestionar la estructura. La creación del índice incluía los algoritmos de división de los Qnodos de datos y Qnodos índice que permiten la paginación de la estructura. También estaban implementadas las consultas exactas, parciales y por rango.
  • Algoritmo de búsqueda del vecino más próximo (2002). Este algoritmo es especialmente útil para resolver consultas por similitud en bases de datos multimedia, de manera que la cercanía entre vectores de características se convierte en una medida de la similitud que hay entre los objetos multimedia que dichos vectores representan.
  • Gestión de las páginas mediante un sistema de buffer que permite reducir el número de accesos a disco en las operaciones de entrada y salida (2002).
  • La utilización del Árbol Q dentro del proyecto Xerka hizo necesaria la incorporación de una serie de mejoras en la implementación (2004):

  •  
    • Portabilidad de los datos. Se llevó a cabo una definición de tipos de datos independientes de la plataforma y los correspondientes algoritmos de transformación entre unos y otros tipos.

  •  
    • Diseño de un modelo de concurrencia que permite la ejecución simultánea de ciertas operaciones.

  •  
    • Nuevas operaciones: borrado y modificación de datos.

  •  
    • Adecuación del Árbol Q al modelo transaccional. Cada operación se lleva a cabo de forma atómica, consistente, aislada y durable.

  • Actualmente se trabaja básicamente en dos frentes:

  •  
    • Mejora del algoritmo de búsqueda de los vecinos más próximos

  •  
    • Incorporación de rectángulos de acotación que definan la zona realmente ocupada por los datos dentro de cada contenedor. De esta forma probablemente podrá mejorarse el control del espacio de datos cuando éstos no están uniformemente distribuidos, ya que en estos casos pueden aparecer amplías zonas del espacio vacías.

Log in