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 (para una justificación más detallada
  98  ver FIXME: REFERENCIA A EXPLICACION DE B+)3.
  99 \layout Standard
 100
 101 Finalmente, para obtener listados basados en campos de los cuales no se
 102  tiene un índice, se implementó un ordenamiento externo.
 103 \layout Standard
 104
 105 A continuación se presenta una descripción un poco más detallada sobre todas
 106  herramientas utilizadas para resolver el trabajo práctico.
 107 \layout Section
 108
 109 Documentación de la API
 110 \layout Standard
 111
 112 Para obtener una documentación de la API más completa, se incluye en formato
 113  HTML en el CD-ROM la documentación generado con Doxygen.
 114  Esta documentación se encuentra en el directorio
 115 \family typewriter
 116 doc/api/html/index.html
 117 \family default
 118 .
 119 \layout Chapter
 120
 121 Estructura común
 122 \layout Section
 123
 124 Tipos
 125 \layout Standard
 126
 127 Se detallan a continuación los tipos de datos definidos y utilizados en
 128  las distintas implementaciones que conforman nuestro sistema, siendo el
 129  más importante de ellos en esta entrega, la estructura
 130 \family typewriter
 131 INDICE
 132 \family default
 133  que actúa como interfaz común para el manejo de cualquier tipo de índice
 134  (no importa que tipo de organización física ni de que forma esté implementado,
 135  esta estructura proveerá una interfaz abstracta para su manejo).
 136 \layout Subsection
 137
 138 Tipos Comunes
 139 \layout Standard
 140
 141 Se agregaron varios tipos comunes nuevos en esta entrega, en su mayoría
 142  relacionados a los índices.
 143  Estos tipos son brevemente descriptos a continuación y pueden ser hallados
 144  en el archivo
 145 \family typewriter
 146 indices.h
 147 \family default
 148 :
 149 \layout Itemize
 150
 151
 152 \family typewriter
 153 INDICE_DATO
 154 \family default
 155 : usado para representar el conjunto de un ID más la ubicación del dato
 156  asociado.
 157 \layout Itemize
 158
 159
 160 \family typewriter
 161 INDICE_TIPO
 162 \family default
 163 : indica el tipo de índice (B, B* o B+).
 164 \layout Itemize
 165
 166
 167 \family typewriter
 168 INDICE_FUNCION
 169 \family default
 170 : indica la función que cumple el índice (principal, selectivo o exhaustivo).
 171 \layout Itemize
 172
 173
 174 \family typewriter
 175 INDICE_TIPO_DATO
 176 \family default
 177 : indica el tipo de dato que se usa como clave.
 178 \layout Itemize
 179
 180
 181 \family typewriter
 182 CLAVE
 183 \family default
 184 : representa una clave de un índice.
 185 \layout Subsection
 186
 187 INDICE
 188 \layout Standard
 189
 190
 191 \family typewriter
 192 INDICE
 193 \family default
 194 \emph on
 195
 196 \emph default
 197 es la estructura principal que encapsula todas las funciones para el manejo
 198  de un índice.
 199  Posee punteros a funciones que permite utilizar la misma interface para
 200  distintas implementaciones de árboles.
 201
 202 \layout Standard
 203
 204 Su declaración puede ser observada en el archivo
 205 \family typewriter
 206 indices.h
 207 \family default
 208 \series bold
 209
 210 \series default
 211 y cuenta con la siguiente información:
 212 \layout Itemize
 213
 214 Tipo de índice.
 215 \layout Itemize
 216
 217 Tipo de dato que maneja.
 218 \layout Itemize
 219
 220 Función del índice.
 221 \layout Itemize
 222
 223 Información sobre el desplazamiento para ubicar el dato dentro de la estructura
 224  a indexar (para poder tener una implementación genérica que sirva para
 225  cualquier estructura).
 226 \layout Itemize
 227
 228 Información sobre archivos auxiliares para almacenar cadenas de texto y
 229  otras estructuras que eventualmente requiera un índice.
 230 \layout Itemize
 231
 232 Punteros a funciones para:
 233 \begin_deeper
 234 \layout Itemize
 235
 236 Agregar entrada.
 237 \layout Itemize
 238
 239 Borrar entrada.
 240 \layout Itemize
 241
 242 Verificar la existencia de una entrada.
 243 \layout Itemize
 244
 245 Buscar entradas.
 246 \layout Itemize
 247
 248 Obtener clave menor o mayor del índice.
 249 \layout Itemize
 250
 251 Obtener siguiente clave (para recorrido secuencial).
 252 \end_deeper
 253 \layout Standard
 254
 255 Esta estructura define los valores de sus punteros según el tipo de implementaci
 256 ón que se desee manejar y esto se realiza a través de la API
 257 \family typewriter
 258 emufs_indice
 259 \family default
 260 , implementada en
 261 \family typewriter
 262 indices.h
 263 \family default
 264 .
 265  Esta API posee funciones para crear y destruir índices, agregarlos y quitarlos
 266  de una estructura
 267 \family typewriter
 268 EMUFS
 269 \family default
 270 , comparar claves y otras, necesarias para la correcta y completa utilización
 271  de los índices a través de la interfaz de
 272 \family typewriter
 273 EMUFS
 274 \family default
 275  descripta en la entrega anterior.
 276 \layout Subsubsection
 277
 278 Integración con
 279 \family typewriter
 280 EMUFS
 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 \layout Chapter
 317
 318 Implementación
 319 \layout Section
 320
 321 Árbol B
 322 \layout Section
 323
 324 Árbol B*
 325 \layout Section
 326
 327 Árbol B+
 328 \layout Section
 329
 330 Ordenamiento externo
 331 \the_end