src/btree.h

   1
   2 #ifndef _B_TREE_H
   3 #define _B_TREE_H
   4
   5 /**
   6  *  La estructura general del archivo seria :
   7  *   +----------+----------+----------+-----+----------+
   8  *   |FileHeader| Bloque 0 | Bloque 1 | ... | Bloque N |
   9  *   +----------+----------+----------+-----+----------+
  10  *
  11  * Cada bloque tiene su propio encabezado siguiendo la siguiente
  12  * estructura :
  13  *   +--------------+-----------------------------------+
  14  *   | BloqueHeader | Area de Claves                    |
  15  *   +--------------+-----------------------------------+
  16  *
  17  * El area de claves depende del tipo de arbol (INDICE o EXAHUSTIVO)
  18  * y del tipo de clave (Longitud fija o variable).
  19  *
  20  * Los nodos que "hojas" (es decir, aquellos que no tienen hijos) no
  21  * tienen "punteros", por lo que el area de datos seria algo como :
  22  *  +--------------+--------------+--------------+--------------+
  23  *  | clave1,dato1 | clave2,dato2 | ............ | claveN,datoN |
  24  *  +--------------+--------------+--------------+--------------+
  25  *
  26  * Ahora, los bloques intermedios tienen punteros a los hijos, y
  27  * quedaria algo como :
  28  *  +---------+----------------------+-------+----------------------+
  29  *  | HijoIzq | clave1,dato1,HijoDer | ..... | claveN,datoN,HijoDer |
  30  *  +---------+----------------------+-------+----------------------+
  31  *
  32  * El tamaño de la clave es variable, por lo que la cantidad de claves
  33  * que puede almacenar se basa en la cantidad de espacio libre.
  34  *
  35  * Para saber si hay que romper en dos un nodo, se debe ver si la clave
  36  * a agregar entra en el espacio libre del nodo encontrado como "lugar
  37  * de insercion". Ahora, un problema a resolver es cuando se debe
  38  * juntar nodos, ya que el arbol B este es particular (Preguntar a Cerveto?).
  39  *
  40  *
  41  * TODO :
  42  *  * Ver como manejar las claves de manera transparente a las APIs de
  43  *    agregar y de borrar (EMUFS lo solucionaba bastante bien, se puede
  44  *    tomar una idea simimar)
  45  */
  46
  47 #include <iostream>
  48 #include <string>
  49 #include <list>
  50 #include "common.h"
  51 #include "clave.h"
  52 #include "clave_fija.h"
  53 #include "clave_variable.h"
  54 #include "btree_data.h"
  55
  56 /* alias para codear menos :) */
  57
  58 /** Encabezado del archivo BTree
  59  *
  60  *  Esta estructura es para comodidad de manejo, aunque en disco
  61  *  ocupe block_size de tamaño.
  62  */
  63 struct BTreeFileHeader {
  64         uint block_size;
  65 };
  66
  67 /** Encabezado de un bloque */
  68 struct BTreeNodeHeader {
  69         /** Indica a que nivel corresponde un bloque
  70          *
  71          *  nivel == 0 : una hoja
  72          *  nivel != 0 : nodo intermedio
  73          */
  74         unsigned short level;
  75
  76         /** Espacio libre en el bloque
  77          *
  78          *  El nodo empieza con free_space = block_size - sizeof (BTreeHeader)
  79          */
  80         unsigned int free_space;
  81
  82         /** Cantidad de elementos en el nodo */
  83         unsigned int item_count;
  84 };
  85
  86 /** Modelo del árbol B
  87  *
  88  *  \param filename Nombre del archivo a crear
  89  *  \param block_size Tamaño de bloque a utilizar
  90  *  \param k_t Tipo de clave a utilizar
  91  *  \return Un nuevo arbol B creado o NULL en caso de error
  92  */
  93 class BTree {
  94         public:
  95                 BTree (const std::string &filename, unsigned int block_size, int k_t = KEY_FIXED, bool create_new_file = false);
  96                 ~BTree ();
  97
  98                 /** Tipos de clave a usar */
  99                 enum {
 100                         KEY_FIXED,
 101                         KEY_VARIABLE
 102                 };
 103
 104                 /** Agrega una nueva clave al árbol. */
 105                 void AddKey (const Clave &k);
 106                 /** Elimina una clave del árbol. */
 107                 void DelKey (const Clave &k);
 108                 /** Busca si existe una clave en el árbol
 109                  *
 110                  * \TODO : Deberia retornar algun tipo de dato
 111                  */
 112                 bool FindKey (const Clave &k);
 113
 114         protected:
 115                 Clave* AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
 116                 Clave* AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
 117                 Clave* AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
 118                 bool FindKeyR (const Clave *k, uint node);
 119
 120                 void WriteFileHeader ();
 121
 122                 void WriteBlock (uchar *block, uint num);
 123                 uchar *ReadBlock (uint num);
 124                 uchar *NewBlock (uint &num);
 125
 126                 void ReadNodoHeader (uchar *node, BTreeNodeHeader *header);
 127                 void WriteNodoHeader (uchar *node, BTreeNodeHeader *header);
 128
 129                 std::list<BTreeData *> ReadKeys (uchar *node, BTreeNodeHeader &node_header);
 130                 void WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list<BTreeData *> &keys);
 131
 132                 void DeleteKeys (std::list<BTreeData *> &keys);
 133
 134                 std::string filename;
 135                 BTreeFileHeader header;
 136                 int key_type;
 137
 138                 /** Apunta al archivo de datos, asi se abre solo 1 vez
 139                  *
 140                  *  \TODO Ver si vale la pena
 141                  */
 142                 FILE *fp;
 143
 144
 145                 /* DEBUG */
 146                 void PrintNode (uint num);
 147 };
 148
 149 #endif // _B_TREE_H
 150