CLASE 9 ARBOL B
Páginas: 7 (1503 palabras)
Publicado: 16 de septiembre de 2015
ESTRUCTURA DE INFORMACION
Árbol B
Docente: Carlos A. Ruiz De La Cruz Melo
Correo: ruizdelacruzmelo@uigv.edu.pe
ARBOL B
Un árbol B es un árbol de m ramas, con paginas
también denominadas nodos, que almacenan un
máximo de m-1 claves y que tienen las siguientes
características:
El número mínimo de claves por nodo es (m/2)-1,
excepto la raíz que puede tener menos.
En un árbol B, los nodos hojasestán en un mismo
nivel.
El árbol siempre tiende a estar ordenado.
Un árbol del cual parten m ramas, registrara un
máximo de m-1 claves por nodo.
Un factor básico en un árbol B es el orden (m), el
cual nos dice que es el número máximo de ramas
que pueden salir de un nodo.
Porque usar arboles B ?
Los arboles B se usan cuando existe
un volumen de información a
procesar tan grande que se hacenecesario almacenarla en disco, y en
el cual los arboles ABB simples o
arboles AVL no hacen un buen
tiempo de acceso a la información
registrada en memoria secundaria.
EJEMPLO DE ARBOL B
Un nodo con
espacio para
4 claves
Ejemplo de un árbol-B de ORDEN 5 y de
profundidad 2.
16
5
10
81
45
78
85
97
99
EJEMPLO DE NO ARBOL B
COMO ES DE ORDEN 5
DEBE TENER CADA NODO
2 CLAVES COMO MINIMO
16
510
45
ARBOL B vs ABB y AVL
ABB
AVL
Un ABB o un AVL solo puede
registrar un dato en cada nodo, lo
que causa que el acceso a disco
se haga cada vez que se cargue
un dato en el árbol.
DISCO
Arbol B
VENTAJAS DE ARBOLES B
Para gran cantidad de información esencialmente cuando los nodos
se alojan en almacenamiento secundario, evitando el uso reiterado de
acceso al disco.
La ventaja de un árbolB es que al tener un control sobre el número de
nodos hijos que pueda tener un nodo interno, la altura del árbol
disminuye, las tareas de tener que equilibrar el árbol también
disminuyen, aumentando por consecuencia la eficiencia de la
estructura.
El número de consultas en un árbol B se puede predecir.
El número de consultas no aumentara con el numero de
registros a ordenar como si sucede con unárbol ABB simple.
DESVENTAJA DE ARBOLES B
El mantener un árbol B es mas complejo, tal es
así que una operación de ingresar, borrar o
modificar causa en un nodo unión o desunión
obligando a una serie de operaciones para
equilibrar el árbol.
INSERCION DE CLAVES
Al insertar 44 las
claves tienen el orden
siguiente:
Las claves se van ordenando
automáticamente en un árbol B
16, 44, 56, 67, 81
Sepromociona la clave
del medio
16
56
16
56
56
67
81
67
56
44
67
56
81
56
67
81
16
44
67
81
INSERCION
Insertamos: 72, 63
56
16
44
63
67
72
81
Luego insertamos: 95
56
16
44
72
63
67
81
95
INSERCION
Se insertan los siguientes valores:
8, 20, 26, 33, 48, 52, 84, 99
20
8
44
56
16
72
63
48
26
33
67
81
84
95
99
52
El árbol ha completado
el
nodo
raíz,…quesucede si insertamos
el valor 90
Se promociona la
clave del centro y
sube al nodo raiz.
INSERCION
Pero ya esta lleno!
90
20
8
16
44
56
63
48
26
33
52
72
67
81
84
95
99
INSERCION
Finalmente queda
el árbol como se
muestra
56
20
8
44
72
48
16
26
33
90
52
63
67
95
81
84
99
ELIMINACION DE CLAVES
Se eliminara la clave 85
43
12
38
48
43
12
38
73
63
76
85
9563
76
95
98
73
48
98
ELIMINACION DE CLAVES
Se eliminara la clave 73
43
12
38
48
43
12
38
38
63
76
85
95
98
63
73
85
95
98
76
48
43
12
73
76
48
63
85
95
98
ELIMINACION DE CLAVES
Se eliminara la clave 48
43
12
38
48
43
12
38
73
63
76
85
95
76
63
73
85
95
98
98
ELIMINACION DE CLAVES
Se eliminara la clave12
43
12
38
73
48
63
76
85
9598
76
85
95
98
73
38
43
48
63
ARBOL B +
El árbol B es bueno para la búsqueda de un elemento del
árbol mediante su clave, limitando la cantidad de accesos al
soporte drásticamente.
No obstante, si lo que se desea es encontrar un elemento y
a partir de allí leer secuencialmente los siguientes
elementos, nos encontramos a un problema difícil de
solucionar que nos lleva al peor de los...
Árbol B
Docente: Carlos A. Ruiz De La Cruz Melo
Correo: ruizdelacruzmelo@uigv.edu.pe
ARBOL B
Un árbol B es un árbol de m ramas, con paginas
también denominadas nodos, que almacenan un
máximo de m-1 claves y que tienen las siguientes
características:
El número mínimo de claves por nodo es (m/2)-1,
excepto la raíz que puede tener menos.
En un árbol B, los nodos hojasestán en un mismo
nivel.
El árbol siempre tiende a estar ordenado.
Un árbol del cual parten m ramas, registrara un
máximo de m-1 claves por nodo.
Un factor básico en un árbol B es el orden (m), el
cual nos dice que es el número máximo de ramas
que pueden salir de un nodo.
Porque usar arboles B ?
Los arboles B se usan cuando existe
un volumen de información a
procesar tan grande que se hacenecesario almacenarla en disco, y en
el cual los arboles ABB simples o
arboles AVL no hacen un buen
tiempo de acceso a la información
registrada en memoria secundaria.
EJEMPLO DE ARBOL B
Un nodo con
espacio para
4 claves
Ejemplo de un árbol-B de ORDEN 5 y de
profundidad 2.
16
5
10
81
45
78
85
97
99
EJEMPLO DE NO ARBOL B
COMO ES DE ORDEN 5
DEBE TENER CADA NODO
2 CLAVES COMO MINIMO
16
510
45
ARBOL B vs ABB y AVL
ABB
AVL
Un ABB o un AVL solo puede
registrar un dato en cada nodo, lo
que causa que el acceso a disco
se haga cada vez que se cargue
un dato en el árbol.
DISCO
Arbol B
VENTAJAS DE ARBOLES B
Para gran cantidad de información esencialmente cuando los nodos
se alojan en almacenamiento secundario, evitando el uso reiterado de
acceso al disco.
La ventaja de un árbolB es que al tener un control sobre el número de
nodos hijos que pueda tener un nodo interno, la altura del árbol
disminuye, las tareas de tener que equilibrar el árbol también
disminuyen, aumentando por consecuencia la eficiencia de la
estructura.
El número de consultas en un árbol B se puede predecir.
El número de consultas no aumentara con el numero de
registros a ordenar como si sucede con unárbol ABB simple.
DESVENTAJA DE ARBOLES B
El mantener un árbol B es mas complejo, tal es
así que una operación de ingresar, borrar o
modificar causa en un nodo unión o desunión
obligando a una serie de operaciones para
equilibrar el árbol.
INSERCION DE CLAVES
Al insertar 44 las
claves tienen el orden
siguiente:
Las claves se van ordenando
automáticamente en un árbol B
16, 44, 56, 67, 81
Sepromociona la clave
del medio
16
56
16
56
56
67
81
67
56
44
67
56
81
56
67
81
16
44
67
81
INSERCION
Insertamos: 72, 63
56
16
44
63
67
72
81
Luego insertamos: 95
56
16
44
72
63
67
81
95
INSERCION
Se insertan los siguientes valores:
8, 20, 26, 33, 48, 52, 84, 99
20
8
44
56
16
72
63
48
26
33
67
81
84
95
99
52
El árbol ha completado
el
nodo
raíz,…quesucede si insertamos
el valor 90
Se promociona la
clave del centro y
sube al nodo raiz.
INSERCION
Pero ya esta lleno!
90
20
8
16
44
56
63
48
26
33
52
72
67
81
84
95
99
INSERCION
Finalmente queda
el árbol como se
muestra
56
20
8
44
72
48
16
26
33
90
52
63
67
95
81
84
99
ELIMINACION DE CLAVES
Se eliminara la clave 85
43
12
38
48
43
12
38
73
63
76
85
9563
76
95
98
73
48
98
ELIMINACION DE CLAVES
Se eliminara la clave 73
43
12
38
48
43
12
38
38
63
76
85
95
98
63
73
85
95
98
76
48
43
12
73
76
48
63
85
95
98
ELIMINACION DE CLAVES
Se eliminara la clave 48
43
12
38
48
43
12
38
73
63
76
85
95
76
63
73
85
95
98
98
ELIMINACION DE CLAVES
Se eliminara la clave12
43
12
38
73
48
63
76
85
9598
76
85
95
98
73
38
43
48
63
ARBOL B +
El árbol B es bueno para la búsqueda de un elemento del
árbol mediante su clave, limitando la cantidad de accesos al
soporte drásticamente.
No obstante, si lo que se desea es encontrar un elemento y
a partir de allí leer secuencialmente los siguientes
elementos, nos encontramos a un problema difícil de
solucionar que nos lleva al peor de los...
Leer documento completo
Regístrate para leer el documento completo.