El orden de b-trees

Question

Estoy estudiando para un examen y se me ocurrió B-trees. Wikipedia describe un árbol B como un árbol donde los nodos tienen al menos d y como máximo 2d claves y, por lo tanto, a lo sumo 2d + 1 hojas. Por ejemplo, si d = 1, tendría un máximo de 2 claves y 3 hijos, lo que lo convertiría en un árbol 2-3. Sin embargo, esto no permitiría, por ejemplo, un árbol 2-3-4 a menos que esté equivocado.

Sin embargo, nuestro material describe un b-tree como un árbol donde cada nodo tiene al menos t> = 2 t-1 teclas y como máximo 2t-1 teclas. Esto significaría que los nodos tienen un número impar de claves y un número par de hijos. Por ejemplo, t = 2 tendría de 1 a 3 teclas y hasta 4 hijos, lo que lo convertiría en un árbol 2-3-4. Por otro lado, no podría haber un árbol 2-3 con esta notación.

Además de esto, hay una anotación de Knuth donde d significa la cantidad máxima de hijos en un nodo. Esta notación permitiría tanto el número impar como el igual de niños, permitiendo 2-3 árboles y 2-3-4 árboles.

Sé que existen 2-3 árboles y 2-3-4 árboles.

¿Cuál es la notación real? ¿Hay una notación real? Como una pregunta adicional; ¿Cuál es el número máximo de claves en un árbol de tamaño h?

Answer 1

Si lee el artículo de la wiki un poco más de cerca, verá que hay dos variantes principales de B-trees (excluidas las variantes estructurales como B * y B +), uno con t ->2t claves, y una con t ->2t+1 teclas.

traducir esas variantes a #children tenemos uno con t+1 ->2t+1 los niños, y uno con t+1 ->2t+2 niños.

Así que, esencialmente para responder a su pregunta, ambos 2-3 y 2-3-4 árboles son válidos los árboles, cada uno de acuerdo a una variante/definición diferente:

2-3 es del primer tipo (t+1 - >2t+1 niños donde t = 1)

2-3-4 es del segundo tipo (t+1 ->2t+2 niños donde t = 1)

la validez de ambas variantes se deriva del hecho de que las dos divisiones y fusiones (las acciones realizadas en eliminar e insertar desde/hacia el ADT) son válidas:

t ->2t:

Split. Ocurre cuando agregamos un nuevo elemento y un nodo tiene más que el número máximo de claves 2t Tenemos las claves 2t+1, dividimos el nodo en dos nodos, y enviamos un elemento al padre, dejando las claves 2t en los dos hijos y t claves en cada niño. Esto es aceptable porque la cantidad mínima de claves en un nodo es de hecho t.

Combinar. Ocurre cuando eliminamos una clave y un nodo contiene menos que el número mínimo, t, y su hermano también es el mínimo. Así que tenemos las claves t-1 + t en nuestro nuevo nodo fusionado, el nodo resultante debe ser válido: t-1 + t = 2t-1 <= 2t. Estupendo.

Lo mismo sucede con t ->2t+1:

Split. 2t+2 se convierte en t y t+1, lo que está bien.

Combinar. t-1 + t = 2t-1 <= 2t+1

Por supuesto, no hay ninguna diferencia en tiempos de funcionamiento, es sólo una ligera diferencia aplicación de poca importancia teórica (puede optimizar ligeramente algunos algoritmos con la primera variante, pero no tanto que se va a cambiar complejidades en tiempo de ejecución)

Answer 2

búsqueda en Google Scholar para comer b árbol => ubicua árbol B, Comer, 1979

Este es el artículo más citado que se encuentra en los documentos de la estructura de datos. Este documento describe el árbol b en detalle (cómo funciona, la complejidad y sus variantes ...). Ahí deberías encontrar tu respuesta.

Espero que esto ayude

p.s. cite ese papel en el examen si usa una fórmula diferente a la que se enseña: P