Organizacion de archivos
Páginas: 7 (1520 palabras)
Publicado: 9 de julio de 2013
Organización de Archivos
Catedrático: Josué Bladimir Jiménez Castro
Tema: Arboles B y AVL
Derechos reservados Junior Guillen
Objetivos
Comentar los inicios del concepto
de arboles B
Describir los arboles AVL
Ejercitar sobre el reconocimiento
de arboles AVL
El artículo de R. Bayer y E. McCreight
A finales de los 60’s el objetivo era el
descubrimiento de un método generalpara el almacenamiento y extracción de
datos en grandes sistemas de archivos que
proporcionan acceso rápido a la
información y a un costo mínimo.
Entre los competidores estaban R. Bayer y
E. McCreight, quienes trabajaban
entonces para la corporación Boeing. Y fue
en 1972 cuando estos dos personajes
mostraron al mundo los árboles B
mediante un interesante artículo.
La invención de losárboles B
Las ciencias de la computación son una disciplina joven. Es increíble pensar
que en 1970, cuando el hombre ya había viajado dos veces a Luna, ni
siquiera existían los árboles B. Hoy en día 40 años después es difícil imaginar
un gran sistema de archivos de propósito general que no esté construido con
árboles B.
A finales de los 60’s el objetivo era el descubrimiento de un método deun método general para el almacenamiento y extracción de datos en
grandes sistemas de archivos que proporcionan acceso rápido a la
información y a un costo mínimo. Entre los competidores estaban R.
Bayer y E. McCreight, quienes trabajaban entonces para la corporación
Boeing. Y fue en 1972 cuando estos dos personajes mostraron al mundo
los árboles B mediante un interesante artículo.
Hastadonde hemos venido estudiando hemos visto el gran problema
que es mantener la información guardada en disco y tener que accesarla,
clasificarla y volverla a escribir. Demos un pequeño vistazo al artículo de
estos dos personajes:
La invención de los árboles B
La invención de los árboles B
¡La gran innovación de los árboles B!
Este esquema que propone que el tiempo de encontrar unregistro en un archivo es
, donde k esta relacionado con el tamaño de la página, es muy
significativo. Por ejemplo, si tenemos un uso de árboles B con páginas de 64, para
indizar un archivo con 1,000,000 de registros, permite encontrar la llave de
cualquier registro con no más de 4 desplazamientos de disco. Si lo hiciéramos
empleando búsqueda binaria esto nos tomaría 20 desplazamientos.
Antes deadentrarnos de lleno en el
tema haremos un pequeño repaso
de conceptos preliminares para
apreciar a su totalidad la magnífica
estructura que R. Bayer y E.
McCreight lograron.
¿Por qué el nombre de árbol B?
El origen del árbol B nunca fue explicado por sus creadores. Muchos creen que la B,
es de “Balanceado”, “Amplio” (en inglés Broad) o “Arborescente” ( en inglés bushy).
Otros dicenque la B sugiere Boeing (la empresa donde laboraban las dos personas
que lo inventaron). Sin embargo parece apropiado pensar en los árboles B como
árboles Bayer (por el apellido del creador)
Planteamiento del Problema
El problema fundamental de mantener un índice en almacenamiento secundario es,
por supuesto, que el acceso a la información es demasiado lento. Y podemos dividir el
problemaen dos partes específicas:
1. La búsqueda binaria requiere demasiados desplazamientos.
2. Puede ser muy costoso mantener el índice ordenado para que sea posible efectuar
una búsqueda binaria: insertar una nueva llave en el índice implica reordenamiento
total del archivo indexado y esa operación resulta muy cara a nivel de
almacenamiento secundario
Planteamiento del Problema
El problemafundamental de mantener un
índice en almacenamiento secundario es, por
supuesto, que el acceso a la información es
demasiado lento. Y podemos dividir el
problema en dos partes específicas:
1. La búsqueda binaria requiere
demasiados desplazamientos.
2. Puede ser muy costoso mantener el
índice ordenado para que sea posible
efectuar una búsqueda binaria:
insertar una nueva llave en el...
Catedrático: Josué Bladimir Jiménez Castro
Tema: Arboles B y AVL
Derechos reservados Junior Guillen
Objetivos
Comentar los inicios del concepto
de arboles B
Describir los arboles AVL
Ejercitar sobre el reconocimiento
de arboles AVL
El artículo de R. Bayer y E. McCreight
A finales de los 60’s el objetivo era el
descubrimiento de un método generalpara el almacenamiento y extracción de
datos en grandes sistemas de archivos que
proporcionan acceso rápido a la
información y a un costo mínimo.
Entre los competidores estaban R. Bayer y
E. McCreight, quienes trabajaban
entonces para la corporación Boeing. Y fue
en 1972 cuando estos dos personajes
mostraron al mundo los árboles B
mediante un interesante artículo.
La invención de losárboles B
Las ciencias de la computación son una disciplina joven. Es increíble pensar
que en 1970, cuando el hombre ya había viajado dos veces a Luna, ni
siquiera existían los árboles B. Hoy en día 40 años después es difícil imaginar
un gran sistema de archivos de propósito general que no esté construido con
árboles B.
A finales de los 60’s el objetivo era el descubrimiento de un método deun método general para el almacenamiento y extracción de datos en
grandes sistemas de archivos que proporcionan acceso rápido a la
información y a un costo mínimo. Entre los competidores estaban R.
Bayer y E. McCreight, quienes trabajaban entonces para la corporación
Boeing. Y fue en 1972 cuando estos dos personajes mostraron al mundo
los árboles B mediante un interesante artículo.
Hastadonde hemos venido estudiando hemos visto el gran problema
que es mantener la información guardada en disco y tener que accesarla,
clasificarla y volverla a escribir. Demos un pequeño vistazo al artículo de
estos dos personajes:
La invención de los árboles B
La invención de los árboles B
¡La gran innovación de los árboles B!
Este esquema que propone que el tiempo de encontrar unregistro en un archivo es
, donde k esta relacionado con el tamaño de la página, es muy
significativo. Por ejemplo, si tenemos un uso de árboles B con páginas de 64, para
indizar un archivo con 1,000,000 de registros, permite encontrar la llave de
cualquier registro con no más de 4 desplazamientos de disco. Si lo hiciéramos
empleando búsqueda binaria esto nos tomaría 20 desplazamientos.
Antes deadentrarnos de lleno en el
tema haremos un pequeño repaso
de conceptos preliminares para
apreciar a su totalidad la magnífica
estructura que R. Bayer y E.
McCreight lograron.
¿Por qué el nombre de árbol B?
El origen del árbol B nunca fue explicado por sus creadores. Muchos creen que la B,
es de “Balanceado”, “Amplio” (en inglés Broad) o “Arborescente” ( en inglés bushy).
Otros dicenque la B sugiere Boeing (la empresa donde laboraban las dos personas
que lo inventaron). Sin embargo parece apropiado pensar en los árboles B como
árboles Bayer (por el apellido del creador)
Planteamiento del Problema
El problema fundamental de mantener un índice en almacenamiento secundario es,
por supuesto, que el acceso a la información es demasiado lento. Y podemos dividir el
problemaen dos partes específicas:
1. La búsqueda binaria requiere demasiados desplazamientos.
2. Puede ser muy costoso mantener el índice ordenado para que sea posible efectuar
una búsqueda binaria: insertar una nueva llave en el índice implica reordenamiento
total del archivo indexado y esa operación resulta muy cara a nivel de
almacenamiento secundario
Planteamiento del Problema
El problemafundamental de mantener un
índice en almacenamiento secundario es, por
supuesto, que el acceso a la información es
demasiado lento. Y podemos dividir el
problema en dos partes específicas:
1. La búsqueda binaria requiere
demasiados desplazamientos.
2. Puede ser muy costoso mantener el
índice ordenado para que sea posible
efectuar una búsqueda binaria:
insertar una nueva llave en el...
Leer documento completo
Regístrate para leer el documento completo.