1 Introducción


1.1 Antecedentes

  • Discos son lentos
    • Gran capacidad de Almacenamiento
    • Lavadoras  --->  Dispositivos Actuales 5 1/4"
  • Lentitud
    • RAM          120 nanosegundos
    • DiscoDuro     30 milisegundos
    • Indice Libro              20 segundos
    • Pedirlo a la Librería   58 días

 

Objetivo ideal :

"Un buen diseño de estructuras de archivos* brindará acceso a grandes capacidades de información, sin gastar tiempo de espera por el disco"

*Estructura de Archivos: combinación de representaciones de datos en archivos y las operaciones para accesarlos
 


 
 

1.1.1 Metas en el desarrollo de estructuras de archivos:

  • Idealmente obtener la información necesaria únicamente con un acceso a disco
  • Si no, encontrar lo deseado  con el menor número de accesos posibles. Ej. Binary Search
  • Agrupar la información de manera que encontremos todo lo que buscamos con un solo viaje a disco

 

Windows Task Manager

 

Linux KDE System Guard


Si los archivos no cambiaran todo sería más fácil, pero en la práctica no es así   :(
 
 
 

1.2 Historia

1.2.1 Cintas

Al principio el medio de almacenamiento eran las cintas, un acceso secuencial
 

 

1.2.2 Discos

Surgen los discos y con ello los "índices"
 

 

Problema: cuando la información cambia mucho --dinámicamente
 
 

1.2.3 Arboles  

En 1960's nace la idea de emplear árboles
 
 
 

 

Problema: pueden formarse accesos secuenciales
 


 
 

1963 AVL Trees
 
 
 

Problemas:

  • Docenas de accesos para búsquedas
  • Método para mantener balanceado el árbol

 
 

...y 10 años despues 1973
Toman forma los B-Trees
 
 

Complejidad O(logk N)

N elementos en un archivo,  k elementos indexados en cada bloque
 
 
 

B+Trees
 
 


 
1.2.4 Hash  

Qué pasó con la meta de un solo viaje al disco ??
 

  • Funciones de Hash


                Registro   ----> Hash  ---->  Dirección

 

Era poco conveniente para archivos dinámicos por eso surje el Hash Extendido, Hash + B-Trees

 

 

1.3 Era Moderna

Desde los 90´s Internet empieza a tomar un gran impuso:

  • Millones de sitios
  • Millones de paginas
  • Millones de correos electronicos -- emails

• WWW = 170 TB
• Email = 400,000 TB por año
• Chat = 274 TB por año

Preguntas:

  • Cómo discernir algo "importante" de lo que no es ??
  • Cómo catalogar automáticamente la información ??

 

Utilizar una búsqueda por palabra ya no es suficiente

Se emplean técnicas basadas en:

  • Frecuencia de palabras
  • Popularidad (Incoming links)
  • Curiosamente inventadas en los 70´s Ej. Modelo Vectorial de Salton

 

Un proyecto iniciado en 1995 y que en el 2000 alcanza el premio:
"Best Search Engine on the Internet"

 

Surgen otras necesidades respecto a la información:

  • Intercambiar
  • De hacerla legible a la vista humana
  • De mantener la estructura/semiestructura de datos

1998 nace XML (eXtensible Markup Language)

<?xml version="1.0" encoding="UTF-8"?>

<DOCUMENT>

<SUBJECT>UDLA Informa </SUBJECT>

<MESSAGE>Blah Blah Blah</MESSAGE>

</DOCUMENT>

 

1.4 Conclusión

El reto de almacenar y recuperar información se puede resumir en 2 aspectos muy importantes

  1. Recuperar la información en el menor tiempo posible
  2. Recuperar exactamente lo que el usuario desea

Algo muy importante a recordar: las necesidades de recuperación serán las que determinen las técnicas de almacenamiento a emplear.