antes de entender árbol B y árbol B+ diferencias, debemos conocer el árbol B y el árbol B+ por separado.

¿Qué es el árbol B?

árbol B es un árbol autoequilibrado y es un árbol de m vías donde m define el orden del árbol. árbol es una generalización de la Árbol de búsqueda binaria en el que un nodo puede tener más de una clave y más de dos hijos dependiendo del valor de metro . En el árbol B, los datos se especifican en un orden ordenado que tiene valores más bajos en el subárbol izquierdo y valores más altos en el subárbol derecho.

java cómo convertir una cadena a int

Propiedades del árbol B

Las siguientes son las propiedades del árbol B:

• En el árbol B, todos los nodos hoja deben estar en el mismo nivel, mientras que, en el caso de un árbol binario, los nodos hoja pueden estar en diferentes niveles.

Entendamos esta propiedad a través de un ejemplo.

En el árbol de arriba, todos los nodos de hoja no están en el mismo nivel, pero tienen como máximo dos hijos. Por lo tanto, podemos decir que el árbol anterior es un árbol binario pero no un árbol B.

• Si el Btree tiene un orden de m, entonces cada nodo puede tener un máximo de metro En el caso de hijos mínimos, los nodos hoja tienen cero hijos, el nodo raíz tiene dos hijos y los nodos internos tienen un techo de m/2.
• Cada nodo puede tener claves máximas (m-1). Por ejemplo, si el valor de m es 5, entonces el valor máximo de las claves es 4.
• El nodo raíz tiene como mínimo una clave, mientras que todos los demás nodos, excepto el nodo raíz, tienen (techo de m/2 menos - 1) claves mínimas.
• Si realizamos la inserción en el árbol B, entonces el nodo siempre se inserta en el nodo hoja.

Supongamos que queremos crear un árbol B de orden 3 insertando valores del 1 al 10.

Paso 1: Primero, creamos un nodo con 1 valor como se muestra a continuación:

Paso 2: El siguiente elemento es 2, que viene después de 1 como se muestra a continuación:

Paso 3: El siguiente elemento es 3 y se inserta después de 2 como se muestra a continuación:

Como sabemos que cada nodo puede tener 2 claves como máximo, dividiremos este nodo a través del elemento central. El elemento del medio es 2, por lo que se mueve a su padre. El nodo 2 no tiene ningún padre, por lo que se convertirá en el nodo raíz como se muestra a continuación:

Etapa 4: El siguiente elemento es 4. Dado que 4 es mayor que 2 y 3, se agregará después del 3 como se muestra a continuación:

Paso 5: El siguiente elemento es 5. Dado que 5 es mayor que 2, 3 y 4, se agregará después de 4 como se muestra a continuación:

Como sabemos que cada nodo puede tener 2 claves como máximo, dividiremos este nodo a través del elemento central. El elemento del medio es 4, por lo que se mueve a su padre. El padre es el nodo 2; por lo tanto, se agregará 4 después de 2 como se muestra a continuación:

Paso 6: El siguiente elemento es 6. Dado que 6 es mayor que 2, 4 y 5, 6 vendrá después de 5 como se muestra a continuación:

Paso 7: El siguiente elemento es 7. Dado que 7 es mayor que 2, 4, 5 y 6, 7 vendrá después de 6 como se muestra a continuación:

Como sabemos que cada nodo puede tener 2 claves como máximo, dividiremos este nodo a través del elemento central. El elemento del medio es 6, por lo que se mueve a su padre como se muestra a continuación:

Pero no se puede agregar 6 después de 4 porque el nodo puede tener 2 claves como máximo, por lo que dividiremos este nodo por el elemento del medio. El elemento del medio es 4, por lo que se mueve a su padre. Como el nodo 4 no tiene ningún padre, el nodo 4 se convertirá en un nodo raíz como se muestra a continuación:

¿Qué es un árbol B+?

El árbol B+ También se conoce como árbol autoequilibrado avanzado porque cada camino desde la raíz del árbol hasta la hoja del árbol tiene la misma longitud. Aquí, la misma longitud significa que todos los nodos de las hojas se encuentran en el mismo nivel. No sucederá que algunos de los nodos de las hojas ocurran en el tercer nivel y otros en el segundo nivel.

Un índice de árbol B+ se considera un índice multinivel, pero la estructura del árbol B+ no es similar a los archivos secuenciales de índice multinivel.

¿Por qué se utiliza el árbol B+?

Se utiliza un árbol B+ para almacenar los registros de manera muy eficiente al almacenar los registros de manera indexada utilizando la estructura indexada del árbol B+. Gracias a la indexación de varios niveles, el acceso a los datos se vuelve más rápido y sencillo.

Estructura de nodo del árbol B+

La estructura de nodos del árbol B+ contiene punteros y valores clave que se muestran en la siguiente figura:

Como podemos observar en la estructura de nodos del árbol B+ anterior, contiene n-1 valores clave (k₁a k_n-1) y n punteros (p₁arriba_norte).

Los valores de la clave de búsqueda que se colocan en el nodo se mantienen ordenados. Así, si yoij.

Restricción en varios tipos de nodos.

Sea 'b' el orden del árbol B+.

Nodo no hoja

Sea 'm' el número de hijos de un nodo, entonces la relación entre el orden del árbol y el número de hijos se puede representar como:

Sea k representa los valores de la clave de búsqueda. La relación entre el orden del árbol y la clave de búsqueda se puede representar como:

Como sabemos que el número de punteros es igual a los valores de la clave de búsqueda más 1, matemáticamente se puede escribir como:

bash para el bucle 1 al 10

Número de punteros (o hijos) = Número de claves de búsqueda + 1

Por lo tanto, el número máximo de punteros sería 'b' y el número mínimo de punteros sería la función límite de b/2.

Nodo hoja

Un nodo hoja es un nodo que ocurre en el último nivel del árbol B+, y cada nodo hoja usa solo un puntero para conectarse entre sí para proporcionar acceso secuencial en el nivel hoja.

En el nodo hoja, el número máximo de hijos es:

El número máximo de claves de búsqueda es:

Nodo raíz

El número máximo de hijos en el caso del nodo raíz es: b

El número mínimo de niños es: 2

Casos especiales en el árbol B+

Caso 1: Si el nodo raíz es el único nodo del árbol. En este caso, el nodo raíz se convierte en el nodo hoja.

En este caso, el número máximo de hijos es 1, es decir, el nodo raíz en sí, mientras que el número mínimo de hijos es b-1, que es el mismo que el de un nodo hoja.

Representación de un nodo hoja en el árbol B+

En la figura anterior, '.' representa el puntero, mientras que 10, 20 y 30 son los valores clave. El puntero contiene la dirección en la que se almacena el valor de la clave, como se muestra en la figura anterior.

Ejemplo de árbol B+

En la figura anterior, el nodo contiene tres valores clave, es decir, 9, 16 y 25. El puntero que aparece antes de 9 contiene los valores clave menores que 9 representados por k_i. El puntero que aparece antes de 16 contiene los valores clave mayores o iguales a 9 pero menores a 16 representados por kj. El puntero que aparece antes de 25 contiene los valores clave mayores o iguales a 16 pero menores a 25 representados por k_norte.

Diferencias entre el árbol B y el árbol B+

Las siguientes son las diferencias entre el árbol B y el árbol B+: