Logo Studenta

Arboles B

Vista previa del material en texto

Y otras organizaciones de 
archivos estructurados en 
forma de árbol
ESTRUCTURA DE DATOS II
/ÁRBOLES B 
9.7 -9.12
#
#
#
9.7 - 9.12
“Son árboles equilibrados que 
permiten construir los árboles hacia 
arriba a partir de la base, en lugar de 
hacerlo hacia abajo desde la cima”. 
● Evitan toda dificultad. 
● Permiten que la raíz emerja, en 
vez de colocarla y después 
encontrar la manera de 
cambiarla.
¿Qué propone el 
árbol B?
/Árboles B: construcción ascendente 
ESTRUCTURA DE DATOS II
Problema anterior
● Se requiere que el nodo raíz divida 
parejamente el conjunto de las otras 
llaves
○ Al tener raices incorrectas, se 
requiere pensar en algoritmos 
rebuscados de reacomodo. 
-
● ¿Cómo evitar que se agrupen llaves 
incorrectas en una página? ¿Cómo 
garantizar que una página tenga un 
número mínimo de llaves?
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
/División y 
promoción
/9.8
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
/9.8 Componentes del árbol
Nodo / Pagina
● Secuencia ordenada de llaves y 
un conjunto de apuntadores. 
● Si existen K claves, existen K+1 
apuntadores/hijos
● En donde K1 < K2 < K3
Orden / Grado
● Es el número máximo de apuntadores 
/ hijos que pueden almacenarse en 
un nodo 
○ Un árbol B de grado M puede 
tener M hijos y M-1 claves .
○ Los nodos tienen al menos M/2 
hijos, menos la raíz que puede 
tener menos, incluso 1.
○ Los nodos tienen al menos M-1 
claves, excepto la raíz.
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Orden / Grado
Ejemplos de árboles B de orden M
M = 4 M = 3 
3 llaves y 4 apuntadores 2 llaves y 3 apuntadores 
* * * * * * *
#
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Más sobre nodos y un ejemplo
Figura 9.14 pagina 421
Nodo de orden 8: 7 llaves y 8 apuntadores 
A B C D E F G* * * * * * * *
Los campos marcados con asteriscos (*) son los campos apuntadores.
● En este ejemplo, que es un nodo hoja, todos los apuntadores apuntan a -1 (posición inválida), 
indicando el final de la lista. En este caso, esta hoja también es la raíz. 
● En la práctica los apuntadores también tienen información adicional, como una referencia al 
registro que contiene datos asociados con la llave, almacenado en otro lugar.
● La hoja inicial del árbol puede tener una estructura similar a esta. 
#
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
1. Construir la primera hoja
Cuando se insertan nuevas llaves, 
solo se usa un acceso al disco para 
transferir la página a memoria e 
insertar la llave en su lugar en la 
página. 
Al trabajar en memoria electrónica, 
la inserción resulta relativamente 
barata, comparada con el costo de 
los accesos adicionales al disco.
/9.8 Cómo se crea el árbol
A B C D E F G* * * * * * * *
Se deben insertar llaves hasta llegar 
al máximo de llaves que se pueden 
tener de acuerdo al orden.
Nodo de orden 8 con 7 claves
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
2. Agregar llaves nuevas
Supóngase que se quiere 
insertar la llave J y se 
encuentra que el nodo ya 
está lleno (ya tiene 7 llaves). 
Se debe dividir el nodo 
anterior en 2 hojas distintas 
tan equitativamente como 
sea posible con las claves 
que se tenían.
/9.8 Cómo se crea el árbol
A B C D E F G* * * * * * * * *J
Se verifica que la hoja ya excede su orden 
al insertar la J
A B C D* * * * * * * * E F G J* * * * * * * *
Se crean dos hojas separadas para acomodar la J
Figura 9.15 pagina 422
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
3. Crecimiento del árbol
Como ahora se tienen dos 
hojas, es necesario crear un 
nivel superior en el árbol 
para que, cuando se esté 
buscando una llave, se 
pueda elegir entre ellas. 
Es necesario crear una raíz 
nueva. Para ello, se 
promueve una llave que 
separe las hojas. 
/9.8 Cómo se crea el árbol
En este caso, se promueve la E de la 
primera posición en la segunda hoja
A B C D* * * * * * * * F G J* * * * * * *
*
Figura 9.16 pagina 422
E* * * * * * * *
En este ejemplo la división y promoción se hace en dos pasos, 
pero en la práctica se hacen en una sola operación. 
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Ejemplo de cómo crece un árbol B
Figura 9.17 y 9.18, páginas 423 y 424
Se quiere insertar la secuencia 
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
en un árbol B de grado 4
C D S 1. Se inserta C, S, D en orden alfabetico
C D S T
2. Se inserta T en orden alfabetico, 
identificamos que excede el orden y 
pomocionamos tercer llave
S
TC D
3. Se promueve la S, del lado izq van las letras antes de la S, y 
del derech., las letras que van después
0
0
0 1
2
Excede!!
#
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Ejemplo de un árbol B
Figura 9.17 y 9.18, páginas 423 y 424
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
4. Se inserta la A en hoja existente y M
S
TA C D M0 1
2
5. Se promueve la D
D S
TA C 1
2
0 M 3
6. Se inserta P, I, B, W en hojas existentes y ND S
T WA B C 1
2
0 I M N P 3
Excede!!
Excede!!
#
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Ejemplo de un árbol B
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
7. Se promueve N
D N S
A B C
1
2
0 I M
3 4
8. Se inserta G, U, R en las hojas existentes y K
P T W
D N S
A B C
1
2
0 I G K M
3 4
P R T U W
Excede!!
9. Se promueve K
D K N S
A B C
1
2
0 I G
3 4
P R T U W
Excede!!
M
5
#
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Ejemplo de un árbol B
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
10. Se promueve N, se inserta E en hojas existentes,
y se inserta H 
D K
A B C
1
2
0 3
4
P R T U W
S
N
E G H I M
7
6
5
Excede!!Antes
Figura 9.17 y 9.18, páginas 423 y 424
#
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Ejemplo de un árbol B
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
Antes
D H K
A B C
1
2
0 3
4
O P R T U W Y
S
N
E G L M
7
6
5
Excede!!11. Se promueve la H, se inserta O, L, J, en hojas 
existentes, y se inserta Y
I J
8
Figura 9.17 y 9.18, páginas 423 y 424
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Ejemplo de un árbol B
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
Antes
D H K
A B C
1
2
0 3
4
O P Q R T U
S W
N
E G L M
7
6
5
Excede!!
12. Se promueve la W, y se inserta la Q
I J
8
Y
9
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Ejemplo de un árbol B
C S D T A M P I B W N G U R K E H O L J Y Q Z F X V
Antes
D H K
A B C
10
2
0 3
4
O P R
Q S W
N
L M
7
6
5
13. Se promueve la Q , y se inserta la Z, F, X, V en hojas existentes
I J
8
1
E F G
T U V
X Y Z
9
Figura 9.17 y 9.18, páginas 423 y 424
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Notese que…
● El árbol siempre está 
perfectamente balanceado con 
respecto a la altura; la trayectoria 
que va de la raíz a una hoja es la 
misma para todas las hojas.
● Las llaves que se promueven hacia 
arriba son necesariamente el tipo 
de llaves que se desean en la raíz.
● Al trabajar por encima del nivel de 
hoja, dividiendo y promoviendo 
conforme se llenan las páginas, se 
evitan los problemas que plagaron 
a los árboles binarios paginados. 
D H K
A B C
10
2
0 3
4
O P R
Q S W
N
L M
7
6
5
I J
8
1
E F G
T U V
X Y Z
9
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
/Algoritmos para la 
búsqueda e inserción 
en árboles B
/9.9
#
#
#
ESTRUCTURA DE LA PÁGINA.
 Existen formas diferentes de construir páginas de un árbol B.
Parte de un 
árbol B.
Árbol B de orden cuatro.
Un nodo interno y 4 nodos hoja.
Contenido de las 
páginas 2 y 3.
La búsqueda es un buen punto para comenzar 
porque ilustra las características de la mayoría de 
los algoritmos para los árboles B:
/9.9 Inserción, división y promoción 
ESTRUCTURA DE DATOS II
Funcionan en dos estepas
Operando en un forma alterna 
sobre las páginas enteras
Y desde dentro de las páginas
#
#
#
#
El procedimiento de búsqueda se 
llama así mismo para localizar una 
página y después busca en ella hasta 
que encuentra la llave por niveles de 
manera descendente hasta que ya 
no pueda descender más. 
/9.9 Inserción, división y promoción 
ESTRUCTURA DE DATOS II
5
3 7
641 8
#
##
#
FUNCION: busca (NRR, LLAVE, NRR_ENCONTRADO, POR_ENCONTRADA)
Si NRR==NULO entonces
Devuelve NO ENCONTRADA
Otro
Lee la página NRR en PÁGINA
Busca LLAVE en PÁGINA, haciendo POS igual a la posición donde LLAVE este 
o debería estar,
/9.9 Inserción, división y promoción 
ESTRUCTURA DE DATOS II
FUNCION BUSQUEDA
#
#
#
#
Si se encontró la LLAVE entonces
NRR_ENCONTRADO:= NRR
POS_ENCONTRADA := POS
Devuelve ENCONTRADA
Otro
Devuelve (busca {PAGINA. HIJO[POS], LLAVE, NRR_ENCONTRADO. 
POS_ENCONTRADA})
Fin FUNCION
/9.9 Inserción, división y promoción 
ESTRUCTURA DE DATOS II
#
#
#
#
NO ENCONTRADA esta se devuelve en varios niveles de posiciones con 
return() hasta que la llamada busca() recibe la información de que no 
encontró la llave
/9.9 Inserción, división y promoción 
ESTRUCTURA DE DATOS II
#
#
#
#
Hay 2 observaciones 
importantes que pueden hacerse 
acerca del proceso de inserción, 
división y promoción:
/9.9 Inserción, división y promoción 
En consecuencia, se puede pensar en el 
procedimiento recursivo con tres fases; 
ESTRUCTURA DE DATOS II
□ Comienza con una búsqueda que 
llega abajo hasta el nivel de hoja, y 
□ Después de encontrar el lugar de 
inserción en el nivel hoja, el trabajo 
de inserción, división y promoción 
continúa en forma ascendente desde 
abajo.
#
#
#
#
1.-
Un paso de búsqueda en páginas que, como en función buscaO, ocurre antes de llamada recursiva
2.-
La llamada recursiva misma, que mueve la operación hacia abajo en el árbol conforme 
busca ya sea la llave o el lugar para insertarla, y
3.-
La lógica de inserción, división y promoción que se ejecuta después de la llamada recursiva; 
la acción tiene lugar en la trayectoria de vuelta luego del descenso recursivo.
ESTRUCTURA DE DATOS II
/9.9 Inserción, división y promoción 
#
#
/9.9 Inserción
ESTRUCTURA DE DATOS II
Se necesita un ejemplo de una inserción para que pueda verse el trabajo del procedimiento de inserción a lo 
largo de estas fases. Se va a insertar el carácter $ dentro del árbol que se muestra en la mitad superior de la 
figura 9,22, que contiene todas las letras del alfabeto. 
D H K
A B C
O P R
Q S W
N
L M
I JE F G
T U V
X Y Z
#
#
/9.9 Inserción
Ahora se estudiará cómo la función insertaO realiza esta división y promoción. Puesto 
que la función opera en forma recursiva, es importante comprender cómo se usan en 
llamadas sucesivas los argumentos de la función. La función insertaO que se describe 
emplea cuatro argumentos:
ESTRUCTURA DE DATOS II
NRR_ACTUAL
El NRR de la página del árbol 
B que se usa actualmente. 
Como la función desciende y 
asciende recursivamente en 
el árbol, se usan todos los 
NRR en la trayectoria de 
búsqueda e inserción.
LLAVE 
La llave que se va a 
insertar. 
LLAVE_PROMO 
Argumento que se usa sólo para 
regresar el valor devuelto. Si de la 
inserción resultan una división y 
la promoción de una llave, 
LLAVE_PROMO contiene la llave 
promovida en el regreso 
ascendente del árbol
HIJO_D_PROMO
Este es otro valor de 
argumento devuelto. Si 
hay una
#
#
/9.9 Diagrama
La figura 9.23 ilustra la forma en que cambian los valores de estos argumentos 
cuando se llama a la función insertaO y ésta se llama a sí misma para efectuar 
la inserción del carácter $. La figura señala varios puntos importantes: 
ESTRUCTURA DE DATOS II
ANTES DE $ DESPUES DE $
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Función InsertaO
➢ Durante el paso de búsqueda de la inserción, mientras la 
función se llama a sí misma sólo NRR_ACTUAL cambia, 
haciendo el descenso en el árbol. 
➢ El paso de búsqueda termina cuando NRR_ACTUAL es 
NULO; ya no existen niveles adicionales en donde se pueda 
buscar.
➢ Conforme regresa cada llamada recursiva, se ejecuta la lógica 
de inserción y división en ese nivel.
 
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
➢ Si la función de nivel inferior devuelve el valor PROMOCION, 
entonces se tiene una llave para insertar en este nivel. 
➢ En caso contrario, no hay nada que hacer y sólo regresa.
➢ Una vez que se codifica la función insertaO emplea varias 
funciones de apoyo, una de ellas es divideO
La cual crea una página 
nueva, distribuye las 
llaves entre una página 
original y la nueva.
Además determina 
cuál llave y cuál NRR 
hay que promover.
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Variables locales importantes.
➢ PAGINA: La página que de momento está examinando insertaO* 
➢ PAGINA_NUEVA: La nueva página que se crea si ocurre una 
división.
➢ POS: La posición en PAGINA donde ocurre la llave (si está 
presente) u ocurriría (si se inserta). 
➢ NRR_P_A: El número relativo de registro promovido desde abajo 
y hasta este nivel Si ocurre una división en el siguiente nivel 
inferior.
➢ PAGINA LLAVE_P_A La llave promovida desde abajo y hasta 
este nivel. Esta llave, junto con NRR_P_A, se inserta en 
PAGINA.
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Pseudocodigo de función Inserta
si NRR_ACTUAL - NULO entonces 
devuelve PROMOCION
leer la página de NRR_ACTUAL en PAGINA r I V
buscar la LLAVE en PAGINA
POS: - la posición en donde esta debería estar LLAVE
si se encuentra LLAVE entonces
emitir mensaje de error indicando llave duplicada devuelve ERROR
VALOR_DEVUELTO inserta (PAGINA.HIJO [POS], LLAVE, NRR_P_A, LLAVE_P_A)
si VALOR_DEVUELT0 - - NO PROMOCION o ERROR entonces
devuelve VALOR_DEVUELTO otro si hay espacio en PAGINA para LLAVE_P_A 
entonces insertar LIAVE_P_A y NRR_P_A (promovida desde abajo, en PAGINA 
devuelve NO PROMOCION otro divide (LLAVE_P_A, NRR_P___A, PAGINA, 
LLAVE_PR0M0, HIJ0_D PROMO, PAGINANUEVA) " escribe PAGINA al archivo 
en el NRR_ACTUAL escribe PAGINANUEVA al archivo en el nrr
HIJO_D_PROM0 devuelve PROMOCION
fin FUNCION
La función PROMOCION 
dado que un nuevo índice 
ha sido creado en este 
nivel, la nueva llave debe 
ser insertada en el 
siguiente nodo con un 
nivel más alto.
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Divide
-Ocurre cuando al realizar una inserción nos percatamos que el nodo tiene más 
claves de lo permitido.
-Se busca pivote que será la mediana de los elementos L
-Trasladamos las claves e hijos mayores que L a un nuevo nodo y las retiramos 
del nodo viejo
-Empujamos el pivote hacia arriba del arbol aunque este puede colapsar.
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Divide
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Pseudocodigo “divide”
PROCEDIMIENTO: divide (LLAVEI, NRRJ, PAGINA, LLAVE_PROMO,
HIJO_D_PR0MO, PAGINANUEVA)
copiar todas las llaves y apuntadores de PAGINA en una página de
trabajo que puede almacenar una llave adicional y un hijo,
insertar LLAVE_I y NRR_I en sus lugares correctos en la página de
Trabajo.
asignar e iniciar nueva página en el archivo del árbol B para que
contenga PAGINANUEVA.
asignar a LLAVE_PROMO el valor de la llave de enmedio, la cual será
promovida después de la división.
asignar a HIJO_D_PROM0 el NRR de PAGINANUEVA.
copiar las llaves y apuntadores a los hijos que preceden a
LIAVE_PR0MO, de la página de trabajo a PAGINA.
copiar las llaves y apuntadores a los hijos que siguen a LLAVE PROMO,
de la página de trabajo a PAGINANUEVA. 
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Pseudocodigo “Manejador”
PROCEDIMIENTO PRINCIPAL: manejador
si el archivo del árbol B existe, entonces
abrir el archivo del árbol B otro
crear un archivo de árbol B y colocar la primera llave en la raiz 
tomar el NRR de la página raiz del archivo y almacenarla en RAIZ 
tomar una llave y almacenarla en LLAVE mientras existan llaves
si (inserta (RAIZ, LLAVE, HIJO_D_PROMO, LLAVE_PROMOJ — PROMOCION)
Entonces
crear una nueva página raiz con la llave : - fllJO_D__PROMO 
■'/"¡
hijo izquierdo :- RAIZ e hijo derecho HIJO_D_PROMO 
asignar*T*AIZ el NRR de la nueva página raiz tomar la 
siguiente llave y almacenarla en LIAVE^fin
mientras escribe el NRR almacenado en RAI2 de regreso al 
archivo del árbol
B cerrar el archivo del árbol
fin PROCEDIMIENTO PRINCIPAL
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
/Nomenclaturade árboles B.
/9.10
#
#
#
● Antes de pasar al análisis del desempeño de los árboles B y a las 
variaciones sobre sus algoritmos básicos, es necesario formalizar la 
terminología sobre los árboles B.
Orden de un árbol B: Es el mínimo número de llaves que 
pueden estar dentro de una página de un árbol.
Bayer y McCreight [1972], Comer [1979] y algunos 
otros se refieren.
Orden 3.
Máximo de 7 llaves.
Pero hay un problema con esta definición debido a que se vuelve difícil de 
aplicar cuando se toman en cuenta páginas que almacenan un número máximo 
de llaves que es impar. 
Hay que considerar considérese la siguiente pregunta: 
dentro del esquema de Bayer y McCreight, 
¿la página de un árbol B de la orden tres está llena cuando 
contiene seis llaves o cuando contiene siete? 
Knuth [1973b] y otros han resuelto la confusión.
Knuth [1973b] y otros 
definieron el orden de un 
árbol B como:
El número máximo de descendientes 
que puede tener una página. 
8 descendientes.
7 llaves.
● Un árbol B de orden 8 tiene un máximo de 
7 llaves por página.
● Un árbol B de orden m, el número máximo 
de llaves por página es m -1
Defiere de Bayer y McCreight en dos aspectos: 
1
Hace referencia a un máximo, no a un mínimo, y cuenta 
descendientes en vez de llaves.
2
El número de llaves en una página de árbol B siempre es 
uno menos que el número de descendientes de la 
página.
Cuando se divide la 
página de un árbol B, 
los descendientes se 
dividen lo más 
equitativamente posible 
entre la página nueva y 
la vieja. 
En consecuencia, cada 
página, excepto la raíz 
y las hojas, tiene al 
menos m/2 
descendientes. 
Expresado en términos de una función de redondeo 
hacia arriba:
El mínimo número de descendientes es [m/2].
Se concluye que el mínimo número de llaves por 
página es [m/2-1].
El ejemplo es de orden ocho, significa:
Que no puede almacenar más de siete llaves 
por página.
Todas las páginas, excepto la raíz, contienen por 
lo menos tres llaves.
¿QUE ES UNA HOJA?
Bayer y 
McCreight 
Otros autores, 
entre ellos Knuth
• Las hojas están 
en un nivel por 
debajo del nivel 
más bajo de 
llaves. 
En otras 
palabras.
• Consideran que 
las hojas son los 
registros de 
datos reales a 
los cuales 
puede apuntar 
el nivel más 
bajo de llaves 
del árbol. 
• Se refieren al 
nivel más bajo 
de llaves dentro 
de un árbol B 
como el nivel 
hoja.
ESTRUCTURA DE DATOS II
9.7 - 9.12
/Definición formal 
de las propiedades 
de los árboles B
/9.11
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
9.11 Propiedades del árbol B
Con estas definiciones de orden y hoja puede formularse una definición 
precisa de las propiedades de un árbol B de orden m: 
1. Cada página tiene un 
máximo de m descendientes. 
2. Cada página, excepto la raíz y las 
hojas, tiene por lo menos [m/2] 
descendientes. 
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
9.11 Propiedades del árbol B
3. La raíz tiene por lo 
menos dos descendientes 
(a menos que sea una 
hoja). 
4. Todas las hojas aparecen en el mismo 
nivel. 
5. Una página que no es hoja con k 
descendientes contiene k -1 llaves. 
6. Una página hoja contiene por lo 
menos [m/2] -1 llaves y no más de m - 1 
llaves.
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
/Profundidad de 
la búsqueda en 
el peor caso
/9.12
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
9.12 ¿Que es el peor caso?
El número de descendientes de cualquier nivel de un árbol B es 1 + el número de llaves 
contenidas en ese nivel y todos los que lo preceden.
El peor caso ocurre cuando cada página del árbol sólo contiene el número mínimo de 
descendientes. En tal caso las llaves se distribuyen sobre una altura máxima para el árbol 
y una amplitud mínima. 
Peor caso
número máximo de 
accesos a disco 
requeridos
Profundidad del 
árbol= =
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Árbol B de 27 llaves
Figura 9.28 de la página 442
B D K
H N
E F GS A T U V
Q S W
C I J L M O P R X Y Z
**Un árbol B con N cantidad de llaves puede tener (fV+1) descendientes a partir del nivel de hoja.
***Este árbol contiene 27 llaves pero 28 descendientes.
#
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
9.12 Profundidad
Para un árbol B de orden M, el número mínimo de descendientes a partir de la página 
raíz es dos, así que el segundo nivel del árbol contiene sólo dos páginas. Cada una de 
estas páginas, a su vez, tiene al menos [m/2]^(d-1) descendientes. Por tanto, el tercer 
nivel contiene 2 veces eso = 2 * [m/2]^(d-1).
Así, en general, para cualquier nivel d de un árbol B, el mínimo número de 
descendientes que se extienden a partir de ese nivel es N + 1 => 2 x [m/2]^(d-1).
Ahora ya sabemos que un árbol con N llaves tiene N + 1 descendientes desde su nivel 
hoja. A la profundidad del árbol en el nivel hoja se le llamará d. puesto que se sabe 
que el número de descendientes de cualquier árbol no puede ser menor que el 
número para el peor caso de un árbol de esa profundidad. 
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
Arbol B de 27 llaves
Figura 9.28 de la página 442
B D K
H N
E F GS A T U V
Q S W
C I J L M O P R X Y Z
d d d d d d d d d d d d d d d d d d d d d d d d d d d
Al despejar d nos entrega la siguiente expresión.
d <= 1 + log[m/2]((N +1)/2).
#
#
#
#
ESTRUCTURA DE DATOS II
9.7 - 9.12
9.12 Ejemplo
 Para un árbol B de 1 000 000 llaves, es razonable emplear 
un árbol B de orden 512 (un máximo de 511 llaves por 
página). 
Un árbol de orden 512 que contenga 1 000 000 de llaves. Al 
sustituir estos números específicos dentro de la expresión
Se encuentra que d <= log[256](500000.5) , entonces d <= 
3.37. 
De esta manera se puede decir que, dadas 1000 000 de 
llaves, un árbol B de orden 512 tiene una profundidad de no 
más de tres niveles.
M = 511 +1
N + 1 = 1 000 001
d<= log[512/2](1 000 001/2)
d<=3.37
#
#
#
/BIBLIOGRAFÍA
● Folk, M. (1992). Estructuras de Archivos. Addison-Wesley Iberoamericana. 
Delaware, EUA.
ESTRUCTURA DE DATOS II
9.7 - 9.12
#
#
#

Otros materiales

Materiales relacionados

100 pag.
NC30G233

SIN SIGLA

User badge image

gabriela_nunez1992

85 pag.
Franch_Arboles

User badge image

Materiales Generales

Preguntas relacionadas

Otros materiales