El hashing es específico del software utilizado, los siguientes ejercicios corregidos exploran las técnicas más utilizadas.
Introducción al hash
Los artículos de un archivo aleatorio (también hablamos de archivo hash) se distribuyen en paquetes compuesto por una o más páginas de disco. Una función hash h asocia con un valor clave (discriminatorio o no) un número entero que representa un número de paquete. Todos los elementos cuyo valor clave es tal que la función h asocia el mismo número de paquete se almacenan juntos en este paquete.
Cuando se busca una clave de acceso, la función h determina de forma única el paquete que contiene todos los artículos que cumplen el criterio de búsqueda. Esta función h rara vez es inyectiva. Sean c1 y c2 dos claves diferentes, llamamos colisión al hecho de que h(c1) = h(c2).
Este fenómeno de colisión exige, por una parte, verificar que cada artículo accedido cumple el criterio de búsqueda y, por otra parte, dificulta la equidistribución de los artículos en los diferentes paquetes, complicando la gestión de la memoria secundaria. Además, la función h rara vez conserva el orden de las teclas (c1 h(c1)
La primera sección de esta parte está dedicada al estudio de organizaciones de hash estáticas en el que el número de paquetes hash se fija estáticamente en el momento de la creación del archivo. La distribución desigual de los artículos en los diferentes paquetes puede provocar que ciertos paquetes saturados se desborden, degradando significativamente el rendimiento de las operaciones de búsqueda e inserción de artículos en el archivo.
La segunda sección de este tema presenta la organizaciones por hash dinámico evitando este problema a costa de una mayor complejidad mecanismos implementados.
Ejercicio de hash estático
Un archivo organizado mediante hash estático se descompone en N paquetes de tamaño fijo cuando se crea. La función hash asociada determina para cada valor de clave de acceso un número de paquete entre 0 y N-1. La elección de la función hash es esencial para garantizar una distribución equidistante de los artículos en los N paquetes.
Esta elección debe guiarse por la distribución raramente uniforme de claves en el archivo. El número de colisiones (c1 diff c2 y h(c1) = h(c2)) es mayor ya que el número de paquetes hash es pequeño en comparación con el número de artículos que se insertarán en el archivo. Las colisiones provocarán que ciertos paquetes hash se desborden y estos paquetes se desborden.
Pregunta 1
¿Cuáles son los criterios para elegir el tamaño de un paquete de hash? Proponer un formato para almacenar artículos en un paquete hash.
Pregunta 2
Proponer diferentes formas de funciones hash que produzcan números aleatorios entre 0 y N-1 a partir de una clave de acceso.
Pregunta 3
Primero suponemos que los paquetes saturados se desbordan hacia los paquetes que aún no están saturados. Sugiera diferentes técnicas para almacenar y luego encontrar elementos sobrantes. ¿Son estas técnicas adecuadas en caso de numerosas colisiones?
Pregunta 4
Ahora consideramos que el archivo incluye una zona de desbordamiento independiente cuyo tamaño se fija cuando se crea el archivo. Los N paquetes hash iniciales se llaman zona primaria para distinguirlos de los zona de desbordamiento.
Proponer nuevas técnicas de desbordamiento que aprovechen esta división en dos zonas independientes. ¿Cuál es la aportación de estas técnicas respecto a las introducidas en la pregunta anterior? ¿Estas técnicas resuelven completamente satisfactoriamente el problema de las colisiones? Concluir sobre las ventajas y desventajas de las organizaciones estáticas.
Pregunta 1
El tamaño de un paquete hash debe ser lo más grande posible para limitar los desbordamientos en caso de colisión. Por otro lado, un paquete debe poder leerse en una única E/S. Por lo tanto, el tamaño de un paquete hash está limitado por el tamaño de una página de disco (considerada como la unidad de E/S). La información de desbordamiento depende de la estrategia utilizada (bit indicador de desbordamiento o número del primer paquete de desbordamiento (ver Pregunta 3).
Pregunta 2
Son posibles muchas funciones hash para determinar un número de paquete entre 0 y N-1 a partir de un valor clave. Los más comunes son:
- División entera: Esta es la función más simple y más utilizada. El resultado de esta función, comúnmente llamada módulo, es el resto de la división entera de la clave por el número de paquetes hash N. Se recomienda garantizar que N sea un número primo para limitar el riesgo de colisiones. Por ejemplo, un archivo dividido en 11 paquetes, el elemento clave 35 se colocará en el paquete número 2 (2 = 35 módulo 11). Si la clave de acceso no es numérica, la función módulo se aplica a la representación binaria de esta clave, considerada como un número entero.
– Extracción de la plaza: Primero se eleva al cuadrado la clave y luego se extrae un conjunto de bits (normalmente los bits bajos o medios) del número resultante para formar un número de paquete. Dado que k bits permiten direccionar 2k paquetes, extraeremos log_2 N bits para formar un número de paquete entre 0 y N-1.
– Plegado generalizado: Si consideramos que un número de paquete se expresa en p bits (con p = log2N), dividimos la clave en porciones de p bits y aplicamos una operación binaria “exclusiva o” entre todas estas porciones para obtener una nueva cadena de p bits que identifican un paquete. Se prefiere la operación "o exclusiva" a la operación "y" que favorece la aparición de muchos ceros en la cadena de bits resultante y a la operación "o" que favorece la aparición de muchos unos.
Pregunta 3
Si el paquete designado por la función hash está saturado, debemos almacenar el artículo de inserción en uno de los paquetes N-1 restantes y poder encontrarlo más tarde. Son posibles varias técnicas de desbordamiento:
– Direccionamiento abierto: Supongamos que el paquete saturado es el paquete i, esta técnica consiste en buscar secuencialmente un lugar libre para el artículo que se está insertando en los paquetes i+1, i+2,…, i+k, hasta encontrar una ubicación de tamaño suficiente. Almacenamos en el paquete i el número del primer paquete en el que se desbordó para acelerar las búsquedas posteriores de elementos desbordados. La búsqueda de todos los artículos pertenecientes al paquete i se realiza de la siguiente manera.
Los artículos almacenados en el paquete i se leen primero secuencialmente comprobando para cada uno de ellos que realmente pertenece al paquete i (una comparación de claves permite eliminar artículos de otros paquetes posiblemente almacenados desbordados en el paquete i). Los elementos del paquete i almacenados en desbordamiento se buscan luego secuencialmente en paquetes posteriores comenzando desde el primer paquete de desbordamiento.
– Encadenamiento de desbordamiento: Esta técnica es idéntica al direccionamiento abierto, pero aquí todos los artículos que pertenecen al mismo paquete se encadenan entre sí. Este encadenamiento evita el coste de una búsqueda secuencial para encontrar todos los artículos de un mismo paquete almacenados en desbordamiento. Por otra parte, además del coste adicional de almacenamiento vinculado al encadenamiento, esta técnica puede generar numerosas E/S si la cadena de artículos es larga y si el encadenamiento pasa frecuentemente de un paquete a otro (es posible que entonces tengamos que leer el mismo paquete varias veces). En el peor de los casos, el recorrido del encadenamiento puede generar una E/S para recuperar cada elemento (consulte el Capítulo 2, pregunta 4).
– Tabla de direcciones de elementos desbordados: Esta técnica, muy similar a la técnica de encadenamiento de desbordamiento, almacena las direcciones de todos los elementos desbordados en una tabla asociada con cada paquete. Las direcciones almacenadas en esta tabla se pueden mantener ordenadas para evitar lecturas múltiples del mismo paquete. Esta técnica, sin embargo, plantea el problema del espacio ocupado y del tamaño estático de cada una de estas mesas.
– Repetir: si el paquete i se desborda, almacenamos en el paquete el hecho de que se ha desbordado y aplicamos una nueva función hash a los artículos que se insertarán en este paquete. Esta segunda función genera un número de paquete diferente de i y entre 0 y N-1. La búsqueda de todos los artículos pertenecientes al paquete i se realiza de la siguiente manera.
Los artículos almacenados en el paquete i se leen primero de forma secuencial, comprobando para cada uno de ellos que realmente pertenece al paquete i (para eliminar artículos de otros paquetes posiblemente almacenados desbordados en el paquete i). Los artículos del paquete i almacenados en desbordamiento se buscan luego en el paquete identificado por la segunda función hash aplicada a la clave de acceso.
Estas técnicas ofrecen una respuesta al problema de la gestión de artículos desbordados pero ninguna es realmente satisfactoria si la tasa de colisiones es alta. El rendimiento se degrada muy rápidamente cuando se buscan artículos desbordados. Este fenómeno se debe al hecho de que se almacenan los artículos desbordados de un paquete i en lugar de los artículos de un paquete j, provocando rápidamente un desbordamiento del paquete j por una reacción en cadena.
Pregunta 4
Las técnicas de desbordamiento presentadas en la pregunta 3 siguen siendo aplicables, con algunas modificaciones, a un archivo con una zona de desbordamiento independiente. En el caso deldireccionamiento abierto, la primera ubicación libre que permite almacenar un elemento desbordado ya no se busca en los siguientes paquetes hash primarios sino secuencialmente en la zona de desbordamiento. Las técnicas de encadenamiento de desbordamiento y tabla de direcciones de artículos desbordados permanecen sin cambios, pero los eslabones de encadenamiento corresponden a direcciones en la zona de desbordamiento.
Finalmente, la técnica de refrito requiere dividir la zona de desbordamiento en paquetes hash P. Por lo tanto, al insertar un artículo en el archivo, primero aplicamos una división entera por N a su clave para determinar un número de paquete principal. Si este paquete primario está saturado, se aplica una división entera por P a esta misma clave para determinar un número de paquete secundario. Si este paquete secundario a su vez está saturado, entonces utilizamos una de las técnicas presentadas en la pregunta 3 en la zona de desbordamiento.
La ventaja de separar la zona primaria de la zona de desbordamiento es evitar el fenómeno de reacción en cadena por saturación de ciertos paquetes generado por el desbordamiento de otros paquetes (ver pregunta 3). Aquí, el desbordamiento de un paquete primario no influye en la tasa de ocupación de otros paquetes primarios. Esta gestión de los desbordamientos es, por tanto, más sólida ante un elevado índice de colisiones. Sin embargo, la búsqueda de artículos en áreas desbordadas sigue siendo una operación costosa.
Conclusión: la principal ventaja de las organizaciones aleatorias estáticas es su simplicidad de implementación y el excelente rendimiento que ofrecen siempre que los desbordamientos de paquetes sean pocos. De hecho, si ningún paquete se ha desbordado, las organizaciones aleatorias estáticas garantizan la búsqueda de todos los elementos con un valor clave determinado en una única E/S. Por otro lado, los desbordamientos causan rápidamente un colapso en el rendimiento independientemente de la técnica de gestión de desbordamiento utilizada. Este problema requiere una reorganización periódica de los archivos tan pronto como la tasa de desbordamiento excede un umbral de tolerancia determinado.
Ejercicio de hash dinámico
El objetivo de las organizaciones de hash dinámico es minimizar el costo de las colisiones reemplazando las técnicas de desbordamiento con un aumento dinámico en el tamaño del archivo. En la literatura se han propuesto muchas estrategias de hash dinámico: hash extensible [Fagin79], hash lineal [Litwin80] y trie-hashing [Litwin81], por nombrar sólo las más conocidas.
Cada una de estas estrategias constituye una adaptación de un principio común: la explotación progresiva del contenido de la clave de acceso. Suponga una clave de acceso cuyo hash produce una cadena de k bits. El hash de dicha clave permite direccionar como máximo 2^k paquetes. El archivo hash se crea inicialmente con N paquetes (N < 2^k) y los artículos se distribuyen en estos paquetes utilizando solo los primeros p bits resultantes del hash de su clave (N=2^p y p < k).
En caso de saturación, un paquete se divide y los artículos que contiene se dividen en dos paquetes aprovechando el valor del (p + 1)ésimo bit resultante del hash de su clave. Los métodos de hash dinámico difieren según la estrategia utilizada para elegir el paquete a explotar en cada saturación.
Pregunta 5
En el método de hash extensible [Fagin79], un paquete se divide en dos tan pronto como se satura. Podemos representar el estado de un archivo en un momento t mediante un árbol estallidos cuyos nodos corresponden a los paquetes y cuyos arcos materializan los sucesivos estallidos de paquetes. La raíz de este árbol tiene hijos 2p que representan los paquetes 2p iniciales.
Cada nodo correspondiente a un paquete de ráfaga es a su vez padre de dos hijos que representan los dos paquetes resultantes de la ráfaga. Por tanto, las hojas del árbol corresponden a los paquetes realmente ocupados por el fichero en el momento t, mientras que los nodos internos corresponden a los paquetes que existieron en los momentos t-1, ..., tn. Cada arco del árbol que estalla es valorado por el firma del paquete al que hace referencia.
Llamamos firma de un paquete al valor de la cadena de bits compartida por las claves de todos los elementos almacenados en este paquete. Así, los arcos que parten de la raíz se valoran mediante firmas de p bits que tienen el valor respectivo: 0…00, 0…01, hasta 1…11. Por inducción, los arcos correspondientes al nivel n del árbol se valoran mediante firmas de p+n-1 bits.
Consideramos un archivo hash con 8 paquetes iniciales numerados del 0 al 7. El paquete número 6 se ha dividido en dos paquetes secundarios, el secundario izquierdo se ha dividido a su vez. Representa el árbol de división de este archivo especificando las valoraciones de los arcos y los paquetes ocupados por el archivo.
Pregunta 6
El árbol de ráfagas debe almacenarse (de alguna forma) en una estructura de datos del sistema llamada catalogar. La función del catálogo es determinar rápidamente la dirección del paquete en el que se debe insertar un nuevo artículo, así como la dirección del paquete que se debe leer durante una búsqueda clave.
Proponer una organización del catálogo en forma de tabla. Ilustre esta organización del catálogo en relación con el árbol de explosión anterior.
Suponiendo que la función hash utilizada es módulo, indique el principio de búsqueda en el catálogo que le permitirá encontrar en el archivo todos los artículos cuyo valor clave sea 54 y luego todos aquellos cuyo valor clave sea 65.
Pregunta 7
Cuando el archivo es muy grande, es posible que el catálogo ya no quepa en la memoria. Proponer una adaptación de la estructura anterior que permita siempre encontrar la dirección de un paquete (durante una inserción o una búsqueda) en una E/S.
Indique el principio de actualización del catálogo cuando se dividen los paquetes. Indique las diferentes versiones del catálogo, cuando se crea el archivo y luego después de cada una de las dos divisiones consideradas en la pregunta 5. ¿Cuántas entradas hacen referencia al paquete 000 y cuál es su firma respectiva?
¿Cómo encontramos ahora los artículos clave 54 y 65?
Pregunta 8
¿Un archivo organizado mediante el método hash dinámico tiene un límite de tamaño? En caso afirmativo, especifique cuál; en caso contrario, especifique por qué.
Pregunta 9
El método de hash lineal [Litwin80] es un método de hash dinámico que evita la gestión de un catálogo. En lugar de dividir un paquete al saturarse como en el hashing extensible, los paquetes se dividen en un orden predefinido (de ahí el nombre lineal). El archivo se compone de N paquetes iniciales, numerados del 0 al N–1. Los elementos se colocan en los paquetes iniciales mediante la aplicación de la función hash h0(clave) = clave módulo N. Cuando un primer paquete se desborda (por ejemplo: paquete i), un paquete vacío de número N se agrega dinámicamente al final del El archivo y el paquete 0 (y no el paquete i) se dividen en dos mediante la aplicación de la función h1(clave) = clave módulo 2N.
Si la distribución es uniforme, la mitad de los elementos del paquete 0 se moverán al paquete N y los demás elementos permanecerán en el paquete 0. El elemento que provocó el desbordamiento del paquete i se encadena al desbordamiento utilizando una técnica clásica (por ejemplo: abrir direccionamiento). Cuando otro paquete j se desborda, se agrega un nuevo paquete con el número N+1 al final del archivo y el paquete 1 se explota con la función h1. Al proceder de esta manera linealmente, los paquetes i y j tarde o temprano se dividirán a su vez. La función h1 se puede utilizar hasta que el archivo haya duplicado su tamaño (luego se han dividido todos los paquetes del 0 al N-1).
Cada vez que el tamaño del archivo se duplica, las ráfagas comienzan nuevamente desde el paquete 0 y la función hash hk-1 se reemplaza por la función hk(key) = módulo de clave (2^k N), donde k representa el número de veces que el archivo tiene duplicado en tamaño (k se llama nivel de archivo).
En un momento t, dos funciones hash son suficientes para gestionar el hash lineal. ¿Cuál es la regla para determinar qué función hash usar al buscar o insertar un elemento en el archivo? ¿Qué información del sistema debe mantenerse para permitir la implementación de esta regla?
Pregunta 10
Dé el algoritmo correspondiente a la regla establecida en la pregunta anterior.
Pregunta 5
El árbol de explosión correspondiente al archivo descrito se muestra en la Figura 5.2. Los paquetes atenuados corresponden a los paquetes ocupados por el archivo en el momento t. Se puede observar que la cadena de bits de firma se expande de derecha a izquierda. Esto permite priorizar los bits de menor orden (cuya distribución es generalmente más aleatoria) de las claves hash.
Cifra. Ruptura de árboles valorada por firmas de paquetes
Pregunta 6
El catálogo se materializa mediante una tabla que garantiza la correspondencia entre la firma y la dirección del paquete. Esta tabla contiene una entrada para cada paquete ocupado por el archivo en un momento t, como se ilustra en la Figura 5.3.
Cifra. Catálogo correspondiente al árbol de ráfagas de la pregunta 6
Para buscar todos los artículos con una clave determinada, basta con buscar en el catálogo la entrada cuya firma corresponde a un prefijo de la cadena de bits resultante del hash de la clave buscada. Por ejemplo, la búsqueda de artículos con una clave de 54 se realiza de la siguiente manera. Actualmente se utilizan como máximo cinco bits en las firmas de paquetes; aplicamos la función hash de módulo 25 en la clave 54. El resultado del hash es, por tanto, 22 (54 mod 32).
En binario, 22 se escribe 10110. Por tanto, buscamos la firma 10110 en el catálogo para encontrar la dirección del paquete correspondiente. Lo mismo ocurre con la búsqueda de artículos clave 65. 65 módulo 25 da 1, o en binario de 5 bits 00001. Se seleccionará la entrada 001 en el catálogo porque es la única entrada correspondiente a un prefijo de 00001.
Pregunta 7
La estructura propuesta en la pregunta 7 requiere una lectura secuencial del catálogo. Para superar este inconveniente, modificamos el principio de actualización del catálogo. Mientras no haya habido una ráfaga de paquetes, el catálogo contiene firmas de bits p que abordan los paquetes 2p iniciales. Cuando uno de estos paquetes se ráfaga por primera vez, el tamaño del catálogo se duplica y se expande un bit adicional de cada firma para que todas las entradas del catálogo contengan firmas de p+1 bits.
Los dos paquetes resultantes de la división están referenciados cada uno por una firma distinta de p+1 bits. Una nueva división de uno de estos dos paquetes resultará nuevamente en una duplicación del catálogo. Por el contrario, los paquetes que no se han estallado están referenciados por dos firmas de p+1 bits cuyos primeros p bits son idénticos. Si uno de estos paquetes explota a su vez, duplicar el catálogo no es útil ya que ya tenemos dos firmas de p+1 bits para direccionar los dos paquetes resultantes de la explosión.
En este caso, sólo se debe actualizar la dirección del paquete asociada a las dos firmas. La Figura 5.4 muestra la evolución del catálogo después de la explosión del paquete 110 y luego del paquete 0110. En esta figura, tener representa la dirección del paquete I.
La ventaja de este principio es doble. Por un lado, dado que la duplicación del catálogo es rara, dividir un paquete suele requerir una simple actualización de las direcciones asociadas con las firmas. Por otro lado, todas las firmas tienen el mismo número de bits desarrollados. Así, si el catálogo es grande y ocupa varias páginas, es posible determinar mediante cálculo en qué página se encuentran las firmas deseadas. Por lo tanto, sólo se necesita una E/S para buscar en el catálogo, independientemente de su tamaño.
Cifra. Etapas de evolución del catálogo
El paquete inicial 000 ahora está referenciado por cuatro entradas que contienen la misma dirección física pero cuyas firmas respectivas son: 00000, 01000, 10000, 11000. Observamos que estas cuatro firmas tienen el mismo perfil xx000.
La búsqueda de artículos clave 54 se lleva a cabo como en la pregunta 7, es decir, seleccionamos la entrada de catálogo de firma 10110. La búsqueda de artículos clave 65 equivale a seleccionar la entrada de firma 00001 que, en el presente caso, hace referencia al mismo paquete que el entradas de firma: 01001, 10001 y 11001. En efecto, al no haber estallado el paquete inicial 001, todas las entradas cuyo perfil de firma es 001 hacen referencia a él.
Nota: La entrada del catálogo que contiene la firma 10110 es la entrada 22 (10110 en binario). Por tanto, no resulta útil almacenar firmas en este tipo de catálogo porque esta información es redundante con el número de cada entrada.
Pregunta 8
Cuando la firma de un paquete alcanza el número total de bits de la cadena de bits resultante del hash de la clave, este paquete ya no se puede dividir porque se han utilizado todos los bits de las claves de los artículos que contiene. En este caso el archivo está lleno. Sin embargo, es posible encadenar un paquete desbordado a cada paquete saturado para permitir su extensión. En este caso, el archivo ya no tiene un límite de tamaño teórico.
Pregunta 9
Para determinar el número del paquete en el que se debe buscar o insertar un artículo, es necesario conocer el nivel k del fichero y saber si el paquete en cuestión ya ha sido dividido o no, para poder determinar si debemos usar la función hash hk o hk+1. Para hacer esto, almacenamos en el descriptor de archivo: el número de veces que el archivo ha duplicado su tamaño (nivel k del archivo) y la posición del puntero de ráfaga actual que hace referencia al siguiente paquete a ráfaga.
Conociendo el nivel k del archivo, aplicamos la función hash hk a la clave del artículo a buscar o insertar. Si el número de paquete determinado por esta función hash es menor que el puntero de ráfaga actual, entonces el paquete correspondiente ya se ha dividido y volvemos a realizar un hash de la clave del artículo con la función hk+1. De lo contrario, el paquete designado por la función hk puede explotarse directamente.
Pregunta 10
El algoritmo que determina qué función hash utilizar, al buscar o insertar un elemento en el archivo, toma como entrada el descriptor del archivo, la clave del elemento y genera el número de paquete en el que se debe buscar o insertar este artículo. La función hash utilizada en este algoritmo es h (k, clave) = módulo de clave (2k N), donde el parámetro k corresponde al nivel de archivo.
función número_paquete_cálculo (descripción_archivo: descriptor, clave:tipo_clave): entero;
var paquete numérico, k: int;
inicio
k := archivo_descripción.k; // nivel de archivo
número de paquete := h (k, clave);
si (número de paquete < file_descrip.ptflare) entonces Paquete_de_cálculo# := h (k+1, clave);
de lo contrario Cálculo_paquete# := paquete#;
fin
A continuación se muestra el algoritmo para insertar un nuevo artículo en un archivo organizado mediante el método hash lineal. La función Calculation_packet# utilizada en este algoritmo es la presentada en la pregunta 10. La función Write(article, package#) escribe el artículo “artículo” en el paquete#paquete o en la cadena de desbordamiento si este paquete está saturado.
procedimiento Insertar(descripción_archivo: descriptor, clave: tipo_clave, artículo: tipo_artículo)
var
paquete numérico, nvnumpacket: int;
k: entero; // nivel de archivo
ráfaga: int; // puntero de ráfaga actual
inicio
k := archivo_descripción.k;
ptflare := descrip_file.ptflare; número_paquete := Número_paquete_cálculo (descripción_archivo, clave);
si (el paquete numérico está lleno) entonces
// estampamos el paquete de números ptburst en el
// empaqueta ptespace y (ptespace + 2k N)
para cada artículoi Î ptsparkle hacer
nvnumpacket := h (k+1, elemento.clave);
Escribir (artículo, nvnumpacket);
para
si (numpaquete = ptshard) entonces
// determina si se debe insertar el nuevo artículo
// en el paquete ptespace o (ptespace + 2k N)
número de paquete := h (k+1, elemento.clave);
fsi
// incrementa el puntero de ráfaga actual
si (ráfaga de puntos = (2k N) – 1)
entonces // actualización a nivel de archivo
k := k + 1;
explosión := 0;
de lo contrario fragmento de pt:= fragmento de pt + 1;
// descriptor de archivo actualizado
descrip_file.k := k;
descrip_file.ptshard := ptshard;
fsi
fsi
// escribe el artículo en el paquete numpaquet
Escribir (artículo, paquete numérico);
FIN
Ejercicio de hash multicriterio
En el ámbito de las bases de datos, las búsquedas de artículos se realizan generalmente según múltiples criterios (ejemplo: búsqueda de coches con potencia superior a 10 CV y marca Citroën). Las organizaciones de archivos estudiadas en los Capítulos 2 y 3 favorecen el procesamiento del criterio de búsqueda más utilizado en un archivo, ordenando los artículos en disco según este criterio. Para procesar eficientemente búsquedas multicriterio, es posible adaptar la mayoría de las organizaciones de archivos para involucrar varios atributos en la política de ubicación.
Una segunda solución consiste en utilizar una estructura de datos adicional, llamada índice secundario. Un índice secundario constituye una reordenación lógica de los artículos de un fichero según una clave de acceso (discriminatoria o no) distinta de la clave de colocación en la que se basa la organización del fichero. Cuando se realiza una búsqueda utilizando una clave de acceso, el escaneo del índice secundario proporciona los identificadores de todos los artículos que satisfacen el criterio de búsqueda.
Luego, estos artículos se recuperan uno por uno a través de sus identificadores, a razón de una E/S por artículo. La creación de un índice secundario introduce un costo de almacenamiento significativo. Además, cualquier actualización del archivo de datos hace que se actualicen todos los índices secundarios relacionados con este archivo. Por tanto, el uso de índices secundarios debe limitarse a criterios de búsqueda frecuentes.
Pregunta 1
En el método de hash estático estudiado anteriormente, un número de paquete está determinado por el valor de una cadena de bits resultante del hash del valor de un único atributo. Para extender este método al hash multiatributo, la cadena de bits se obtiene concatenando respectivamente b1, b2,… bn bits resultantes del hash de los atributos A1, A2,…, An mediante las funciones hash h1, h2,…, hn. .
a) Dé el principio de buscar todos los artículos del archivo que cumplan la condición Ai = .
b) Calcule la cantidad de E/S necesarias (cantidad de paquetes a los que se accede) para realizar la búsqueda anterior suponiendo que no haya desbordamiento.
c) Una búsqueda con la condición (Ai = y Aj= ) genera más o menos E/S que la búsqueda anterior? Misma pregunta con la condición (Ai = o Aj= ).
Pregunta 2
Se han propuesto muchos métodos de hash dinámico de atributos múltiples, incluidos: archivo de cuadrícula [Nivergelt81], hash lineal de atributos múltiples [Ouksel83] y árboles de predicados [Gardarin84]. Al igual que el hash estático de atributos múltiples, la cadena de bits utilizada para determinar un número de paquete se compone de los bits resultantes del hash de los atributos A1, A2,…, An mediante las funciones hash h1, h2,…, hn.
Sin embargo, los métodos de hash dinámico de atributos múltiples difieren según el orden de los bits provenientes de cada función hash hi(Ai) en esta cadena de bits (por ejemplo, los bits asociados con un atributo Ai no son necesariamente contiguos en la cadena). Al igual que en el hashing dinámico de un solo atributo, esta cadena de bits se expande poco a poco a medida que los paquetes se expanden.
Dé el principio de búsqueda de artículos que cumplan la condición Ai = .
Pregunta 3
Supongamos un archivo con hash dinámico en los atributos A1, A2 y A3. ¿En qué orden deben disponerse los bits resultantes de las funciones hash h1(A1), h2(A2) y h3(A3) en la cadena de bits que determina un número de paquete para favorecer el acceso al atributo A2, luego al atributo A3 y luego al atributo A3? ¿Finalmente atribuye A1 en este orden de prioridad?
Pregunta 4
El método del archivo de cuadrícula permite que cada uno de los atributos de ubicación se trate de manera equitativa. Supongamos un archivo con hash de los atributos A1, A2 y A3. ¿En qué orden deben disponerse los bits de las funciones hash h1(A1), h2(A2) y h3(A3) en la cadena de bits que determina un número de paquete para garantizar esta equidad?
Pregunta 1
a) Los N paquetes de un archivo codificado mediante un método estático de atributos múltiples se identifican mediante cadenas de p bits (donde p=log_2 N) construidas mediante la concatenación de b1, b2,…, bn bits (donde b1+b2+… +bn = p) asociado respectivamente a los atributos A1, A2, …, An. La búsqueda de todos los artículos del fichero que cumplen la condición Ai = requiere la lectura de todos los paquetes cuyos números están identificados por una cadena de p bits en la que los valores de los bits bi asociados a Ai corresponden a los valores de los bits bi resultantes del hash del valor buscado por el Hola función. oh
Por lo tanto, n selecciona todos los paquetes cuyos números tienen la forma que se muestra en la figura 6.1. Luego, estos paquetes se escanean secuencialmente para recuperar todos los elementos que satisfacen el criterio de búsqueda.
Cifra. Firmar paquetes seleccionados
b) Si no hubo desbordamiento, el número de E/S generadas por dicha búsqueda corresponde al número de paquetes cuyos números tienen la forma citada anteriormente. Dado que el archivo contiene 2ppaquetes (2p= número de combinaciones posibles de p bits), el número de paquetes seleccionados (número de E/S) es igual a 2^(p-bi), es decir, el número de combinaciones posibles de p-bi bits ya que los bits bi están fijados por el criterio de búsqueda.
c) Siguiendo el mismo razonamiento, el número de E/S generadas por una búsqueda con la condición (Ai = y Aj= ) es igual a 2^(p-bi-bj). Por tanto, este coste es inferior al coste calculado en b). El número de E/S generadas por una búsqueda con la condición (Ai = o Aj= ) es igual a 2^(p-bi) + 2^(p-bj).
Pregunta 2
Idéntico al hash estático de múltiples atributos, buscando todos los artículos en el archivo que cumplan la condición Ai = requiere la lectura de todos los paquetes cuyos números están identificados por una cadena de bits en la que los valores de los bits bi asociados a Ai corresponden a los valores de los bits bi resultantes del hash del valor buscado por la función hi . La diferencia es que aquí los paquetes se crean dinámicamente y las firmas de los paquetes se desarrollan a medida que se distribuyen.
Por lo tanto, comenzamos construyendo una cadena de bits, denominada perfil de firma, en la que solo se ingresan los valores de los bits bi asociados con Ai. Este perfil de firma se utiliza luego para filtrar el catálogo con el fin de seleccionar todas las firmas cuyos valores de los bits bi de Ai corresponden a los del perfil de firma, independientemente de los valores de los demás bits de la firma. Si ciertos bits del perfil de firma corresponden a bits aún no desarrollados en una firma, la comparación se aplica sólo a los bits desarrollados.
Al combinar el valor deseado 12 con hi, se obtiene 3 u 11 en binario. Por tanto, el filtrado del catálogo se realizará con el perfil ??1?1 (donde ? simboliza un valor de bit desconocido). Este filtrado permitirá seleccionar las 2^(5-2) entradas del catálogo que contienen las firmas 00101, 00111, 10101, 10111, 01101, 01111, 11101 y 11111. El número resultante de E/S es simplemente 2 porque el conjunto de estas firmas hacen referencia a dos paquetes iniciales 101 y 111 que nunca estallan.
Pregunta 3
En un método de colocación estática, el orden de los bits en la firma de un paquete no importa. Por otra parte, en un método de colocación dinámica, la explosión de paquetes se realiza explotando los bits de firma uno tras otro. En la colocación sólo participan los bits utilizados de la firma, mientras que los demás bits permanecen insignificantes durante las búsquedas. Favorecer el acceso a un atributo equivale, por tanto, a colocar los bits asociados a él al principio de la firma (es decir, a la derecha) de manera que adquieran significado desde las primeras ráfagas.
Considere las siguientes funciones hash h1(A1), h2(A2), h3(A3):
h1(A1) = i^1 i^2 i^3 … i^n donde i^q corresponde al qésimo bit de h1(A1)
h^2(A2) = j^1 j^2 j^3 … j^n donde j^q corresponde al q-ésimo bit de h2(A2)
h3(A3) = k^1 k^2 k^3 … k^n donde k^q corresponde al q-ésimo bit de h3(A3)
Favorecer el acceso al atributo A2, luego al atributo A3 y finalmente al atributo A1 en este orden de prioridad equivale a colocar los bits de las funciones hash h1(A1), h2(A2) y h3(A3) en el siguiente orden: i^ 1 i^2 i^3... en k^1 k^2 k^3... k^nj^1 j^2 j^3... j^n. En este ejemplo, la ubicación en el atributo A1 solo será efectiva cuando el archivo haya alcanzado un tamaño grande, después de una cantidad significativa de ráfagas de paquetes.
Pregunta 4
Para tratar cada atributo de ubicación de manera justa, el método del archivo grid mezcla los bits de cada función hash en la cadena de bits para explotar un bit de un atributo diferente cada vez que se explota un paquete.
En el ejemplo del archivo con hash de los atributos A1, A2 y A3, el método del archivo grid explotará un bit de h1(A1) durante la primera ráfaga de un paquete, luego un bit de h2(A2) en la segunda ráfaga. de este paquete, luego un bit de h3(A3) en la tercera ráfaga, luego nuevamente un bit de h1(A1) en la cuarta ráfaga y así sucesivamente, rotando cíclicamente en cada uno de los atributos.
Por lo tanto, esta equidad se obtiene colocando los bits de las funciones hash h1(A1), h2(A2) y h3(A3) en el siguiente orden: k^1 j^1 i^1 k^2 j^2 i ^2 … k^nj^ni^n, donde i^q, j^q, k^q tienen el mismo significado que en la pregunta 5.
ES 
FR 
EN