From 36612600baec1e24eee239cf773bba048c5d6453 Mon Sep 17 00:00:00 2001 From: Ricardo Markiewicz Date: Mon, 31 May 2004 10:09:20 +0000 Subject: [PATCH] agrego b y B* --- doc/informe_2da_entrega.lyx | 72 +++++++++++++++++++++++++++++++++++++ 1 file changed, 72 insertions(+) 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 -- 2.43.0