From: Ricardo Markiewicz <gazer.arg@gmail.com>
Date: Mon, 31 May 2004 10:09:20 +0000 (+0000)
Subject:  agrego b y B*
X-Git-Tag: svn_import_r684~6
X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/commitdiff_plain/36612600baec1e24eee239cf773bba048c5d6453?ds=sidebyside;hp=939371a10ca8ccd1811505ec58865046aba4d7f2

 agrego b y B*
---

diff --git a/doc/informe_2da_entrega.lyx b/doc/informe_2da_entrega.lyx
index 7c71ab5..934ed6e 100644
--- a/doc/informe_2da_entrega.lyx
+++ b/doc/informe_2da_entrega.lyx
@@ -324,9 +324,81 @@ Especificaciones de 
 \layout Section
 
 Indice B
+\layout Standard
+
+En esta sección no se explicará como funciona la implementación del árbol
+ B, sino que se darán algunos detalles de la implementación para algunos
+ casos particulares.
+\layout Standard
+
+Cada nodo del árbol cuenta con un header y un array de datos, donde cada
+ dato contiene, entre otras cosas la clave, el dato al que apunta (id/bloque
+ del archivo de datos) y el hijo derecho (aquel nodo que contiene las claves
+ superiores).
+ En el header se guarda el puntero (numero de nodo) al hijo izquierdo, que
+ viene a ser el nodo que contiene claves menores a la primer clave de nodo
+ actual.
+\layout Standard
+
+Existen 2 casos particulares para lo que contiene la clave y el dato.
+ El primer caso se da cuando la clave es de tipo string.
+\layout Standard
+
+Cuando un indice debe almacenar string, estos no son guardados en el arbol,
+ sino que se reutiliza la estructura EMUFS de la primer entrega para guardar
+ las cadenas de texto, utilizano para ello una organización de registros
+ de longitud variable sin bloques, elegida de forma arbitraria.
+ En la clave del arbol se guardará entonces el ID del registro que contiene
+ el texto en la estructura mensionada anteriormente.
+ Cuando se quiere recuperar una clave, se lee el archivo que contiene las
+ claves de texto (que permanecen abreviadas).
+\layout Standard
+
+El otro caso particular es para los indices con clave repetida (como ser
+ el selectivo y el exahustivo).
+ Para este caso lo que cambia es lo que se almacena en el campo DATO que
+ acompaña a la clave.
+ Este DATO contendra el ID de un registro que se guarda nuevamente en un
+ EMUFS en formato de registro de longitud variable sin bloques, donde estarán
+ los ID/Bloque reales del archivo de dato de todas las ocurrencias de la
+ clave correspondiente.
+\layout Standard
+
+Cada vez que se inserta una clave y ya existia una previa, se agrega a dicho
+ arreglo la nueva posicion y luego se guarda.
+ Si al eliminar todos los datos de una clave este array quedara vacio, la
+ clave es eliminada del arbol.
+\layout Standard
+
+Puede darse el caso (es mas, casi todos los indices utilizados en el TP
+ son de esta manera) que ocurran ambas situaciones descriptas anteriormente,
+ por lo que para un indice, por ejemplo de presentacion de los articulos,
+ se tenga que acceder a 9 archivos (el arbol B, 4 para los string, 4 para
+ las claves repetidas) para obtener todos los ID del archivo de datos para
+ mostrar en pantalla.
+ Con esta falla de diseño y todo el acceso a registros por campos de identifacac
+ion no unico es muy superior a realizar una busqueda secuencial sobre todo
+ el archivo para realizar una consultas.
 \layout Section
 
 Indice B*
+\layout Standard
+
+Para la implantación de los árboles B* se tomo la desición de tratar a la
+ raiz como si fuera un árbol B en lugar de tomar una raiz de 2*tam_bloque
+ para reutilizar el código ya hecho para el árbol B y todas las funciones
+ anexas.
+\layout Standard
+
+Lo único que se reescribió fue la función insertar, que aunque es muy similar
+ al del otro árbol, meter más codigo en la misma función hacía aún más dificil
+ de mantener y debuggear el árbol.
+\layout Standard
+
+Otro cambio a la API de árbol B fue en el borrar, que mediante una macro
+ se verifica que tipo de árbol se está tratando y en base a eso se calcula
+ la cantidad de hijos mínimos antes de fundir 2 nodos (o pedir una clave
+ a algún hermano).
 \layout Subsection
 
 Decisiones de diseño