Arboles B+ y árboles B ¿qué son y para qué sirven?

[Mac]

Hola Comunidad tendrán algún material acerca de la temática de Arboles B y B+ que me puedan facilitar
Desde ya muchísimas Gracias por su colaboración !!!

[Alex Rodríguez]

Los árboles B+ son un tipo de estructuras de datos utilizados para la creación de índices sobre atributos de bases de datos entre otras cosas.

Los índices en forma de archivos secuenciales indexados tienen un problema: el rendimiento (tanto para buscar en el índice como para buscar registros) se degrada a medida que crece el archivo. Habría soluciones basadas en la reorganización de archivos, pero no son deseables.

La estructura en árbol B+, donde la B indica "balanceado"es la más usada de las estructuras de índices para bases de datos por mantener una buena eficiencia a pesar de la inserción y borrado de datos.

Un índice de árbol B+ toma la forma de árbol equilibrado caracterizado por un valor "n" (por ejemplo podría hablar de índice en árbol B+ para la clave de búsqueda <<ciudad>> sobre la relación <<delegaciónComercial>> con n=3)

n es un entero que implica dos cosas:

a) Cada nodo que no es hoja tiene entre n/2 y n hijos

b) Un nodo típico de un árbol B+ se estructura en hasta n-1 pares <<puntero - clave de búsqueda>> terminando con un puntero final.

Ejemplo de nodo para n=5

P1-K1|P2-K2|P3-K3|P4-K4|P5

K1, K2... son claves de búsqueda (p.ej. Caracas, Buenos Aires, Lima, Santiago, México D.F., Madrid) y se mantienen ordenadas en un nodo, de modo que Ki < Kj si i<j

En un nodo hoja un puntero Pi apunta o bien a un registro del archivo con el valor de clave de búsqueda Ki o bien a un cajón de punteros cada uno de los cuales apunta a un registro del archivo con valor de la clave de búsqueda Ki

Cada hoja Li contiene claves de búsqueda menores que otra hoja Lj

El puntero Pn se usa para encadenar los nodos hoja en el orden de la clave de búsqueda.

En los nodos internos (los que no son hoja) la estructura es análoga a la de los nodos hoja, con la diferencia de que todos los punteros son punteros a nodos del árbol.

Dado un nodo con 1, 2, ... m punteros, el puntero P1 apuntará a un nodo con valores de la clave menores que K1 y el puntero Pm apuntará a un nodo con valores de la clave mayores o iguales que Km-1

De este modo los nodos internos de un árbol B+ forman un índice multinivel (disperso) sobre los nodos hoja.

En resumen: el árbol B+ mantiene varios órdenes. Dentro de cada nodo existe orden. Entre las hojas existe orden. En los punteros dentro de un nodo existe orden.

[Mac]

Alex Rodríguez Gracias ...

Y B sola ! que quiere decir ?¿  .. por que nada mas habla de B+

[Alex Rodríguez]

Hola, un árbol B es similar a un árbol B+ con la diferencia de que mientras el árbol B+ permite la repetición de claves en nodos internos hasta llegar a los nodos hoja, el árbol B no permite la repetición.

Esto en principio supone que el árbol tiene menos nodos, pero al no ser posible la repetición se hace necesario un puntero adicional que permita ir directamente desde una clave en un nodo interno hasta el registro o cajón correspondiente. Es decir, por cada clave de un nodo interno tendremos dos punteros: uno que lleva al registro correspondiente al puntero y otro que lleva a otro nodo menor o mayor según el criterio de ordenación de claves empleado.

Los nodos hoja no requieren el puntero adicional, pero los nodos internos sí.

En estos árboles, a diferencia de B+, no siempre es necesario alcanzar un nodo hoja para concluir una búsqueda (ya que los nodos internos tienen punteros directos a registros). Esto da rapidez en el acceso a algunas claves. Pero al requerir más espacio los árboles son más profundos (tienen más niveles), y esto ralentiza el acceso a claves que se encuentren en el nivel de las hojas.