Construyendo secuencialmente los árboles B completos

Question

Si tengo un conjunto de datos ordenados, que quiero almacenar en el disco de una manera que sea óptima tanto para leer secuencialmente como para hacer búsquedas aleatorias, parece que un árbol B (o una de las variantes es una buena opción. .. suponiendo que este conjunto de datos no se ajuste a la RAM).

La pregunta es ¿se puede construir un árbol B completo a partir de un conjunto ordenado de datos sin hacer ninguna división de página? Para que los datos ordenados se puedan escribir en el disco secuencialmente.

Answer 1

Construir un "árbol B+" a esas especificaciones es simple.

1. Elija su factor de ramificación k.
2. Escriba los datos ordenados en un archivo. Este es el nivel de la hoja.
3. Para construir el siguiente nivel más alto, escanee el nivel actual y escriba cada k^th artículo.
4. Detente cuando el nivel actual tenga k elementos o menos.

Ejemplo con k = 2:

0 1|2 3|4 5|6 7|8 9
0   2  |4   6  |8
0       4      |8
0               8

Ahora buscamos 5. Use la búsqueda binaria para encontrar el último número menor o igual a 5 en el nivel superior, o 0. Mire el intervalo en el siguiente nivel más bajo correspondiente a 0:

0       4

Ahora 4:

        4   6

Ahora 4 otra vez:

        4 5

Lo encontré. En general, el J^th Sin embargo, el elemento corresponde a los elementos JK (j+1) K-1 en el siguiente nivel. También puede escanear el nivel de la hoja linealmente.

Answer 2

Podemos hacer un árbol B en un solo pase, pero puede que no sea el método de almacenamiento óptimo. Dependiendo de la frecuencia con las consultas secuenciales frente a las de acceso aleatorio, puede ser mejor almacenarlo en secuencia y usar la búsqueda binaria para dar servicio a una consulta de acceso aleatorio.

Dicho esto: Suponga que cada registro en su árbol B se mantiene (M - 1) llaves (metro > 2, el caso binario es un poco diferente). Queremos que todas las hojas en el mismo nivel y todos los nodos internos tengan al menos (m - 1) / 2 llaves. Sabemos que un árbol B completo de altura k posee (M^K - 1) llaves. Suponga que tenemos norte Keys Total para almacenar. Dejar k ser el entero más pequeño de tal manera que m^k - 1> n. Ahora si 2 m^(k - 1) - 1 <n Podemos llenar completamente los nodos internos y distribuir el resto de las claves de manera uniforme a los nodos de la hoja, cada nodo de la hoja obtiene el piso o el techo de (n + 1 - m^(k - 1))/m^(k - 1) llaves. Si no podemos hacer eso, entonces sabemos que tenemos suficiente para llenar todos los nodos en profundidad K - 1 Al menos a mitad de camino y almacene una llave en cada una de las hojas.

Una vez que hemos decidido la forma de nuestro árbol, solo necesitamos hacer un recorrido por orden del árbol que coloque secuencialmente las teclas en posición a medida que avanzamos.

Answer 3

Significado óptimo de que una transversión de los datos siempre buscará avanzar a través del archivo (o región mmaped), y una búsqueda aleatoria se realiza en un número mínimo de busca.