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 (para una justificación más detallada
- ver FIXME: REFERENCIA A EXPLICACION DE B+)3.
+ no tiene sentido el set secuencial.
\layout Standard
Finalmente, para obtener listados basados en campos de los cuales no se
\family typewriter
INDICE_DATO
\family default
-: usado para representar el conjunto de un ID más la ubicación del dato
- asociado.
+: usado para representar el conjunto de un ID más su dato.
\layout Itemize
Integración con
\family typewriter
EMUFS
+\family default
+.
\layout Standard
Para integrar la utilización de índices a
fueron necesarios los siguientes cambios:
\layout Paragraph
-Nuevos tipos de archivo
+Nuevos tipos de archivo.
\layout Standard
Se incluyen dos tipos de archivo nuevos T4 y T5, que representan, respectivament
ya que al saber que es T4 o T5 siempre se inserta de forma ordenada.
\layout Paragraph
-Puntero a un arreglo de índices
+Puntero a un arreglo de índices.
\layout Standard
Se agrega a la estructura
, donde el primero es siempre el índice principal.
\layout Chapter
-Implementación
+Especificaciones de índices
\layout Section
-Árbol B
+Indice B
\layout Section
-Árbol B*
+Indice B*
\layout Section
-Árbol B+
-\layout Section
+Indice B+ Secuencial Indexado
+\layout Standard
+
+Se ha implementado un índice secuencial indexado utilizando un árbol B+,
+ el cual tiene la particularidad de tener en sus hojas todas las claves
+ que se han insertado.
+\layout Standard
+
+La estructura de un nodo del árbol es la siguiente:
+\layout Itemize
+
+Nivel
+\layout Itemize
+
+Cantidad de claves
+\layout Itemize
+
+Arreglo de claves
+\layout Itemize
+
+Arreglo de hijos
+\layout Standard
+
+Esta estructura se encuentra en el archivo
+\family typewriter
+indice_bplus.h
+\layout Standard
+
+Esta organización permite, con la ayuda del árbol, mantener el archivo de
+ datos ordenado por la clave principal.
+\layout Standard
+
+Para lograr esto, el árbol nos indicará donde (en qué bloque) debe insertarse
+ un registro.
+ (ver 3.3.1 Inserción)
+\layout Standard
+
+En el caso de una hoja, dado que cada nodo posee un hijo mas que la cantidad
+ de claves, el hijo que sobra será utilizado como referencia al nodo
+\begin_inset Quotes eld
+\end_inset
+
+hermano
+\begin_inset Quotes erd
+\end_inset
+
+, lo cual constituye el
+\begin_inset Quotes eld
+\end_inset
+
+set secuencial
+\begin_inset Quotes erd
+\end_inset
+
+ del índice.
+ Para un nodo que no sea hoja el hijo será el número de nodo correspondiente
+ según la clave, es decir, para la clave
+\series bold
+\emph on
+n
+\series default
+\emph default
+el hijo
+\series bold
+\emph on
+n
+\series default
+\emph default
+ contiene claves menores y el hijo
+\series bold
+\emph on
+n+1
+\series default
+\emph default
+ contiene las claves mayores.
+ En el caso particular del nivel 1 el hijo
+\series bold
+\emph on
+n+1
+\series default
+\emph default
+ contiene las claves mayores o iguales ya que el
+\begin_inset Quotes eld
+\end_inset
+
+secuence set
+\begin_inset Quotes erd
+\end_inset
+
+ debe contener todas las claves insertadas, esto produce que exista una
+ repetición de las claves entre el nivel 1 y el 0.
+\layout Standard
+
+En nuestro caso hemos implementado un Secuencial Indexado tipo ISAM (Indexed
+ Sequential Access Method) el cual posee en sus hojas las anclas de cada
+ bloque en el archivo de datos, es decir, solo se guardan en los nodos del
+ arbol la menor de las claves de un bloque del archivo de datos, acompañada
+ cada clave por el numero de bloque al cual pertenece.
+\layout Subsection
+
+Inserción
+\layout Standard
+
+Para realizar una inserción en el archivo de datos se debe realizar una
+ consulta en el árbol, la cual nos indicará el número de bloque donde debemos
+ insertar el nuevo registro.
+\layout Standard
+
+Las consultas se realizan a través de una estructura INDEX_DAT que posee:
+\layout Itemize
+
+Clave
+\layout Itemize
+
+Número de Bloque
+\layout Standard
+
+Esta estructura se encuentra en el archivo
+\family typewriter
+indice_bplus.h
+\layout Standard
+
+El modo de uso es el siguiente:
+\layout Standard
+
+En primer lugar se carga la clave a insertar en el campo Clave, y en el
+ campo Número de Bloque se almacena un número de bloque válido, mas adelante
+ se explica el por qué.
+\layout Standard
+
+Luego se invoca a la función
+\family typewriter
+int emufs_b_plus_get_bloque(INDICE, INDEX_DAT)
+\family default
+la cual recibe como parámetro una estructura de índice y un INDEX_DAT para
+ realizar la consulta.
+\layout Standard
+
+Esta función recorre recursivamente el árbol y busca una clave mayor inmediata
+ a la enviada, siempre culminando la búsqueda en una hoja.
+ Al encontrar la clave mayor inmediata, el resultado de la búsqueda será
+ la clave anterior en el nodo, pues cada clave en el nodo es un ancla de
+ bloque de datos, de esta manera la clave anterior será menor a la clave
+ enviada, pues las claves en las hojas estan ordenadas.
+
+\layout Standard
+
+En este paso pueden suceder dos cosas:
+\layout Enumerate
+
+Que exista una clave menor a la enviada.
+\layout Enumerate
+
+Que la clave enviada sea menor a todas las claves del árbol.
+\layout Standard
+
+En el primer caso, se ha encontrado la clave y se carga la estructura con
+ el hijo de esa clave, que será el número de bloque donde debe insertarse
+ el nuevo registro (por el cual se realizó la consulta), sobreescribiendo
+ el valor que almacenaba al ingresar, y la función retornará código 0 que
+ indica que se ha encontrado un bloque donde insertar.
+\layout Standard
-Ordenamiento externo
+En el segundo caso, puede darse que la clave enviada sea menor a todas las
+ claves del árbol, por lo cual no es posible encontrar un ancla de bloque
+ para esa clave.
+ Aquí la función retornará código -1 lo cual indica que no se ha encontrado
+ un bloque donde insertar el registro nuevo, y es por esto que la estructura
+ debe inicializarse con un número de bloque válido antes de realizarse la
+ consulta.
\the_end
projects / z.facultad / 75.06 / emufs.git / commitdiff