Con la autorización de los ayudantes de la cátedra decidimos que el árbol
B+ sólo pueda ser utilizado para índices principal ya que de otra manera
- no tiene sentido el set secuencial.
+ no tiene sentido el set secuencial (ver página
+\begin_inset LatexCommand \pageref{sub:justificacion}
+
+\end_inset
+
+ para una justificación más detallada).
\layout Standard
Finalmente, para obtener listados basados en campos de los cuales no se
\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
indicará a la hora de grabar registros en nuestro archivo de datos con
bloques (Organización del TP1, Tipo1 o 3), en que bloque de datos debemos
realizar la mencionada inserción.
- La operativa se detalla mas adelante, pero basicamente realizaremos una
+ La operativa se detalla más adelante, pero básicamente realizaremos una
búsqueda del ancla menor inmediata a la clave del registro que se desea
- insertar, y esto nos indicara el bloque apropiado.
- (el bloque donde esta el ancla).
+ insertar, y esto nos indicará el bloque apropiado (el bloque donde esta
+ el ancla).
\layout Standard
Como resultado concreto de este comportamiento (teniendo en cuenta también
del encadenamiento es denominada
\series bold
Sequence Set.
+\layout Subsubsection
+
+
+\begin_inset LatexCommand \label{sub:justificacion}
+
+\end_inset
+
+Razones por las cuales el B+ es útil sólo para clave principal.
+\layout Standard
+
+El mejor aprovechamiento del Arbol B+ se da en su utilizacion en implementacion
+ ISAM (Indexed Sequential Access Method), en donde se realiza una indexacion
+ parcial de claves, sólo ingresando en el árbol las claves anclas de cada
+ bloque en el archivo de datos.
+
+\layout Standard
+
+Esta aplicación del árbol B+ a ISAM, además de indicarnos donde grabar y
+ donde buscar los registros por identificación primaria, nos asegura el
+ ordenamiento de los registros parcialmente a nivel de bloque (esto es,
+ los registros en un bloque dado, estarán ordenados, pero los bloques no
+ necesariamente).
+ Así pués, recorriendo el Sequence Set del Arbol B+, minimizaremos los saltos
+ de lectura en disco, pues dentro de un bloque indicado por un ancla dada
+ en el Sequence Set, podremos recorrer los registros secuencialmente.
+\layout Standard
+
+Visto y considerando que la aplicación más importante a nuestro criterio
+ del Arbol B+, era para la indexacion parcial de claves primarias, y que
+ en caso de utilizarlo para otros índices, el B+ se convertiría simplemente
+ en un B con encadenamiento a nivel de hojas, luego de consultar con los
+ ayudantes, decidimos utilizarlo unicamente para el índice primario, y utilizar
+ el B y B* para los restantes índices y/o el primario.
+
\layout Subsection
Estructura
projects / z.facultad / 75.06 / emufs.git / blobdiff