Arboles B
Páginas: 3 (624 palabras)
Publicado: 2 de septiembre de 2013
Árbol B
Introducción
Para almacenar muchos datos disco, es
necesario una estructura de datos eficiente.
Los accesos al disco son costosos en tiempo
por lo que se debe evitarrealizar muchos
accesos a los datos.
AVL es la mejor estructura para memoria
principal, pero es ineficiente si se utiliza para
almacenamiento secundario. Esto se debe a
la cantidad de accesosnecesarios para
efectuar las rotaciones. Otro problema es
que se requieren tantos accesos como
niveles se recorran en el árbol para efectuar
la búsqueda.
Árboles B
Bayer y McCreight propusieron en1970 esta
estructura.
Manejan árboles de búsqueda multicamino,
cuyos nodos guardan más de un elemento.
Son árboles 100% balanceados en su
estructura, lo cual repercute en búsquedas
eficientesy en accesos mínimos a disco.
10 20
5 8
25 65 92 99
12 18
Características del Árbol B
Un Árbol B de orden n es aquel que:
Todas las hojas del árbol están en elnivel
inferior.
Cada nodo contiene entre n y 2n
elementos, excepto el nodo raíz, que
puede tener entre 1 y 2n elementos.
Si un nodo tiene ‘m’ elementos, el nodo
siempre contendrá m + 1 hijossi no es un
nodo hoja.
Ejemplo....
Para
un Árbol B de orden 3:
Cuántos elementos máximo puede
guardar cada nodo del árbol?
6
¿Cuántos elementos mínimo puede
guardar cadanodo del árbol?
1 si el la raíz, 3 cualquier otro nodo.
¿Cuántos hijos máximo puede tener un
nodo?
7
¿Cuántos hijos mínimo puede tener un
nodo?
0 si es hoja, 2 si es raíz, 4cualquier otro nodo.
Más características del Árbol B
Un árbol B de orden n es aquél en que:
Los elementos de un nodo están ordenados
linealmente.
Los elementos están organizados de talforma que se cumple la regla de la
búsqueda: a la izquierda menores, a la
derecha mayores.
10 20
5 8
25 65 92 99
12 18
Ejemplo...
¿De qué orden es este árbol B?
10 20
5 8...
Introducción
Para almacenar muchos datos disco, es
necesario una estructura de datos eficiente.
Los accesos al disco son costosos en tiempo
por lo que se debe evitarrealizar muchos
accesos a los datos.
AVL es la mejor estructura para memoria
principal, pero es ineficiente si se utiliza para
almacenamiento secundario. Esto se debe a
la cantidad de accesosnecesarios para
efectuar las rotaciones. Otro problema es
que se requieren tantos accesos como
niveles se recorran en el árbol para efectuar
la búsqueda.
Árboles B
Bayer y McCreight propusieron en1970 esta
estructura.
Manejan árboles de búsqueda multicamino,
cuyos nodos guardan más de un elemento.
Son árboles 100% balanceados en su
estructura, lo cual repercute en búsquedas
eficientesy en accesos mínimos a disco.
10 20
5 8
25 65 92 99
12 18
Características del Árbol B
Un Árbol B de orden n es aquel que:
Todas las hojas del árbol están en elnivel
inferior.
Cada nodo contiene entre n y 2n
elementos, excepto el nodo raíz, que
puede tener entre 1 y 2n elementos.
Si un nodo tiene ‘m’ elementos, el nodo
siempre contendrá m + 1 hijossi no es un
nodo hoja.
Ejemplo....
Para
un Árbol B de orden 3:
Cuántos elementos máximo puede
guardar cada nodo del árbol?
6
¿Cuántos elementos mínimo puede
guardar cadanodo del árbol?
1 si el la raíz, 3 cualquier otro nodo.
¿Cuántos hijos máximo puede tener un
nodo?
7
¿Cuántos hijos mínimo puede tener un
nodo?
0 si es hoja, 2 si es raíz, 4cualquier otro nodo.
Más características del Árbol B
Un árbol B de orden n es aquél en que:
Los elementos de un nodo están ordenados
linealmente.
Los elementos están organizados de talforma que se cumple la regla de la
búsqueda: a la izquierda menores, a la
derecha mayores.
10 20
5 8
25 65 92 99
12 18
Ejemplo...
¿De qué orden es este árbol B?
10 20
5 8...
Leer documento completo
Regístrate para leer el documento completo.