En informática , un árbol KDB ( árbol B de dimensión k ) es una estructura de datos en forma de árbol para subdividir un espacio de búsqueda de dimensión k . El objetivo del árbol KDB es proporcionar la eficiencia de búsqueda de un árbol kd equilibrado , al mismo tiempo que proporciona el almacenamiento orientado a bloques de un árbol B para optimizar los accesos a la memoria externa. [1]
Descripción informal
Al igual que el árbol k -d, un árbol KDB organiza puntos en un espacio k -dimensional, lo que resulta útil para tareas como la búsqueda de rangos y las consultas a bases de datos multidimensionales. Los árboles KDB subdividen el espacio en dos subespacios comparando elementos en un único dominio. Si tomamos como ejemplo un árbol 2-DB (árbol KDB bidimensional), el espacio se subdivide de la misma manera que un árbol k -d: si utilizamos un punto en solo uno de los dominios, o ejes en este caso, todos los demás valores son menores o mayores que el valor actual y caen a la izquierda y a la derecha del plano de división, respectivamente.
A diferencia de un árbol k -d, cada semiespacio no es su propio nodo. En cambio, como en un árbol B, los nodos del árbol KDB se almacenan como páginas y el árbol almacena un puntero a la página raíz.
Estructura
La estructura básica de un árbol KDB.
El árbol KDB contiene dos tipos de páginas:
Páginas de región: una colección de pares (región, hijo) que contienen una descripción de la región delimitante junto con un puntero a la página hija correspondiente a esa región.
Páginas de puntos: una colección de pares (punto, ubicación) . En el caso de las bases de datos, la ubicación puede apuntar al índice del registro de la base de datos, mientras que para los puntos en un espacio de k dimensiones, puede verse como las coordenadas del punto en ese espacio.
Los desbordamientos de página se producen cuando la inserción de un elemento en un árbol KDB hace que el tamaño de un nodo supere su tamaño óptimo. Dado que el propósito del árbol KDB es optimizar los accesos a la memoria externa, como los que se realizan desde un disco duro, se considera que una página se ha desbordado o está sobrellenada si el tamaño del nodo supera el tamaño de la página de la memoria externa.
Durante las operaciones de inserción/eliminación, el árbol KDB mantiene un determinado conjunto de propiedades:
El gráfico es un árbol multidireccional. Las páginas de región siempre apuntan a páginas secundarias y no pueden estar vacías. Las páginas de puntos son los nodos de hoja del árbol.
Al igual que un árbol B, la longitud de la ruta a las hojas del árbol es la misma para todas las consultas.
Las regiones que componen una página de región están disjuntas.
Si la raíz es una página de región, la unión de sus regiones es todo el espacio de búsqueda.
Cuando el hijo de un par (región, hijo) en una página de región también es una página de región, la unión de todas las regiones en el hijo es región .
Por el contrario, en el caso anterior, si child es una página de puntos, todos los puntos en child deben estar contenidos en region .
Operaciones en un árbol KDB
Consultas
Las consultas en un árbol KDB son una búsqueda de rangos en intervalos en todos los dominios o ejes del árbol. Esta colección de intervalos se denomina región de consulta . En el espacio k , la región de consulta se puede visualizar como un volumen delimitador alrededor de algún subespacio en todo el espacio de búsqueda k -dimensional. Una consulta puede pertenecer a una de tres categorías:
Algunos intervalos abarcan un dominio o eje completo, lo que hace que la consulta sea una consulta de rango parcial .
Algunos intervalos son puntos, otros son dominios completos y, por lo tanto, la consulta es una consulta de coincidencia parcial .
Los intervalos son todos puntos, por lo que el volumen delimitador también es solo un punto. Esta es una consulta de coincidencia exacta .
Algoritmo
Si la raíz del árbol es nula, terminar, de lo contrario dejar que la página sea la raíz .
Si la página es una página de puntos, devuelve cada punto en un par (punto, ubicación) que se encuentre dentro de la región de consulta .
De lo contrario, la página es una página de región, por lo que para todos los pares (región, hijo) donde la región y la región de consulta se cruzan, configure la página como hija y recurra desde el paso 2.
Inserciones
Dado que una inserción en un árbol KDB puede requerir la división de una página en el caso de un desbordamiento de página, es importante definir primero la operación de división.
Algoritmo de división
Primero, una página de región se divide a lo largo de un plano para crear dos nuevas páginas de región, la página izquierda y la página derecha. Estas páginas se llenan con las regiones de la página de región anterior, y la página de región anterior se elimina. Luego, para cada ( región , hijo ) en la página de región original, recordando que hijo es una página y región especifica una región delimitadora real:
Si la región se encuentra completamente a la izquierda del plano de división, agregue (región, hijo) a la página izquierda.
Si la región se encuentra completamente a la derecha del plano de división, agregue (región, hijo) a la página derecha.
De lo contrario:
Divida recursivamente al niño por el plano de división, lo que da como resultado las páginas new_left_page y new_right_page
Región dividida por el plano de división, lo que da como resultado región_izquierda y región_derecha
Agregue (left_region, new_left_page) a la página izquierda y (right_region, new_right_page) a la página derecha.
Algoritmo de inserción
La importancia de elegir el dominio de división correcto.
Utilizando el algoritmo de división, las inserciones de un nuevo par (punto, ubicación) se pueden implementar de la siguiente manera:
Si la página raíz es nula, simplemente haga que la página raíz sea una nueva página de puntos que contenga (punto, ubicación)
Si se realiza una consulta de coincidencia exacta en un punto para buscar la página a la que se debe agregar ese punto . Si ya existe en la página, finalice.
Añade (punto, ubicación) a la página. Si la página se desborda, deja que page indique esa página.
Sea old_page igual a page . Elija algún elemento y un dominio/eje para definir un plano por el cual dividir la página , lo que dará como resultado dos páginas que no resulten en que una de las páginas se llene en exceso con la adición de un nuevo punto. Divida la página por el plano para crear dos páginas nuevas, new_left_page y new_right_page , y dos regiones nuevas left_region y right_region .
Si la página era la página raíz, vaya al paso 6. De lo contrario, la página se convierte en la página principal de la página . Reemplace (region, old_page) en la página por (left_region, new_left_page) y (right_region, new_right_page) . Si la página se desborda, repita el paso 4; de lo contrario, finalice.
Sea left_region todo el espacio de búsqueda a la izquierda del plano de división, y right_region el espacio de búsqueda a la derecha, resultante de la división en el Paso 4. Establezca la página raíz como una página que contenga las regiones left_region y right_region .
Es importante tener cuidado con el dominio y el elemento elegidos para dividir la página , ya que es conveniente tratar de equilibrar la cantidad de puntos a ambos lados del plano de división. En algunos casos, una mala elección del dominio de división puede dar como resultado divisiones no deseadas. También es posible que una página no pueda dividirse por un determinado dominio.
Eliminaciones
Las eliminaciones de un árbol KDB son increíblemente sencillas si no se imponen requisitos mínimos de utilización del almacenamiento. Si utilizamos una consulta de coincidencia exacta para encontrar un par (punto, ubicación) , simplemente eliminamos el registro del árbol si existe.
Algoritmo de reorganización
Dado que las eliminaciones pueden dar como resultado páginas que contienen muy pocos datos, puede ser necesario reorganizar el árbol KDB para cumplir con algunos criterios mínimos de utilización del almacenamiento. El algoritmo de reorganización que se debe utilizar cuando una página contiene muy pocos datos es el siguiente:
Sea página el padre de P , que contiene (región, P) .
Encuentra regiones en la página que sean adyacentes y cuya unión forme una región rectangular. Estas regiones se consideran "unibles". Sea R el conjunto de estas regiones.
Fusionar el conjunto R en una página S y, si S está sobrecargada, dividir repetidamente hasta que ninguna de las páginas resultantes esté sobrecargada.
Reemplace el conjunto R de regiones en la página con las páginas resultantes de dividir S.
Trabajo relacionado
Al igual que en un árbol k -d, las actualizaciones en un árbol KDB pueden dar lugar a la necesidad de dividir varios nodos de forma recursiva. Esto es increíblemente ineficiente y puede dar lugar a una utilización de memoria subóptima, ya que puede dar lugar a muchas hojas casi vacías. Lomet y Salzberg propusieron una estructura denominada árbol hB (árbol de ladrillos perforados) para mejorar el rendimiento de los árboles KDB al limitar las divisiones que se producen después de una inserción a una sola ruta de raíz a hoja. Esto se logró almacenando las regiones no solo como rectángulos, sino como rectángulos con un rectángulo eliminado del centro. [2]
Árbol BKD
Más recientemente, se propuso el árbol Bkd como un medio para proporcionar consultas rápidas y una utilización del espacio cercana al 100 % de un árbol KDB estático. En lugar de mantener un solo árbol y reequilibrarlo, se mantiene y reconstruye un conjunto de árboles KDB a intervalos regulares. [3] En este caso, es el tamaño del búfer de memoria en número de puntos.
Referencias
^ Robinson, John (1981). "El árbol KDB". Actas de la conferencia internacional ACM SIGMOD de 1981 sobre gestión de datos - SIGMOD '81. Sigmod '81. págs. 10-18. doi :10.1145/582318.582321. ISBN 978-0897910408. S2CID 27482172 . Consultado el 8 de abril de 2014 .
^ Lomet, David; Betty Salzberg (diciembre de 1990). "El árbol hB: un método de indexación de atributos múltiples con un buen rendimiento garantizado". ACM Transactions on Database Systems . 15 (4): 625–658. CiteSeerX 10.1.1.63.2056 . doi :10.1145/99935.99949. S2CID 15333693.
