 |
 |
 |
||||||||||
|
|
|
|
||||||||||
El archivo invertido de CDS/ISIS está formado en realidad por seis archivos físicos, cinco de los cuales contienen los términos de búsqueda del diccionario (organizados como un árbol B*) y el sexto contiene la lista de ocurrencias (postings) asociadas a cada término. A fin de optimizar el almacenamiento en disco, se mantienen dos árboles B* por separado, uno para términos de hasta 10 caracteres (almacenados en los archivos .N01/.L01) y uno para los términos de mas de 10 caracteres, hasta un máximo de 30 (almacenados en los archivos .N02/.L02). El archivo .CNT contiene campos de control para ambos árboles B*. En cada archivo de árbol B*, el archivo .N0x contiene los nodos del árbol y el archivo .L0x contiene las hojas. Los registros de hoja apuntan a las ocurrencias respectivas (postings) en el archivo .IFP.
La relación entre los varios archivos se representa esquemáticamente en la Figura 67.
La relación física entre estos seis archivos está dada por un apuntador, el cual representa la posición relativa del registro al que se está señalando. Una dirección relativa es el número ordinal del registro en un determinado archivo (por ejemplo, el primer registro es el registro 1, el segundo es el registro 2, etc.). El archivo .CNT apunta al archivo .N0x; el archivo .N0x apunta al .L0x; y el archivo .L0x apunta al .IFP. Dado que el .IFP es un archivo compacto (empacado), el apuntador de .L0x a .IFP tiene dos componentes: el número del bloque y el desplazamiento dentro del bloque, cada uno expresado como un entero.
FORMATO DEL ARCHIVO .CNT
Este archivo contiene dos registros de longitud fija de 26 bytes (uno para cada Arbol B*) cada uno de los cuales contiene 10 enteros del siguiente modo (los campos marcados con * son enteros con signo, de 31 bits):
Los demás valores son establecidos de acuerdo a los requerimientos cuando se generan los arboles B*.
Figura 67: Estructura del archivo invertido
FORMATO DE LOS ARCHIVOS .N0X
Estos archivos contienen los índices del diccionario de términos recuperables (.N01 para términos de menos de 11 caracteres y .N02 para términos mayores de 10 caracteres). Los registros del archivo .N0x tienen el siguiente formato (los campos marcados con * son enteros de 31 bits, con signo):
FORMATO DE LOS ARCHIVOS .L0X
Estos archivos contienen el diccionario completo de términos recuperables (.L01 para los términos de menos de 11 caracteres y .L02 para términos de mas de 10 caracteres). Los registros de los archivos .L0x tienen el siguiente formato (los campos marcados con * son enteros de 31 bits, con signo):
FORMATO DEL ARCHIVO .IFP
Este archivo contiene la lista de apuntadores (postings) para cada término del diccionario. Cada lista de estos apuntadores tiene el formato que se indica mas adelante. El archivo está estructurado en bloques de 512 caracteres, donde (para un archivo recién cargado y compactado) las listas de apuntadores para cada término son adyacentes, excepto cuando se indica a continuación.
El formato general de cada bloque es:
Los apuntadores desde .L0x hacia .IFP y los apuntadores dentro de .IFP están formados por dos enteros con signo de 31-bits: el primer entero es el número del bloque y el segundo es el desplazamiento en palabras en IFPREC (por ejemplo, el desplazamiento hacia la primera palabra en IFPREC es 0). La lista de apuntadores (postings) asociados al primer término de búsqueda empezará por lo tanto en 1/0.
Cada lista de apuntadores (postings) está formada por un encabezado (5 dobles-palabras) seguido por la lista real de apuntadores (8 bytes para cada uno de ellos). El encabezado tiene el siguiente formato (cada campo es un entero con signo de 31-bits):
Cada apuntador (posting) es una cadena de 64-bits integrada del siguiente modo:
Cada campo se almacena en estricta secuencia de izquierda a derecha, agregándole ceros a la izquierda si es necesario, para ajustar la cadena de bits correspondiente hacia la derecha (esto permite la comparación de dos apuntadores (postings) tratándolos como cadenas de caracteres).
La lista de apuntadores (postings) es almacenada en secuencia ascendente de PMFN/PTAG/POCC/PCNT. Cuando se carga secuencialmente el archivo invertido (por ejemplo después de una generación completa del archivo invertido con ISISINV), cada lista está formada por uno o mas segmentos adyacentes. Si IFPTOT <= 32768, entonces: IFPNXTB/IFPNXTP = 0/0 y IFPTOT = IFPSEGP = IFPSEGC.
Conforme se realizan actualizaciones, pueden irse creando segmentos adicionales cuando sea necesario agregar nuevos apuntadores (postings). En este caso se crea un nuevo segmento con capacidad IFPTOTP, ligándolo a otros segmentos (mediante el apuntador IFPNXTB /IFPNXTP) de modo que se mantenga la secuencia PMFN/PTAG/POCC/PCNT. Cada vez que ocurre una división de este tipo, los apuntadores (postings) del segmento donde debía insertarse el nuevo apuntador (posting), son distribuidos equitativamente entre este segmento y el nuevo recién creado. Los nuevos segmentos son siempre insertados al final del archivo (el cual es mantenido en IFPREC[1]/IFPREC[2] del primer bloque de .IFP).
Por ejemplo, supóngase que debe insertarse un nuevo apuntador (posting) Px entre P2 y P3 en la siguiente lista:
____________________________________________
| 0 0 5 5 5 | P1 P2 P3 P4 P5 |
|________________|_________________________|
después de sementar la lista, (y suponiendo que la siguiente posición disponible en .IFP es 3/4) la lista de apuntadores (postings) estar formada por los dos segmentos:
____________________________________________
| 3 4 5 3 5 | P1 P2 Px -- -- |
|________________|_________________________|
|
|
___V________________________________________
| 0 0 5 3 5 | P3 P4 P5 -- -- |
|________________|_________________________|
En esta situación, no se creará un nuevo segmento hasta que cualquiera de los segmentos se llene nuevamente.
Como ya se mencionó, normalmente las listas de apuntadores (postings) se almacenan una después de la otra. Sin embargo, a fin de facilitar el acceso al .IFP los segmentos se almacenan de modo que: