Marco TODOs

[z.facultad/75.52/treemulator.git] / src / btree.h

diff --git a/src/btree.h b/src/btree.h
index 61fbb8c36592695a965153e462816dd0d72120aa..6feb5a8e3b700026d9d5bdafaadc97f073c5f5a9 100644 (file)
--- a/src/btree.h
+++ b/src/btree.h
@@ -4,6 +4,33 @@
 
 /** \page page_btree Árbol B
  * 
 
 /** \page page_btree Árbol B
  * 

+ * \section page_model_class Estructura del árbol en memoria.
+ *
+ * La organización de las clases utilizadas es la siguiente :
+ * 
+ * \image html clases.png
+ * \image latex clases.eps "Diagrama de Clases" width=10cm
+ * 
+ * Para operar con un determinado nodo en memoria, lo que se hace es lo siguiente.
+ * Como primer paso se carga el bloque en memoria llamando a ReadBlock y se lee de él 
+ * su encabezado utilizando una llamada a BTree::ReadNodeHeader, que almacena los datos
+ * en una clase BTreeNodeHeader. A continuación se leen las claves, todavía en formato
+ * RAW, y se genera una lista con instancias de BTreeData. Esta lista es generada
+ * con la llamada a BTree::ReadKeys.
+ *
+ * La operación de búsqueda o inserción se realiza en memoria sobre la lista cargada
+ * anteriormente. Cuando se está listo para guardar todo de nuevo en disco se opera
+ * como se explica a continuación.
+ *
+ * Como primer paso se escriben las claves de la lista nuevamente en el bloque en
+ * memoria en formato RAW, para ello se utilizar WriteKeys, que además de pasar
+ * las claves a formato RAW, también actualiza los datos del header (espacio libre
+ * y cantidad de ítems). Luego se escribe el header en formato RAW con BTree::WriteNodeHeader
+ * y por último se baja a disco el bloque con WriteBlock.
+ *
+ * Para liberar la memoria utilizada solo basta llamar a BTree::DeleteKeys y liberar
+ * el bloque RAW utilizado para el nodo.
+ *

  * \section page_model_estructura Estructura del árbol en disco.
  *
  *  La estructura del archivo donde se almacena el árbol es una secuencia
  * \section page_model_estructura Estructura del árbol en disco.
  *
  *  La estructura del archivo donde se almacena el árbol es una secuencia


@@ -22,15 +49,15 @@
  * estructura :
  *   <pre>
  *   +--------------+-----------------------------------+
  * estructura :
  *   <pre>
  *   +--------------+-----------------------------------+

- *   | BloqueHeader | Area de Claves                    |
+ *   | BloqueHeader | Área de Claves                    |

  *   +--------------+-----------------------------------+
  *   </pre>
  *
  *   +--------------+-----------------------------------+
  *   </pre>
  *

- * El area de claves depende del tipo de arbol (INDICE o EXAHUSTIVO)
+ * El área de claves depende del tipo de árbol (IDENTIFICACION o CLASIFICACION)

  * y del tipo de Clave (ClaveFija o ClaveVariable).
  *
  * Los nodos que son "hojas" (es decir, aquellos que no tienen hijos) no
  * y del tipo de Clave (ClaveFija o ClaveVariable).
  *
  * Los nodos que son "hojas" (es decir, aquellos que no tienen hijos) no

- * tienen "punteros", por lo que el area de datos seria algo como :
+ * tienen "punteros", por lo que el área de datos seria algo como :

  *  <pre>
  *  +--------------+--------------+--------------+--------------+
  *  | clave1,dato1 | clave2,dato2 | ............ | claveN,datoN |
  *  <pre>
  *  +--------------+--------------+--------------+--------------+
  *  | clave1,dato1 | clave2,dato2 | ............ | claveN,datoN |


@@ -40,14 +67,14 @@
  * El par (claveN,datoN) es representado por la clase BTreeLeafData.
  *
  * Ahora, los bloques intermedios tienen punteros a los hijos, y 
  * El par (claveN,datoN) es representado por la clase BTreeLeafData.
  *
  * Ahora, los bloques intermedios tienen punteros a los hijos, y 

- * quedaria algo como :
+ * quedaría algo como :

  *  <pre>
  *  +---------+----------------------+-------+----------------------+
  *  | HijoIzq | clave1,dato1,HijoDer | ..... | claveN,datoN,HijoDer |
  *  +---------+----------------------+-------+----------------------+
  *  </pre>
  *
  *  <pre>
  *  +---------+----------------------+-------+----------------------+
  *  | HijoIzq | clave1,dato1,HijoDer | ..... | claveN,datoN,HijoDer |
  *  +---------+----------------------+-------+----------------------+
  *  </pre>
  *

- * El puntore HijoIzq es representado en memoria por la clase BTreeChildData, y
+ * El puntero HijoIzq es representado en memoria por la clase BTreeChildData, y

  * el resto por BTreeData.
  *
  * El tamaño de la clave es variable, por lo que la cantidad de claves
  * el resto por BTreeData.
  *
  * El tamaño de la clave es variable, por lo que la cantidad de claves


@@ -55,14 +82,111 @@
  *
  * Para saber si hay que romper en dos un nodo, se debe ver si la clave
  * a agregar entra en el espacio libre del nodo encontrado como "lugar
  *
  * Para saber si hay que romper en dos un nodo, se debe ver si la clave
  * a agregar entra en el espacio libre del nodo encontrado como "lugar

- * de insercion". Ahora, un problema a resolver es cuando se debe
- * juntar nodos, ya que el arbol B este es particular (Preguntar a Cerveto?).
+ * de inserción".
+ *
+ * \section page_model_op Operaciones Básicas
+ *
+ * En esta sección explicaremos como se realizan las diferentes operaciones
+ * sobre el árbol.
+ *
+ * \subsection page_model_add Agregar una Clave.
+ *
+ * Agregar una clave al árbol es relativamente fácil ya que siempre se agregan
+ * en las hojas.
+ *
+ * El algoritmo comienza a recorrer la raíz buscando la clave inmediatamente
+ * superior (llamada clave de corte) a la que deseamos agregar. Si la raíz es una hoja, la clave es
+ * agregada antes de la clave que corta el algoritmo.
+ *
+ * Si la raíz no es una hoja, se llama recursivamente yendo al nodo hijo de
+ * la clave anterior a la clave de corte, hasta llegar a una hoja y finalmente
+ * agregar la clave.
+ *
+ * En este punto pueden pasar dos cosas. La primera es que la clave entre en el 
+ * lugar libre que le queda al nodo, entonces es agregada y retorna liberando
+ * todo lo que quedó pendiente.
+ *
+ * La segunda situación es que la clave no entre y el nodo deba ser separado
+ * en dos. Cuando esto sucede se crea una lista temporal ordenada con las
+ * claves del nodo a partir y la nueva clave a agregar.
+ * 
+ * La primer mitad se guarda en un nodo, la clave del medio se deja para retornar
+ * al padre y la segunda mitad se pone en un nuevo nodo. Luego de guardar todo
+ * se le retorna al padre una clave. Éste al detectar que un hijo manda una clave
+ * tratará de agregarla siguiendo el mismo procedimiento que el hijo (si no entra
+ * debe realizar un split), hasta llegar a la raíz.
+ *
+ * La única diferencia entre el split en una hoja y el resto de los nodos, es que 
+ * estos últimos hace uso de los datos "hijo izquierdo" e "hijo derecho" también
+ * pasados como parámetros luego del split, a fin de ajustar los punteros necesarios.
+ *
+ * \subsection page_model_del Eliminar una Clave.
+ *
+ * El proceso de eliminar una clave es un poco más complejo y cubre más situaciones
+ * particulares.
+ *
+ * El algoritmo se divide básicamente en 2 casos : eliminar de una hoja y eliminar
+ * de un nodo interno.

  *
  *

+ * Ambos algoritmos comienzan con una búsqueda en profundidad de la clave a borrar.
+ * en el momento de encontrarla se llama a BTree::DelKeyFromLeaf o BTree::DelKeyFromNode
+ * dependiendo del caso.
+ * 
+ * \subsubsection page_model_del_hoja Eliminar de una Hoja.
+ *
+ * Cuando la clave es encontrada en una hoja simplemente se elimina de la hoja.
+ *
+ * Luego debemos verificar que se cumpla la condición de que el nodo tenga al menos
+ * el 50% del espacio ocupado. Si esto no ocurre debemos actuar como se explica a
+ * continuación.
+ *
+ * Como primer intento pedimos prestada una clave a alguno nuestros hermanos. Si 
+ * alguno es capaz de pasar una clave, ésta última se reemplaza en el padre y la
+ * clave del padre para al nodo en cuestión. Esto se hace para mantener el ordenamiento
+ * del árbol intacto.
+ *
+ * Si ningún hermano me puede prestar, lo único que nos queda es unir dos nodos.
+ * La unión se realiza con cualquier nodo disponible, siempre preguntando primero
+ * por el derecho y si este no existe, se une con el izquierdo. Luego de unir se
+ * le notifica al padre y se ajustan los punteros correspondientes.
+ *
+ * \subsubsection page_model_del_nodo Eliminar de un Nodo.
+ *
+ * Cuando la clave a eliminar se encuentra en una hoja se debe tratar de forma
+ * especial. Lo primero que se hace es buscar en todo el árbol la clave
+ * inmediatamente superior. Esto se logra yendo al hijo derecho de la clave a borrar
+ * y luego siempre hacia el hijo izquierdo hasta llegar a una hoja.
+ *
+ * La primer clave de la hoja encontrada es reemplazada por la clave del padre y 
+ * se llama al borrar de una hoja. Como siempre la clave reemplazada en la hoja queda
+ * en primer lugar, no hay problemas que no esté ordenada al momento de llamar
+ * al algoritmo de borrado en una hoja. De acá en más todo sigue como fue descripto
+ * en el borrado en una hoja.
+ *
+ * \subsubsection page_model_problema El problema de la Clave Mayor.
+ *
+ * Este es un problema que hemos encontrado en la actual implementación de árbol
+ * B con claves variables.

  *
  *

- * \todo :
- *  * Ver como manejar las claves de manera transparente a las APIs de
- *    agregar y de borrar (EMUFS lo solucionaba bastante bien, se puede
- *    tomar una idea simimar)
+ * Este puede ocurrir únicamente cuando sucede una junta de nodos. Lo que ocurre
+ * se ejemplifica a continuación. Supongamos por un momento que tenemos dos
+ * nodos a unir cuya suma de tamaños ocupados es N. Ahora supongamos que la clave
+ * del padre, que debe ser unida con los nodos es de tamaño M.
+ *
+ * Si por algun caso particular de las claves N+M es mayor al tamaño del bloque,
+ * la junta no podrá ser realizada.
+ *
+ * Hemos detectado este problema seguido en árboles con bloques de 128 o 256, y muy
+ * rara vez en nodos de 512 o superiores, por lo que no hemos tomado medida alguna
+ * más que documentar su existencia.
+ * 
+ * \subsection page_model_find Búsqueda de una Clave.
+ *
+ * Esta operación se realiza haciendo una búsqueda en profundidad en el árbol.
+ * Si la clave es encontrada se retorna una estructura del tipo BTreeFindResult
+ * con toda la información útil.
+ *
+ * Si no se encuentra retorna NULL.

  */
 
 #include <iostream>
  */
 
 #include <iostream>


@@ -73,6 +197,7 @@
 #include "clave_fija.h"
 #include "clave_variable.h"
 #include "btree_data.h"
 #include "clave_fija.h"
 #include "clave_variable.h"
 #include "btree_data.h"

+#include "exception.h"

 
 /* alias para codear menos :) */
 
 
 /* alias para codear menos :) */
 


@@ -83,6 +208,8 @@
  */
 struct BTreeFileHeader {
        uint block_size;
  */
 struct BTreeFileHeader {
        uint block_size;

+       int tree_type;
+       int key_type;

 };
 
 /** Encabezado de un bloque */
 };
 
 /** Encabezado de un bloque */


@@ -121,7 +248,9 @@ struct BTreeFindResult {
  */
 class BTree {
        public:
  */
 class BTree {
        public:

-               BTree (const std::string &filename, unsigned int block_size, int k_t = KEY_FIXED, bool create_new_file = false);
+               BTree (const std::string &filename, unsigned int block_size, int t_t = TYPE_IDENTIFICACION, int k_t = KEY_FIXED, bool create_new_file = false);
+               BTree (const std::string &filename);
+

                ~BTree ();
 
                /** Tipos de clave a usar */
                ~BTree ();
 
                /** Tipos de clave a usar */


@@ -130,6 +259,11 @@ class BTree {
                        KEY_VARIABLE  /**< Utilización de clave de longitud variable */
                };
 
                        KEY_VARIABLE  /**< Utilización de clave de longitud variable */
                };
 

+               enum {
+                       TYPE_IDENTIFICACION,
+                       TYPE_CLASIFICACION
+               };
+       

                /** Agrega una nueva clave al árbol. */
                void AddKey (const Clave &k);
                /** Elimina una clave del árbol. */
                /** Agrega una nueva clave al árbol. */
                void AddKey (const Clave &k);
                /** Elimina una clave del árbol. */


@@ -140,6 +274,8 @@ class BTree {
                 */
                BTreeFindResult *FindKey (const Clave &k);
 
                 */
                BTreeFindResult *FindKey (const Clave &k);
 

+               int type() const;
+

        //protected:
                /* Funciones de Alta */
                Clave* AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
        //protected:
                /* Funciones de Alta */
                Clave* AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child);


@@ -160,6 +296,7 @@ class BTree {
 
                /* Funciones de manejo de archivo */
                void WriteFileHeader ();
 
                /* Funciones de manejo de archivo */
                void WriteFileHeader ();

+               void ReadFileHeader ();

 
                /* Manejo de Bloques */
                void WriteBlock (uchar *block, uint num);
 
                /* Manejo de Bloques */
                void WriteBlock (uchar *block, uint num);


@@ -175,15 +312,19 @@ class BTree {
                void WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list<BTreeData *> &keys);
                void DeleteKeys (std::list<BTreeData *> &keys);
 
                void WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list<BTreeData *> &keys);
                void DeleteKeys (std::list<BTreeData *> &keys);
 

+               /* Abreviacion de Claves */
+               void AbrevKey (std::list<BTreeData *> &lst);
+               void DeAbrevKey (std::list<BTreeData *> &lst);
+

                std::string filename;
                BTreeFileHeader header;
                std::string filename;
                BTreeFileHeader header;

-               int key_type;

 
                /** Apunta al archivo de datos, asi se abre solo 1 vez
                 *
                 *  \todo Ver si vale la pena
                 */
                FILE *fp;
 
                /** Apunta al archivo de datos, asi se abre solo 1 vez
                 *
                 *  \todo Ver si vale la pena
                 */
                FILE *fp;

+               std::list<uint> deleted_nodes;

 
 
                /* DEBUG */
 
 
                /* DEBUG */