6








         APENDICE H. ESTRUCTURA DEL ARCHIVO INVERTIDO Y FORMATO DE REGISTROS
          ___________________________________________________________________

          A. Introducci¢n

            El archivo invertido  de CDS/ISIS est   formado en realidad por
          seis archivos f¡sicos, cinco de los cuales contienen los trminos
          de b£squeda del diccionario (organizados como  un  rbol  B*) y el
          sexto  contiene  la  lista de ocurrencias  (postings) asociadas a
          cada trmino.  A fin de optimizar el almacenamiento  en disco, se
          mantienen dos  rboles B* por separado, uno para trminos de hasta
          10  caracteres (almacenados en los archivos .N01/.L01) y uno para
          los  trminos  de  m s 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 ocu-
          rrencias respectivas (postings) en el archivo .IFP.

             La  relaci¢n  entre  los  varios  archivos  se  representa es-
          quem 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 desplaza-
          miento dentro del bloque, cada uno expresado como un entero.

          B. 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):

          IDTYPE  Tipo de Arbol B* (1 para .N01/.L01, 2 para .N02/.L02)
          ORDN   Orden de  los Nodos (cada registro  del  .N0x  contiene un
              m ximo de 2 * ORDN llaves)







                                         283








                             ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
                             ³ Ra¡z del Arbol ³   archivo.CNT
                             ÀÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÙ
                                     ³
                                     V
                         ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
                         ³ llave1 llave2 ..llaven ³ archivo.NOx
                         ÀÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÙ Ra¡z
                             ³               ³
                   ÚÄÄÄÄÄÄÄÄÄÙ               ÀÄÄÄÄÄÄÄÄÄ¿
                   ³                                   ³
                   V                                   V
          ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿           ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
          ³llave1 llave2..llaven ³           ³llave1 llave2..llaven ³
          ÀÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ           ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÙ
               ³                                ÚÄÄÄÄÄÄÄÄÄÄÄÙ ¡ndice del
               V                                V             primer nivel
           ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿           ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
           ³llave1 llave2.llaven ³           ³llave1 llave2..llaven ³
           ÀÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÙ           ÀÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÙ
                   ³                                    ³ ¡ndice del £ltimo
                   ³                             ÚÄÄÄÄÄÄÙ     nivel
                   ³                             ³          ÄÄÄÄÄÄÄÄÄÄ
                   V                             V          archivo LOx
           ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿          ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
           ³llave1 llave2..llaven ³          ³ llave1 llave2 llaven ³
           ÀÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ          ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
               ³                                            ÄÄÄÄÄÄÄÄÄÄÄÄ
               ³                                            ARCHIVO IFP
               V
           ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
           ³ P1 P2 P3...         ...Pn ³
           ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
                    Figura 67: Estructura del archivo invertido

          ORDF  Orden de las hojas (cada registro del .L0x contiene un
                  m ximo de 2 * ORDF llaves)
          N     N£mero de buffers de memoria asignados a los nodos
          K     N£mero de buffers asignados al ¡ndice de primer nivel
                  (K < N)
          LIV   N£mero actual de niveles de ¡ndices
          POSRX*  Apuntador hacia el registro ra¡z en .N0x
          NMAXPOS*  Siguiente posici¢n disponible en el archivo .L0x
          FMAXOS*  Siguiente posici¢n disponible en el archivo .N0x
          ABNORMAL Indicador formal de normalidad del  rbol B* (0 si el
                     rbol B* es anormal, 1 si el  rbol B* es normal). 
                     Un  rbol B* es anormal si el archivo de nodos .N0x
                      contiene s¢lo la ra¡z.
          ORDN,  ORDF, N y K son fijos para un sistema generado dado. En la
          versi¢n  actual  del  sistema  estas  variables  deben  tener los
          siguientes valores:

          ORDN = 5; ORDF = 5; N = 15; K = 5 para ambos arboles B*

          Los dem s valores son establecidos de acuerdo  a los requerimien-
          tos cuando se generan los arboles B*.


                                         284









          C. Formato de los archivos .N0x

           Estos archivos contienen los ¡ndices del diccionario de trminos
          recuperables (.N01 para trminos de menos de 11 caracteres y .N02
          para  trminos  mayores  de  10  caracteres).  Los  registros del
          archivo .N0x tienen el siguiente formato (los campos marcados con
          * son enteros de 31 bits, con signo):

          POS*   Un entero  que  indica  el  n£mero  relativo  del registro
              (1 para el primer registro, 2 para el segundo, etc.)
          OCK   un entero  que indica  el  n£mero  de claves activas  en el
              registro (1 <= OCK <= 2 * ORDN)
          IT     Un entero que indica el tipo de   rbol B*  (1 para .N01, 2
              para .N02)
          IDX   Un  vector  de  ORDN  elementos (OCK  de  los  cuales est n
              activos) cada uno de ellos tiene el siguiente formato:
          KEY     Una  cadena  de  caracteres  de  longitud  fija  con  LEx
              caracteres (LE1=10, LE2=30)
          PUNT   Un apuntador al  registro  de  .N0x  (si PUNT  >  0), ¢ al
              registro  de  .L0x  (si PUNT  <  0),  cuyo  IDX(1).KEY = KEY.
              PUNT=0 indica un elemento activo. Un PUNT positivo indica una
              rama hacia un nivel jer rquicamente inferior en el ¡ndice. El
              nivel de ¡ndice m s bajo (PUNT < 0) apunta hacia las hojas en
              el archivo .L0x.
           
          D. Formato de los archivos .L0x

            Estos  archivos  contienen el  diccionario completo de trminos
          recuperables (.L01  para los trminos de menos de 11 caracteres y
          .L02 para trminos de m s de 10 caracteres). Los registros de los
          archivos  .L0x tienen el  siguiente formato (los  campos marcados
          con * son enteros de 31 bits, con signo):

          POS*   Un  entero  que  indica  el  n£mero  relativo  de registro
              (1 para el primer registro, 2 para el segundo, etc.)
          OCK    Un  entero  que indica el n£mero  de llaves activas  en el
              registro (1 <= OCK <= 2 * ORDF)
          IT     Un entero que indica el tipo de  rbol B*  (1  para .L01, 2
              para .L02)
          PS*    Apuntador  hacia el registro siguiente de  .L0x  (o sea el
              registro cuyo IDX[1].KEY es el sucesor inmediato de
          IDX[OCK].KEY  en  este  registro  (esto  se   usa  para  acelerar
              el acceso secuencial al archivo)
          IDX    Un vector  de  ORDN  elementos (OCK  de  los  cuales est n
              activos) cada uno de ellos tiene el siguiente formato:
          KEY  una   cadena  de  caracteres  de   longitud   fija   de  LEx
              caracteres (LE1=10, LE2=30)
          INFO Apuntador hacia el  registro  .IFP donde inicia la  lista de
              apuntadores (postings)  asociados a KEY.  Este apuntador est 
              formado  por  dos  enteros  de  31  bits,  con  signo,  de la
              siguiente forma:
              INFO[1]* n£mero relativo de bloque en el .IFP
              INFO[2]* desplazamiento (n£mero de palabra relativo a 0)hacia
              la lista de apuntadores (postings).



                                         285








          E. Formato del archivo .IFP

            Este archivo contiene  la lista  de apuntadores (postings) para
          cada trmino del diccionario.  Cada  lista  de  estos apuntadores
          tiene el  formato que se  indica  m s adelante.  El  archivo est 
          estructurado en bloques de 512 caracteres, donde (para un archivo
          recin cargado y compactado)  las listas de apuntadores para cada
          trmino son adyacentes, excepto cuando se indica a continuaci¢n.

           El formato general de cada bloque es:

          IFPBLK   Un entero  con signo  de  31-bit  que  indica  el n£mero
              de  bloque  de  ese   bloque  (los  bloques   se   numeran  a
              partir de 1)
          IFPREC   Un vector de 127 enteros con signo de 31-bits
          IFPREC[1]  e IFPREC[2] del primer  bloque,  integran un apuntador
              hacia  la   siguiente  posici¢n  disponible   en  el  archivo
              .IFP.

            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 desplaza-
          miento  hacia la  primera palabra en  IFPREC  es 0).  La lista de
          apuntadores (postings)  asociados al  primer  trmino 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 apun-
          tadores (8  bytes para cada uno de ellos). El encabezado tiene el
          siguiente formato (cada campo es un entero con signo de 31-bits):

           IFPNXTB* Apuntador hacia el pr¢ximo segmento (n£mero de bloque)
           IFPNXTP* Apuntador hacia el pr¢ximo segmento (desplazamiento)
           IFPTOTP* N£mero total de apuntadores (postings), (exacto s¢lo en
                    el primer segmento)
           IFPSEGP* N£mero de apuntadores (postings) en este segmento
                    (IFPSEGP <= IFPTOTP)
           IFPSEGC* Capacidad del segmento (es decir, n£mero de apuntadores
                    (postings) que pueden ser almacenados en este seg
                    mento).

          Cada apuntador (posting)  es una cadena de 64-bits  integrada del
          siguiente modo:

          PMFN  (24 bits) n£mero del registro en el archivo maestro (MFN)
          PTAG  (16 bits) identificador de campo (asignado en la FST)
          POCC  (8 bits) n£mero de la ocurrencia
          PCNT  (16 bits) n£mero secuencial del trmino en el campo

          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).



                                         286








          La  lista de  aputadores  (postings)  es  almacenada en secuencia
          ascendente   de   PMFN/PTAG/POCC/PCNT.   Cuando   se   carga  se-
          cuencialmente  el archivo  invertido (por ejemplo  despus de una
          generaci¢n completa del archivo invertido con ISISINV), cada lis-
          ta est  formada por uno o m s segmentos adyacentes.  Si IFPTOT <=
          32768,  entonces: IFPNXTB/IFPNXTP = 0/0 y IFPTOT = IFPSEGP = IFP-
          SEGC.

          Conforme   se  realizan  actualizaciones,   pueden  irse  creando
          segmentos adicionales cuando sea necesario agregar nuevos apunta-
          dores (postings).  En este caso se crea un nuevo segmento con ca-
          pacidad IFPTOTP, lig ndolo a otros segmentos (mediante el apunta-
          dor 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 inser-
          tarse el nuevo apuntador (posting),  son distribuidos equitativa-
          mente entre este  segmento y  el nuevo recin 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 ³
              ÀÄÄÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
          despus  de  segmentar 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 despus de  la otra.  Sin embargo, a
          fin de facilitar el acceso al .IFP los segmentos se  almacenan de
          modo que:

          1.  el encabezado y el  primer apuntador (posting)  en cada lista
          (28 bytes) nunca estn divididas entre dos bloques.
          2.  nunca se divide un apuntador (posting)  entre dos bloques; si
          no hay suficiente espacio en el bloque actual,  todo el apuntador
          (posting) es almacenado en el siguiente bloque.







                                         287




: