Hacer btree y B + árboles sólo almacenan datos en las hojas?

Question

b Los árboles y árboles B sólo almacenar datos en sus hojas? Estoy asumiendo que utilizan sus nodos internos para buscar los datos necesarios.

¿Es que el caso o no se almacenan datos en cada nodo?

Answer 1

nodos que no son hojas "registros" contienen

• un puntero (una "dirección" del nodo de tipo) a un nodo en el siguiente nivel inferior del árbol
• el valor de la clave de la primera (o la última, dependiendo de la aplicación) récord en ese nodo

Tal no hoja "registros" se enumeran en el orden de la clave para que los escaneos (o de búsqueda binaria dentro de) un nodo no hoja, se sabe que el nodo en el siguiente nivel inferior pueden contener la valor buscado.

Discos de hoja nodos contienen registros de datos completos: el valor de la clave y cualquier otra cosa

.

Por lo tanto datos "real", sólo está contenida en los nodos hoja, los nodos que no son hojas sólo contienen [una copia de] los valores de clave. para una proporción muy pequeña de los datos (esta proporción depende del número promedio de registros de datos encontradas en un nodo hoja).

Esto se ilustra en la siguiente imagen de la href="http://en.wikipedia.org/wiki/B%2B_tree" rel="nofollow noreferrer"> artículo

El nodo no hoja, en la parte superior, (el único en este árbol simplista) sólo contiene dos registros de nodo no hoja, cada uno con una copia de un valor de clave (color azulado) y un puntero al nodo correspondiente (color gris). Este árbol sucede sólo para tener dos niveles, por lo tanto, los "registros" en el punto de nodo raíz a los nodos hoja. Uno puede imaginar que hay niveles adicionales (por encima del árbol superior se muestra a continuación, llaman el "3-5 nodo"); si ese fuera el caso, el nodo anterior contendría (junto con otros registros similares), un registro con valor de clave 3 con un puntero a la "3-5" nodo.
Nota también que sólo los valores de clave 3 y 5 están contenidos en los nodos que no son hojas (es decir, ni siquiera todos valores de clave se reproducen en los no foliares nodos).
 Por cierto, en este ejemplo, los nodos que no son hojas contienen la clave de la última registro en el siguiente nodo (también funcionaría si el primero registro se utilizaron en cambio, una ligera diferencia en el manera se implementa la lógica de búsqueda).

Los nodos hoja contienen el valor de la clave (en color azul también) y el correspondiente registro de datos (D1, D2 ... se muestra en gris). El puntero rojo-ish se muestra al final de cada punto de nodo de hoja al siguiente nodo de hoja, es decir, el que contiene el siguiente registro de datos en un orden clave; estos punteros son útiles para "scan" una serie de registros de datos.

Answer 2

Todos los datos están en las hojas.

Wiki en B + .

Answer 3

Hay una cierta confusión en Btrees y B + Árboles. B + Árboles solamente almacenar datos en los nodos hoja como punteros. Esto significa que los datos deben ser almacenados en otro lugar. Btrees pueden almacenar datos en todos los nodos. Hay ventajas y desventajas de cada uno. Me he dado cuenta de que algunos sitios muestran Btrees exactamente igual que los árboles B +. En general, Btrees son mejores para almacenar los datos reales, y B + Los árboles son mucho más eficientes como índices.