doc/informe_2da_entrega.lyx

   1 #LyX 1.3 created this file. For more info see http://www.lyx.org/
   2 \lyxformat 221
   3 \textclass book
   4 \language spanish
   5 \inputencoding auto
   6 \fontscheme palatino
   7 \graphics default
   8 \paperfontsize default
   9 \spacing single
  10 \papersize a4paper
  11 \paperpackage widemarginsa4
  12 \use_geometry 0
  13 \use_amsmath 0
  14 \use_natbib 0
  15 \use_numerical_citations 0
  16 \paperorientation portrait
  17 \secnumdepth 3
  18 \tocdepth 3
  19 \paragraph_separation indent
  20 \defskip medskip
  21 \quotes_language english
  22 \quotes_times 2
  23 \papercolumns 1
  24 \papersides 1
  25 \paperpagestyle default
  26
  27 \layout Title
  28
  29 Organización de Datos (75.06)
  30 \newline
  31 Trabajo Práctico
  32 \newline
  33 E
  34 \begin_inset Formula $\mu$
  35 \end_inset
  36
  37 FS
  38 \layout Author
  39
  40
  41 \series bold
  42 Grupo 11
  43 \series default
  44
  45 \newline
  46 Nicolás Dimov (77624)
  47 \newline
  48 Alan Kennedy (78907)
  49 \newline
  50 Leandro Lucarella (77891)
  51 \newline
  52 Ricardo Markiewicz (78226)
  53 \layout Date
  54
  55 Segunda Entrega, 31 de Mayo de 2004
  56 \layout Standard
  57
  58
  59 \begin_inset LatexCommand \tableofcontents{}
  60
  61 \end_inset
  62
  63
  64 \layout Chapter
  65
  66 Introducción
  67 \layout Standard
  68
  69 En esta entrega el trabajo estuvo concentrado en el manejo de índices para
  70  los tipos de archivos implementados en la primer entrega.
  71  Los índices se implementaron con:
  72 \layout Enumerate
  73
  74 Árbol B
  75 \layout Enumerate
  76
  77 Árbol B*
  78 \layout Enumerate
  79
  80 Árbol B+
  81 \layout Standard
  82
  83 Además de esto, se pide 3 funciones distintas para estos índices:
  84 \layout Enumerate
  85
  86 Principal
  87 \layout Enumerate
  88
  89 Selectivo
  90 \layout Enumerate
  91
  92 Exhaustivo
  93 \layout Standard
  94
  95 Con la autorización de los ayudantes de la cátedra decidimos que el árbol
  96  B+ sólo pueda ser utilizado para índices principal ya que de otra manera
  97  no tiene sentido el set secuencial.
  98 \layout Standard
  99
 100 Finalmente, para obtener listados basados en campos de los cuales no se
 101  tiene un índice, se implementó un ordenamiento externo.
 102 \layout Standard
 103
 104 A continuación se presenta una descripción un poco más detallada sobre todas
 105  herramientas utilizadas para resolver el trabajo práctico.
 106 \layout Section
 107
 108 Documentación de la API
 109 \layout Standard
 110
 111 Para obtener una documentación de la API más completa, se incluye en formato
 112  HTML en el CD-ROM la documentación generado con Doxygen.
 113  Esta documentación se encuentra en el directorio
 114 \family typewriter
 115 doc/api/html/index.html
 116 \family default
 117 .
 118 \layout Chapter
 119
 120 Estructura común
 121 \layout Section
 122
 123 Tipos
 124 \layout Standard
 125
 126 Se detallan a continuación los tipos de datos definidos y utilizados en
 127  las distintas implementaciones que conforman nuestro sistema, siendo el
 128  más importante de ellos en esta entrega, la estructura
 129 \family typewriter
 130 INDICE
 131 \family default
 132  que actúa como interfaz común para el manejo de cualquier tipo de índice
 133  (no importa que tipo de organización física ni de que forma esté implementado,
 134  esta estructura proveerá una interfaz abstracta para su manejo).
 135 \layout Subsection
 136
 137 Tipos Comunes
 138 \layout Standard
 139
 140 Se agregaron varios tipos comunes nuevos en esta entrega, en su mayoría
 141  relacionados a los índices.
 142  Estos tipos son brevemente descriptos a continuación y pueden ser hallados
 143  en el archivo
 144 \family typewriter
 145 indices.h
 146 \family default
 147 :
 148 \layout Itemize
 149
 150
 151 \family typewriter
 152 INDICE_DATO
 153 \family default
 154 : usado para representar el conjunto de un ID más su dato.
 155 \layout Itemize
 156
 157
 158 \family typewriter
 159 INDICE_TIPO
 160 \family default
 161 : indica el tipo de índice (B, B* o B+).
 162 \layout Itemize
 163
 164
 165 \family typewriter
 166 INDICE_FUNCION
 167 \family default
 168 : indica la función que cumple el índice (principal, selectivo o exhaustivo).
 169 \layout Itemize
 170
 171
 172 \family typewriter
 173 INDICE_TIPO_DATO
 174 \family default
 175 : indica el tipo de dato que se usa como clave.
 176 \layout Itemize
 177
 178
 179 \family typewriter
 180 CLAVE
 181 \family default
 182 : representa una clave de un índice.
 183 \layout Subsection
 184
 185 INDICE
 186 \layout Standard
 187
 188
 189 \family typewriter
 190 INDICE
 191 \family default
 192 \emph on
 193
 194 \emph default
 195 es la estructura principal que encapsula todas las funciones para el manejo
 196  de un índice.
 197  Posee punteros a funciones que permite utilizar la misma interface para
 198  distintas implementaciones de árboles.
 199
 200 \layout Standard
 201
 202 Su declaración puede ser observada en el archivo
 203 \family typewriter
 204 indices.h
 205 \family default
 206 \series bold
 207
 208 \series default
 209 y cuenta con la siguiente información:
 210 \layout Itemize
 211
 212 Tipo de índice.
 213 \layout Itemize
 214
 215 Tipo de dato que maneja.
 216 \layout Itemize
 217
 218 Función del índice.
 219 \layout Itemize
 220
 221 Información sobre el desplazamiento para ubicar el dato dentro de la estructura
 222  a indexar (para poder tener una implementación genérica que sirva para
 223  cualquier estructura).
 224 \layout Itemize
 225
 226 Información sobre archivos auxiliares para almacenar cadenas de texto y
 227  otras estructuras que eventualmente requiera un índice.
 228 \layout Itemize
 229
 230 Punteros a funciones para:
 231 \begin_deeper
 232 \layout Itemize
 233
 234 Agregar entrada.
 235 \layout Itemize
 236
 237 Borrar entrada.
 238 \layout Itemize
 239
 240 Verificar la existencia de una entrada.
 241 \layout Itemize
 242
 243 Buscar entradas.
 244 \layout Itemize
 245
 246 Obtener clave menor o mayor del índice.
 247 \layout Itemize
 248
 249 Obtener siguiente clave (para recorrido secuencial).
 250 \end_deeper
 251 \layout Standard
 252
 253 Esta estructura define los valores de sus punteros según el tipo de implementaci
 254 ón que se desee manejar y esto se realiza a través de la API
 255 \family typewriter
 256 emufs_indice
 257 \family default
 258 , implementada en
 259 \family typewriter
 260 indices.h
 261 \family default
 262 .
 263  Esta API posee funciones para crear y destruir índices, agregarlos y quitarlos
 264  de una estructura
 265 \family typewriter
 266 EMUFS
 267 \family default
 268 , comparar claves y otras, necesarias para la correcta y completa utilización
 269  de los índices a través de la interfaz de
 270 \family typewriter
 271 EMUFS
 272 \family default
 273  descripta en la entrega anterior.
 274 \layout Subsubsection
 275
 276 Integración con
 277 \family typewriter
 278 EMUFS
 279 \family default
 280 .
 281 \layout Standard
 282
 283 Para integrar la utilización de índices a
 284 \family typewriter
 285 EMUFS
 286 \family default
 287  fueron necesarios los siguientes cambios:
 288 \layout Paragraph
 289
 290 Nuevos tipos de archivo.
 291 \layout Standard
 292
 293 Se incluyen dos tipos de archivo nuevos T4 y T5, que representan, respectivament
 294 e, un archivo T1 (registros variables, bloques fijos) y un archivo T3 (registros
 295  y bloques fijos), ambos organizados como un set secuencial indexado.
 296  De esta manera se conserva la interfaz de
 297 \family typewriter
 298 EMUFS
 299 \family default
 300  (los punteros a funciones) incluso cuando se debe insertar de forma ordenada,
 301  ya que al saber que es T4 o T5 siempre se inserta de forma ordenada.
 302 \layout Paragraph
 303
 304 Puntero a un arreglo de índices.
 305 \layout Standard
 306
 307 Se agrega a la estructura
 308 \family typewriter
 309 EMUFS
 310 \family default
 311  un puntero a un arreglo de
 312 \family typewriter
 313 INDICE
 314 \family default
 315 , donde el primero es siempre el índice principal.
 316 \the_end