tagged 1.1

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

diff --git a/src/btree.h b/src/btree.h
index 2d9ca6a204072cf4eb569b8013a099710773145c..9e492139317a15351162c43f5c3637fc42a767cf 100644 (file)
--- a/src/btree.h
+++ b/src/btree.h
@@ -82,9 +82,7 @@
  *
  * 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 inserción". Ahora, un problema a resolver es cuando se debe
- * juntar nodos, ya que el árbol B este es particular <b>(Preguntar a
- * Cerveto?)</b>.
+ * de inserción".
  *
  * \section page_model_op Operaciones Básicas
  *
@@ -165,6 +163,23 @@
  * 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.
+ *
+ * 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.
@@ -192,7 +207,11 @@
  *  ocupe block_size de tamaño.
  */
 struct BTreeFileHeader {
+       char magic[7];
        uint block_size;
+       int tree_type;
+       int key_type;
+       uint block_data_counter;
 };
 
 /** Encabezado de un bloque */
@@ -232,6 +251,8 @@ struct BTreeFindResult {
 class BTree {
        public:
                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 */
@@ -277,6 +298,7 @@ class BTree {
 
                /* Funciones de manejo de archivo */
                void WriteFileHeader ();
+               void ReadFileHeader ();
 
                /* Manejo de Bloques */
                void WriteBlock (uchar *block, uint num);
@@ -298,14 +320,16 @@ class BTree {
 
                std::string filename;
                BTreeFileHeader header;
-               int key_type;
-               int tree_type;
+
+               uint GetNextBlockData ();
 
                /** Apunta al archivo de datos, asi se abre solo 1 vez
                 *
                 *  \todo Ver si vale la pena
                 */
                FILE *fp;
+               std::list<uint> deleted_nodes;
+               std::list<uint> deleted_block_data;
 
 
                /* DEBUG */