UNIDAD II.

ORGANIZACIONES BÁSICAS

ESTRUCTURAS DE ORGANIZACIÓN SECUENCIAL

Archivo secuencial es la forma más simple de almacenar y recuperar registros de un archivo.

En un archivo secuencial, se almacenan los registros uno tras otro. El primer registro
almacenado se coloca al principio del archivo. El segundo se almacena inmediatamente
después (no existen posiciones sin uso), el tercero después del segundo, etc. Este orden
nunca cambia en la organización secuencial.

Rudimentos de los archivos Secuenciales; dependiendo del dispositivo de almacenamiento

utilizado el archivo se puede mostrar el usuario como si fuera un sistema secuencial.
Al finalizar un archivo secuencial se denota con una marca de fin de archivo. (End-of-file)
El usuario de un archivo secuencial puede ver los registros en un orden secuencial simple.
La única forma de recuperar registros es comenzar al principio y extraerlos en el orden
contemplado.

VENTAJAS

 Los archivos secuenciales proveen la mejor utilización de espacio y son rápidos cuando
los registros son accesados secuencialmente.
 Los archivos con poca volatilidad, gran actividad y tamaño variable son altamente
susceptibles de ser organizados secuencialmente.
 La ventaja más importante de la técnica de organización secuencial de archivos es la
capacidad de acceso al "siguiente" registro rápidamente: Mientras que el patrón de
acceso a un archivo secuencial se conforme al ordenamiento de registros en el archivo,
los tiempos de acceso serán muy buenos. Sin embargo, si el patrón de acceso al
programa no se conforma al patrón de ordenamiento de los registros, entonces la
eficiencia del programa puede ser terrible.
 Otra ventaja de los archivos de organización secuencial es que son muy sencillos de usar
y aplicar.

DESVENTAJAS

 El acceso a un registro es pobre, la localización de un determinado registro no se puede

hacer individualmente no de manera rápida, y el acceso aleatorio es impráctico.
 Además, en los archivos secuenciales la dirección de registro está implícita y están
vulnerables a fallas del sistema

ARCHIVOS SECUENCIALES

 El sistema más normal para crear un archivo de clientes era escribir su nombre, separar
con un retorno de carro, escribir su dirección seguida de otro retorno de carro, población
y así sucesivamente.
 Entre cliente y cliente se colocaba una marca de final de bloque que indicaba el inicio de
los datos de un nuevo cliente o bien el final del archivo de clientes.
 Cada uno de estos bloques con los datos de un cliente recibe el nombre de registro y
cada una de estas informaciones (nombre, dirección, población, etc.) recibe el nombre
de campo.
 Por tanto, un registro se compone de campos.

EJEMPLO

Juan Pérez
Calle de Matamoros, 105
Tuxtla Gutiérrez
<FIN>
Comercial Martínez
Calle Independencia, 10
Cintalapa
<FIN>
José Sánchez
Calle CalyMayor, 207
Tonala
<FIN>

CARACTERÍSTICAS

 Lectura ordenada obligatoria

Para leer un registro situado en medio del archivo debemos pasar por todos los registros
anteriores.
 No permite el retroceso (forward only)
En los archivos secuenciales se realiza la lectura sólo hacia delante. Por ejemplo: si nosotros
leemos el primer registro del cliente, el segundo, el tercero, el cuarto y después deseamos
volver al segundo, la única forma de hacerlo consiste en cerrar el archivo y volver a abrirlo,
ya que no podemos retroceder.
 Los archivos secuenciales son monousuarios
Los archivos secuenciales no permiten el acceso simultáneo (concurrencia) de varios
usuarios. Si por desventura se accediera simultáneamente en modo escritura, los resultados
son impredecibles: puede producirse corrupción de datos por escrituras entremezcladas o
desaparición inadvertida de datos. El último que escribe tiene mayores posibilidades de
mantener su información. Evitemos la concurrencia en archivos secuenciales.
 Estructura rígida de campos
Todos los registros deben aparecer en orden. Esto quiere decir que si nosotros escogemos
el orden Nombre, Dirección, Población en el primer registro, no podemos cambiarlo por
Dirección, Población, Nombre en el siguiente registro. El programa de lectura de un archivo
secuencial va a ciegas leyendo líneas y necesita saber qué significado tiene cada línea según
su orden.
 ¿Qué pasa si queremos grabar más datos de cada cliente?
Por ejemplo su teléfono o su código fiscal, o sus condiciones de pago…
La primera consecuencia es que debemos rehacer todos los programas de lectura para tener
en cuenta estos nuevos campos. Y esto puede representar mucho trabajo si tenemos que
acabarlo de un día para otro.
La segunda consecuencia es que ese archivo ya no nos serviría para imprimir etiquetas.
Tendríamos que guardar un archivo central con todos los datos y, a partir de éste, extraer
en otro archivo sólo los datos que deseamos imprimir. Tras ello ya podríamos lanzar el nuevo
listado por la impresora. Por tanto, debemos crear un nuevo proceso y complicar el que ya
teníamos.
 El modo de apertura condiciona lectura o escritura
Las lecturas y las escrituras dependen del modo en que se haya abierto un archivo
secuencial. En el momento de abrir un archivo, dependiendo del modo que hayamos
escogido, quedaremos autorizados a leer o a escribir, pero no a las dos cosas.
 Lecturas parciales pero escrituras totales
Las operaciones de lectura pueden ser parciales, pero las operaciones de escritura conllevan
obligatoriamente la escritura total de toda la secuencia completa de registros.
Dicho de otro modo: al abrir un archivo en modo escritura estamos borrando su contenido
anterior si lo hubiere.
Por esta razón algunos lenguajes de programación contienen un modo de apertura llamado
Append que escribe al final de un archivo existente en vez de reescribirlo de nuevo.
 La marca de final de archivo (EOF)
Las operaciones de lectura deben comprobar siempre que no rebasan el final del archivo
secuencial, mediante la comparación del carácter de final de archivo (EOF o End Of File).
Este carácter se coloca siempre y de modo implícito al cerrar un archivo secuencial en modo
escritura.
 Borrado de registros omitiendo contenido
El borrado de un registro puede hacerse por varios métodos, aunque el más utilizado consiste
en la escritura de todos los registros menos el que deseamos eliminar.
Otro sistema es mantener la información, pero marcarla como borrada, lo cual implica hacer
consideraciones de programación más complejas.
 la posibilidad de uso de la marca de sincronismo
Existe una posibilidad –realmente una técnica– que no se utilizaba en los primeros años del
uso de los archivos secuenciales y que tiene que ver con la marca de sincronismo entre
registros.
La marca de sincronismo es una línea con un contenido específico que es palabra reservada.
Es decir, si la marca que nosotros elegimos es <FIN>, no puede haber ningún cliente que
se llame <FIN> ni ninguna dirección ni población que sea <FIN>.
Por tanto, cuando nosotros veamos en una línea un contenido aislado como la palabra
reservada <FIN> sabremos que se acaba un registro y a continuación empieza otro con el
mismo orden.
 registros de longitud variable
Los registros de un archivo secuencial tienen una longitud variable porque también sus
campos tienen una longitud variable.
No ocupa el mismo espacio un cliente que se llame Juan Sánchez, que otro cliente que se
llame José María González de Castro y Santos de Carballar.
Esto implica que a priori no vamos a saber el tamaño de las variables que debemos usar en
memoria para almacenar estos contenidos.
Para superar este tipo de problemas apareció el archivo de acceso aleatorio, que veremos
más adelante.
 contenido legible en un procesador de textos
El contenido de un archivo secuencial es legible en un procesador de textos.
Pasó mucho tiempo antes de que aparecieran los editores de pantalla completa que
permitían mover el cursor hasta la línea que queríamos con las flechas del teclado o con
combinaciones de teclas.

CONSIDERACIONES ADICIONALES SOBRE LOS ARCHIVOS SECUENCIALES

 Los archivos secuenciales siguen siendo buenas opciones para almacenamiento de

pocos registros en los que la velocidad de acceso no sea un punto clave.
 Todos los sistemas operativos soportan operaciones de lectura y escritura sobre
archivos secuenciales.
 Todos los lenguajes de programación están dotados de funciones para acceder a
archivos secuenciales.
 Los programas encargados de las altas, bajas, modificaciones, consultas, listados y
otras operaciones que afectan exclusivamente a un archivo (por ejemplo, clientes)
reciben el nombre de mantenimientos.
 Podemos, pues, realizar mantenimientos de archivos secuenciales mediante
programas escritos en lenguajes de todo tipo: antiguos y modernos, como BASIC,
Pascal, Fortran, COBOL, C/C++, Java, Visual Basic, C#, Prolog, LISP, etc.

ARCHIVOS INDEXADOS

Los archivos indexados son básicamente archivos de acceso aleatorio a los que se añade
una utilidad para acceder al registro deseado a través de una clave.
En el caso de los archivos de acceso aleatorio, la clave es siempre el número de registro.
Los archivos indexados pueden buscar un cliente según su nombre, según su código de
identificación fiscal o según cualquier otro campo.
Para ello se construye una estructura de índice por cada campo que se desea indexar.
Esta estructura de índice se mantiene en la memoria RAM de forma ordenada, de manera
que podamos encontrar rápidamente una relación entre el apellido de un cliente y el número
de registro en el que se encuentra.
Esto es lo que permite realizar las búsquedas por clave sin necesidad de recorrer todos los
registros de la base de datos.
Tradicionalmente, la estructura de información utilizada para localizar los registros por clave
es el árbol binario o árbol de índices.
El archivo secuencial indexado mantiene las características básicas de los archivos
secuenciales: los registros están organizados en una secuencia basada en un campo. Dos
características se añaden: un índice del archivo para soportar los accesos aleatorios y un
archivo de desbordamiento (overflow).
Un archivo está organizado en forma secuencial indexada si:
 El tipo de sus registros contiene un campo clave identificador.
 Los registros están situados en un soporte direccionable por el orden de los valores
indicados por la clave.

Existe un índice con cada una de las posiciones direccionables, que almacena la dirección de
la posición y el valor de la clave; en esencia, el índice contiene la clave del ultimo registro y
la dirección de acceso al primer registro del bloque.

Un archivo en organización secuencial indexada consta de las siguientes partes:

 Área de datos o primaria: contiene los registros en forma secuencial y está
organizada en secuencia de claves sin dejar huecos intercalados.
 Área de índices: es una tabla que contiene los niveles de índice; la existencia de
varios índices enlazados se denomina nivel de indexación.
 Área de desbordamiento o excedentes: utilizada, si fuese necesario, para las
actualizaciones.

El área de índices es equivalente, en su función, al índice de un libro. En ella se refleja el

valor de la clave identificativa más alta de cada grupo de registros del archivo y la dirección
de almacenamiento del grupo.

VENTAJAS Y DESVENTAJAS

Los archivos secuenciales indexados presentan las siguientes ventajas:

 Rápido acceso
 El sistema de gestión de archivos se encarga de relacionar la posición de cada registro
con su contenido mediante la tabla de índices.
Y los siguientes inconvenientes:
 Desaprovechamiento del espacio, por quedar huecos intermedios cada vez que se
eliminan.
 Se necesita espacio adicional para el área de índices.

REPRESENTACIÓN CON ÍNDICES

La principal función de un índice dentro de una organización secuencial indexada es proveer

una capacidad de búsqueda para llegar rápidamente a las proximidades de un registro
deseado.
En la estructura secuencial indexada más simple, se usa un solo nivel de indexación. El
índice, en este caso, es un archivo secuencial simple. Cada registro del archivo índice tiene
dos campos: un campo clave, que es el mismo que el campo clave del archivo principal y un
puntero al archivo principal. Para encontrar un campo específico se busca en el índice hasta
encontrar el valor mayor de la clave que es igual o precede al valor deseado de la clave. La
búsqueda continúa en el archivo principal a partir de la posición indicada por el puntero.
 El campo clave-secundaria sobre el cual se crea un índice se llama clave inversa o clave
indexada.
Se dice que una clave inversa está parcialmente indexada si solo algunos de sus valores
claves estan incluidos en el índice valor-clave. Los valores clave que están indexados son
aquellos usados en la condiciones de búsqueda.
Un índice parcialmente indexado se llama índice disperso. Para un índice con una gran
cantidad de elementos, la búsqueda secuencial sobre el índice no es muy eficiente. Por
esto, un índice se organiza generalmente como una estructura de varios niveles como es
el caso de la estructura multinivel de índice principal para los archivos secuenciales
indexados

TIPOS DE DIRECCIÓN

 Dirección relativa: El campo señalador en el índice valor clave señala la posición del
registro dentro del archivo de datos.
 Señalador simbólico: Un señalador simbólico es un identificador de registros, pero no
una dirección de registro. Por ejemplo, un valor de clave primaria puede usarse como
señalador simbólico porque identifica de manera única a un registro del archivo.
 Dirección física: El campo señalador puede contener direcciones físicas, las cuales
pueden usarse para accesar registros directamente sin necesidad de traducir la
dirección. Sin embargo, la mayor desventaja del uso de las direcciones reales, es que
los valores del señalador dependen entonces del dispositivo. Por ejemplo, hay que
recrear un índice si los datos del archivo emigran de un disco a otro.

Cada vez que se inserta, borra o actualiza un registro, las entradas afectadas de un índice
deben ser modificadas para que así, el índice pueda proporcionar las trayectorias de datos
correctas.
Para poder estructurar esta organización (secuencial indexada) podemos utilizar uno de los
métodos más comunes que es el de construir el índice como un árbol de valores llave. Otro
método común es de construir el índice basándose en la disposición física de los datos
almacenados

ÁRBOLES DE ÍNDICES

Un árbol se compone de nodos, que son los que contienen la información

de la clave y del número de registro en donde se encuentran los datos
que nos interesan.

Dentro de un nodo tenemos:

1. El propio valor de la clave.

2. Un dato útil para referenciar en donde se encuentran los campos del registro, como por
ejemplo, un número de registro para ir a buscar los datos.
3. Un puntero hacia un nodo que contenga una clave con un valor inferior o un nulo si no
la hay, a la que llamaremos puntero L (de left o puntero a la izquierda).
4. Un puntero hacia un nodo con una clave mayor o un nulo si no la hay, a la que
llamaremos R (de right o puntero a la derecha).
5. Otros datos interesantes para conocer rápidamente el estado del árbol, como por
ejemplo la altura del nodo respecto a la base del árbol o el factor de equilibrio, que son
datos que veremos más adelante. Los árboles binarios se representan al revés, como
una coliflor boca abajo, en la que la raíz está siempre arriba.

Ejemplo de árbol en el que ordenamos números:

 A la izquierda de cada nodo colgamos un elemento más

pequeño que el propio y a la derecha colgamos un
elemento más grande.
 En todos los procesos de búsqueda mediante árboles,
se entra a buscar siempre por la raíz.

 Imaginemos que estamos buscando el número 4.

 Entramos por la raíz, que es el 5.
 ¿Es éste el que buscamos? No. ¿Es menor? Sí. Nos
vamos hacia la izquierda.
 Encontramos el 3. ¿Mayor, menor o igual que 4? Mayor.
 Nos vamos hacia la derecha y lo encontramos. Hemos
realizado 3 comparaciones hasta llegar al dato que
buscamos.

 Esto es más lógico que emplear una lista ordenada, ya que en una lista los
números se organizarían así: 1
2
En el caso de buscar el mismo número, el 4, el número de comparaciones
sería el mismo que empleando un árbol. 3
Si buscamos el número 2 en la lista, el número de comparaciones sería 1, más rápido
que con el árbol. 4
5
En cambio, si buscáramos el 7, deberíamos hacer 6 comparaciones; mucho más lento,
puesto que el árbol sólo tiene 3 niveles. En un árbol de 8 elementos, la altura máxima del
árbol es de 3 niveles. No hará falta nunca rebasar 3 comparaciones para llegar al dato que
buscamos, independientemente de si es grande o pequeño.
En una lista ordenada, el número de comparaciones crece linealmente en función de la
cantidad de elementos que almacenamos en la lista.
En cambio, con el árbol, el número de comparaciones queda mucho más contenido.
Comparemos el peor de los casos en cada sistema.

Árbol Lista ordenada

8 elementos 3 8
16 elementos 4 16
 32 elementos 5 32
64 elementos 6 64
128 elementos 7 128

ARCHIVOS DE ACCESO ALEATORIO (DIRECTOS)

Si los archivos secuenciales se emparejan en el tiempo con el hardware de los tambores de

cinta magnética, los archivos de acceso aleatorio aparecen con el disquete y el disco duro.
Los archivos de acceso aleatorio no están sujetos a la esclavitud de pasar por el inicio hasta
llegar a la porción de la información que nos interesa.
En los archivos de acceso aleatorio podemos colocarnos en una posición determinada
expresada por un número.
Por ejemplo, podemos ir directamente a la posición 100, volver atrás hasta la posición 20,
avanzar ahora hasta la 200 y así tantas veces como queramos.
Esto implica que si utilizamos una estructura delimitada en longitud, podemos calcular la
posición en la que debemos situarnos para leer un registro.

Pongamos por caso que tenemos un registro como éste codificado en ANSI (1 byte por
carácter):
 Nombre: 80 caracteres ANSI
 Dirección: 100 caracteres ANSI
 Población: 50 caracteres ANSI
Su longitud será de 230 caracteres. Esto implica que el primer registro se encontrará en la
posición 0; el segundo registro se encontrará en la posición 230; el tercero estará en la
posición 460 y así sucesivamente.

Por tanto, podemos decir que la posición será:

Pos = NumRegistro * LongitudRegistro
Si en cambio codificamos los caracteres en Unicode (UTF-16) de forma que su longitud es
de 16 bits por carácter, esto es 2 bytes, el registro quedará así:
 Nombre: 80 caracteres UTF-16.
 Dirección: 100 caracteres UTF-16.
 Población: 50 caracteres UTF-16.
Su longitud será de 460 caracteres para un solo registro, ya que cada carácter ocupa 2 bytes.

En los archivos secuenciales se guardaba el número con su formato expresado en decimal:

dígito a dígito. Por tanto, el número “10” ocupaba 2 caracteres y el número “1234567”
ocupaba 7 caracteres.
En los archivos aleatorios no se guardan los dígitos, sino el valor binario.
Un número entero simple de 16 bits (de 0 a 65535) emplea 2 bytes
Si se trata de un número entero de 32 bits (de 0 hasta 4.000 millones aproximadamente)
ocupa 4 bytes.
Si se trata de un número en coma flotante (normalmente se ajustan a la norma IEE488 como
Excel) usa 8 bytes para almacenar mantisa y exponente.
Estos datos ya no son legibles con un procesador de texto y si intentamos leerlos nos
aparecerán caracteres extraños, con posibilidad de que el contenido no aparezca entero, ya
que es frecuente encontrar un valor binario que coincida con el valor EOF (final de archivo).

CARACTERÍSTICAS

 Posicionamiento inmediato
Permiten situar el puntero de lectura o escritura sobre una posición concreta del archivo sin
necesidad de pasar por las posiciones anteriores, con el consiguiente incremento de rapidez.
Una sola apertura proporciona la capacidad de avanzar y retroceder sin necesidad de reabrir
el archivo.
 Registros de longitud fija
Todos los registros tienen la misma longitud, ya que se utiliza siempre una estructura rígida
dimensionada a la máxima longitud para cada campo.
 Apertura para lectura/escritura
Permiten su apertura en modo mixto (lectura y escritura), de forma que con una sola
operación de apertura podemos leer o escribir a voluntad en cualquier posición según nos
convenga.
 Permiten el uso concurrente (multiusuario)
Al establecerse zonas específicas y limitadas de actuación para lectura y escritura, diversos
usuarios pueden acceder y escribir en diferentes porciones del archivo de forma simultánea.
Esto lleva a considerar la posibilidad de concurrencia de dos usuarios en el mismo registro.
Para ello se utilizan algoritmos de gestión de los bloqueos. Dichos algoritmos administran
zonas (que no siempre coinciden con registros) y las marcan para evitar dicha concurrencia
de forma temporal.
 Dimensionamiento máximo al ser creados
Los archivos de acceso aleatorio deben dimensionarse hasta un número de registros máximo
en el momento de crearse.
 Borrado de registro mediante ceros
El borrado de un registro se realiza poniendo a 0 el espacio que ocupa; rellenándolo con
bytes con el valor binario 0. En sistemas más complejos se emplea un algoritmo de
reutilización de gaps o espacios vacíos, o incluso de compactación.
Si empleamos un algoritmo de compactación de registros de gaps, deberemos ser
conscientes de que el número de registro cambiará para un cliente dado en el momento en
que se reubica, por lo cual una clave de acceso basada en número de registro no tendrá
validez.
Si utilizamos un algoritmo de reutilización de gaps deberemos ser conscientes de que un
cliente nuevo puede reutilizar el espacio de un cliente borrado. Por tanto, si utilizamos
referencias a su número de registro en otros archivos, deberemos ser cuidadosos de que un
cliente no sea falsamente referenciado en otros archivos.

CONSIDERACIONES ADICIONALES SOBRE LOS ARCHIVOS DE ACCESO ALEATORIO

Los archivos de acceso aleatorio están especialmente indicados para aquellos casos en que
el código del registro (cliente, proveedor, etc.) pueda ser directamente el número de registro
en el que se guardan los datos.
Al trabajar con archivos de acceso aleatorio deberemos tener en cuenta no rebasar nunca
el final de archivo. Si nuestro archivo está dimensionado hasta 100 registros, intentar que
no haya ningún usuario que nos pregunte por el 101 o por el 200. Para ello deberemos
establecer nuestros sistemas de prevención desde el interfaz o desde el sistema de cálculo
de la posición del puntero de lectura / escritura.

FUNCIONES HASHING

El origen de los algoritmos de hash es la ambición de los científicos por encontrar una forma
más rápida de encontrar la información
Una función de hash es una función para sumarizar o identificar probabilísticamente un gran
conjunto de información (dominio), dando como resultado un conjunto imagen finito
generalmente menor (un subconjunto de los números naturales por ejemplo). Varían en los
conjunto de partida y de llegada y en cómo afectan a la salida similaridades o patrones de
la entrada. Una propiedad fundamental del hashinges que si dos resultados de una misma
función son diferentes, entonces las dos entradas que generaron dichos resultados también
lo son.
Son usadas en múltiples aplicaciones, como los arrays asociativos, criptografía ,
procesamiento de datos y firmas digitales entre otros. Una buena función de hash es una
que experimenta pocas colisiones en el conjunto esperado de entrada; es decir que se
podrá identificar unívocamente las entradas

UN ALGORITMO DE HASH

No existe una fórmula “única” para hash, pero el producirla es un algoritmo que básicamente
se presenta en 3 pasos:
1) Representar la llave de manera numérica (siempre que no sea de por sí un número) Una
buena opción es usar los valores ASCII o bien los Unicode de las letras
LOWELL= L O W E L L _ _ _ _ _ _
76 79 87 69 76 76 32 32 32 32 32 32
2) Plegar y Agregar Combinar algunos de estos números para generar pequeños trozos con
los que podamos trabajar 76 79 | 87 69 | 76 76 | 32 32 | 32 32 | 32 32 De manera que
podemos hacer algunas operaciones matemáticas con dichos números para finalmente
obtener un número del cual obtendremos la dirección 7679 + 8769 + 7676 + 3232 + 3232
= 30 588

TÉCNICAS HASHING

Son similares a las de direccionamiento por clave en

que la fórmula es aplicada a un campo del registro
(usualmente la clave primaria) teniendo como
resultado un valor usado como la dirección en disco
para almacenar ese registro. La diferencia es que las
técnicas hashing no garantizan una dirección de
almacenamiento única. La fórmula puede producir dos o más registros con el mismo valor
resultante
Esta técnica permite utilizar el disco eficientemente mientras
intenta retener la rapidez del acceso aleatorio (no más de un
acceso a disco para obtener un registro específico) si se
pueden minimizar los efectos de los resultados duplicados de
la fórmula.

La función hashing es seleccionada de manera tal que los

registros sean esparcidos lo más uniformemente posible a lo
largo de todo el archivo, pero no quedan almacenados en una
secuencia en particular.
Cuando para dos o más registros se obtiene como resultado el mismo valor de la función
hashing se dice que se produce una colisión y los dos registros son llamados sinónimos.

Dentro de las técnicas hashing más usadas se tienen:

• Técnica Hashing plegable (folding).
• Técnica Hashing división-cociente

Técnica hashing plegable (folding)

Consiste en tomar el valor de la clave

primaria, dividir sus dígitos en dos o más
grupos y sumar estos grupos de dígitos. El
resultado de la suma es usado como la
dirección en disco. La idea es tomar un valor
de clave primaria que puede ser grande (C.I.,
por ejemplo) y transformarlo en números
pequeños que son direcciones en disco
minimizando el número de colisiones a obtener.

Técnica hashing división-cociente

Consiste en dividir el valor de la clave primaria

entre un número fijo, preseleccionado y el
cociente de la división se usa como dirección
en disco. Las investigaciones demuestran que
el número seleccionado para hacer la división
debe ser un número primo para disminuir el
número de colisiones posibles.
Manejo de colisiones: No importa lo bien seleccionado que esté nuestra función hashing,
siempre habrá que enfrentar el problema de las colisiones y se debe buscar la mejor forma
de manejarlo. Se sabe que el SMBD almacena registros en páginas que tienen capacidad
para varios registros y que cada página tiene un número único o dirección. Mas que usar un
número relativo para almacenar y recuperar registros, la técnica hashing usa el número de
página para localizar los registros.
Entre las formas de manejar las colisiones se tienen:
• Búsqueda lineal
• Áreas de overflow.

BÚSQUEDA LINEAL

Si la página en donde se debe almacenar un registro nuevo, según la función hashing, no

tiene espacio disponible, este se almacena en la próxima página que tenga espacio
disponible. La ventaja de este método es que los registros que tengan la misma página
estarán almacenados en la misma página o en páginas cercanas pero si existen muchos
registros que deben estar en una misma página y no caben allí se necesitarán varios accesos
a disco para obtenerlos y el problema puede empeorarse para archivos de gran tamaño con
altas densidades de ocupación

ÁREAS DE OVERFLOW

Este método usa un área de overflow separada para almacenar los registros que no pueden
ser almacenados en la página especificada por la función hashing. Al momento de ubicar un
registro que está en al área de overflow, el sistema obtiene primero la página en donde
debería estar almacenado. Al no ser encontrado allí se comienza a obtener las páginas del
área de overflow hasta que el registro es encontrado.
El método de búsqueda lineal tiende a causar colisiones a futuros registros que tengan que
ser ubicados en la página en la que ubico el registro sinónimo y si se mantienen el número
de colisiones al mínimo, es más rápido buscar en una área de overflow pequeña que buscar
en el área primaria.
La eficiencia de ambos métodos puede ser mejorada a través del uso de una cadena de
apuntadores (cadena de sinónimos o colisiones). Para esto cada página tiene un campo,
llamado apuntador, que sirve como indicador de que una colisión ha ocurrido en esa página.
En este campo se almacena el número de página en donde se encuentra almacenado el
sinónimo. De este forma no es necesario hacer una búsqueda secuencial en el área primaria
para el método de búsqueda lineal o no es necesario buscar en todas las páginas del área
de overflow para el método de áreas de overflow.