Un hash es un algoritmo que transforma los datos que se le pasan a una cadena de caracteres de longitud fija. La longitud de los datos de entrada puede ser variable pero el resultado de aplicar el algoritmo es siempre de longitud fija.
Además, este algoritmo tiene una peculiaridad que es la que lo hace realmente útil: funciona sólo en una dirección. Es prácticamente imposible, obtener los datos de entrada a partir de la salida del algoritmo
Un hash se emplea cuando tengamos un conjunto ilimitado de valores de entrada y queramos obtener un conjunto limitado de valores resultado. Normalmente, los valores de entrada serán cadenas de caracteres de longitud variable, que convertiremos en cadenas de longitud fija. Aunque este tipo de funciones admiten todo tipo de datos de entrada. Además, los resultados de la función pueden delimitarse a un conjunto definido de caracteres: enteros y alfanuméricos.
En la imagen siguiente puedes ver el comportamiento de una función hash:
Ahora que ya sabemos como funcionan los árboles binarios de búsqueda, vamos a estudiar como trabajar con ellos. Las operaciones con árboles binarios de búsqueda que podemos realizar son: Búsqueda, inserción y eliminación de un nodo.
Búsqueda de un nodo
Cuando queremos recuperar datos de nuestra estructura de árbol binario de búsqueda, sacaremos provecho de que estas estructuras están ordenadas. Básicamente, empezaríamos comprobando el nodo raíz, y si este es el que buscamos, ya hemos acabado. Si no lo es, nos moveríamos a su hijo izquierdo o al derecho, dependiendo de si el dato que buscamos es menor o mayor del que contiene el nodo padre. Y así proseguiríamos hasta encontrar el dato o terminar de recorrer el árbol sin encontrarlo.
Este proceso es recursivo, ya que cuando nos movemos a un nodo hijo, podemos considerar a este como el nodo raíz de un nuevo árbol. El proceso de búsqueda podría expresarse como:
Flujo para la búsqueda de un nodo
Que también podríamos representar en seudocódigo de la siguiente manera:
Encontrado (Arbol, buscado){
Si no existe Arbol -> No encontrado
Si existe Arbol {
Si valor Raiz= buscado ->Encontrado
Si valor Raiz <> buscado{
Si valor Raiz >buscado{
árbol = nodo izquierdo
Encontrado(Arbol, buscado)
}
Si valor Raiz < buscado{
árbol = nodo derecho
Encontrado(Arbol, buscado)
}
}
}
}
Un árbol binario de búsqueda es una estructura ordenada de datos donde cada registro puede estar relacionado con otros dos registros. Vamos a prestar especial atención a los árboles binarios de búsqueda, ya que son muy populares y ampliamente utilizados en BBDD. Como ya adelantaba en el post anterior, los arboles binarios son de orden 2, es decir, sus nodos pueden tener un máximo de dos hijos. Y si además es de búsqueda, tiene que cumplir las siguientes condiciones para todos los nodos:
Si el nodo tiene un hijo izquierdo, este tiene que ser menor que él.
Si el nodo tiene un hijo derecho, este tiene que ser mayor que él.
Después de los archivos de acceso aleatorio que explicaba en otro post, aparece el acceso indexado para corregir los principales inconvenientes de aquellos. Los archivos de acceso aleatorio suponían una reducción considerable en el tiempo de búsqueda de un dato sobre los archivos de acceso secuencial. Sin embargo, había que conocer exactamente el número de registro del dato que querías buscar, lo cual es muy poco práctico, ya que normalmente querremos buscar por valores en los distintos campos.
Los archivos de acceso aleatorio nos permiten ir directamente a recuperar el registro deseado, sin necesidad de leer antes todos los anteriores. Solucionan de esta manera la principal limitación de los archivos de acceso secuencial, que era precisamente su método de acceso a los datos, la necesidad de recorrer todo el fichero desde el principio hasta llegar al punto que nos interesaba. Esta limitación se hacia cada vez más grande, según aumentaba el tamaño de nuestro fichero. Con un alto número de registros, los tiempos de lectura podían extenderse demasiado, hasta el punto de ser muy poco operativos y propiciar la migración a un fichero de acceso aleatorio.
La primera opción de almacenamiento digital que se empleo fueron los archivos de acceso secuencial, ficheros con una cierta estructura para almacenar los datos pero muy lejos todavía de las bases de datos.
Pongámonos al inicio de la segunda mitad del siglo XX, cuando nuestro protagonista Antonio comienza a pasar a formato digital los datos de su tienda SuperGades. La opción que por entonces tiene disponible es sencillamente pasar los datos de un fichero en papel a un fichero digital, empleando un procesador de textos muy sencillo con muy pocas funcionalidades, en el que escribiríamos los datos sin ningún tipo de formato. A este fichero, se le denomina también archivo, tomando el nombre de su antecedente analógico, un fichero físico con cajones donde guardábamos las fichas con los datos. Si estuviéramos almacenando los datos de los proveedores, el archivo podría tener un aspecto similar a:
Frutas Gutierrez
Antonio Gutierrez
607454545
Hortalizas del Sur
Guillermo Morales
652854874
Azucarera Sevillana
Rodrigo Mendez
622525885
En este archivo hemos escrito los datos de nuestros proveedores uno detrás de otro, como lo haríamos en un cuaderno. Hemos generado un archivo secuencial, que recibe este nombre porque los datos se almacenan uno detrás de otro, y el acceso a los mismos será de forma secuencial, es decir, tengo que recorrer el archivo desde el principio hasta llegar al dato que quiero recuperar.
La marca EOF (End of File)
Esta manera de trabajar obligaba a incluir algún tipo de marca que nos indicara que habíamos llegado al final del archivo, de otro modo, obtendríamos un error al intentar leer un dato más allá del final del archivo. Esta marca es el carácter de final de archivo EOF.
Desde siempre, las organizaciones han tenido que guardar y procesar distintos tipos de datos para su funcionamiento. La organización física de los datos para su posterior explotación, ha constituido una de las prioridades de las citadas organizaciones. Cuando no contábamos con ordenadores, hace ya bastantes años, registrábamos los datos en papeles que almacenábamos en archivadores. Armarios con cajones, los cuales consultábamos cuando necesitábamos recuperar alguno de dichos datos.
Esta organización de los datos, nos obligaba a disponer de grandes espacios para su almacenamiento y requería de un gran esfuerzo de registro. Además presentaba otros muchos inconvenientes. Cada vez que queríamos acceder a un dato, teníamos que emplear un tiempo considerable para localizarlo. El acceso era exclusivo, de tal manera que si alguien estaba consultando un dato, este no estaba disponible para nadie más. Todo esto sin mencionar las escasas posibilidades con las que se contaba para el tratamiento de los datos.
La digitalización de los datos
Posteriormente, con la llegada de la electrónica digital y los ordenadores, comenzamos a guardar estos datos en formato digital, lo cual facilitaba enormemente el almacenamiento, distribución y recuperación de los datos. Primero en un archivo digital, posteriormente en una base de datos y finalmente en varias bases de datos de distintos tipos. En estos últimos años, la disponibilidad y las capacidades de almacenamiento y tratamiento de los datos, se han visto sensiblemente aumentadas, dando lugar a lo que ha venido a denominarse “Big Data”.
Primera Digitalización
Empezaremos nuestro recorrido con las primeras técnicas digitales de almacenamiento y tratamiento de datos, posteriormente profundizaremos en los distintos tipos de bases de datos y su gestión, para terminar, presentando el entorno Big Data. Para recorrer este camino, me apoyare en un ejemplo ficticio de una empresa para así mejor mostrar la evolución de las distintas arquitecturas de datos que han ido dando respuestas a las crecientes necesidades de almacenamiento y manejo de datos.
Mi ejemplo es una tienda de ultramarinos que fue fundada por Antonio, empresario gaditano, a mediados del siglo pasado. Iremos viendo la evolución de las necesidades de manejo de datos de la empresa, desde su fundación hasta hoy en día, convertida en un próspero supermercado con varias tiendas en toda España.
SuperGades
Pongamos que la tienda se llama SuperGades. En sus primeros años de vida, Antonio maneja muy poquitos datos, únicamente un cuaderno con datos de sus proveedores y otro con los datos de venta, todo ello, por supuesto, en papel. En seguida crecen las necesidades de manejo de datos para Antonio, quiere incluir información de Clientes, y quiere poder ordenar toda la información para luego poder encontrarla cuando la necesite. Comienza a plantearse el empleo de un ordenador, la migración de los datos a un soporte digital. La primera solución disponible para Antonio será el uso de archivos digitales de acceso secuencial.
NOTA:
Este post es parte de la colección “Sistemas de acceso y almacenamiento de datos”. Puedes ver el índice de esta colección aquí.
