tagged 1.0-pre2

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

diff --git a/src/btree.h b/src/btree.h
index 2d9ca6a204072cf4eb569b8013a099710773145c..6feb5a8e3b700026d9d5bdafaadc97f073c5f5a9 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
  *
  * 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
  *
  *
  * \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.
  *
  * 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.
  * \subsection page_model_find Búsqueda de una Clave.
  *
  * Esta operación se realiza haciendo una búsqueda en profundidad en el árbol.


@@ -193,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 */


@@ -232,6 +249,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);
 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 */
                ~BTree ();
 
                /** Tipos de clave a usar */


@@ -277,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);


@@ -298,14 +318,13 @@ class BTree {
 
                std::string filename;
                BTreeFileHeader header;
 
                std::string filename;
                BTreeFileHeader header;

-               int key_type;
-               int tree_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 */