\emph default
es la estructura principal que encapsula todas las funciones para el manejo
de un índice.
- Posee punteros a funciones que permite utilizar la misma interface para
+ Posee punteros a funciones que permite utilizar la misma interfaz para
distintas implementaciones de árboles.
\layout Standard
Indice B*
\layout Subsection
-Desiciones de diseño
+Decisiones de diseño
\layout Standard
-Una de las pocas desiciones que tuvimos que tomar fue la forma de manejar
+Una de las pocas decisiones que tuvimos que tomar fue la forma de manejar
el nodo raíz.
Hay dos formas comunes de hacerlo:
\layout Enumerate
El problema que encontramos para hacerlo de esa forma fue que usamos un
tamaño de nodo fijo de 512 para poder leer un sector completo del disco
y ganar algo de velocidad, por lo que para poder mantener este esquema
- hubieramos necesitado de 3 bloques de 512 para poder guardar los 2N+1 claves,
+ hubiéramos necesitado de 3 bloques de 512 para poder guardar los 2N+1 claves,
desperdiciando 512-tamaño_de_clave espacio en el bloque final y haciendo
que cualquier ahorro de espacio en los hijos del nodo raíz difícilmente
lo compense.
\layout Standard
-Ademas de esto, el utilizar la segunda forma trae como ventaja la reutilización
+Además de esto, el utilizar la segunda forma trae como ventaja la reutilización
de código del árbol B, lo que facilita la implementación y el mantenimiento
del código.
\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
+ árbol 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
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.
+ enviada, pues las claves en las hojas están ordenadas.
\layout Standard
El algoritmo de ordenamiento es completamente genérico, ya que recibe un
puntero void como registro, su tamaño (para poder manipularlo sin conocer
su tipo) y una función de comparación, para poder comparar dos registros
- (sin saber su tipo) a través de una relación de órden (descripta por dicha
+ (sin saber su tipo) a través de una relación de orden (descripta por dicha
función).
\layout Section
-Desiciones de diseño.
+Decisiones de diseño.
\layout Standard
El algoritmo se eligió en base a una serie de razones y cuenta con una serie
El buffer ordenado se implementó con un árbol binario debido a que tiene
una buena relación entre velocidad de búsqueda y facilidad de implementación.
Al ser el principal determinante de la velocidad los accesos a disco no
- se creyo necesario buscar una alternativa más rapida para mantener el buffer
+ se creyó necesario buscar una alternativa más rápida para mantener el buffer
ordenado en memoria, ya que no cambiaría de forma notable el tiempo total
del algoritmo.
Otras posibilidades hubieran sido cargar todo el buffer en memoria y ordenarlo