src/btree.h

   1
   2 #ifndef _B_TREE_H
   3 #define _B_TREE_H
   4
   5 /** \page page_btree Árbol B
   6  *
   7  * \section page_model_estructura Estructura del árbol en disco.
   8  *
   9  *  La estructura del archivo donde se almacena el árbol es una secuencia
  10  *  de bloques de tamaño fijo parametrizable. Cada bloque representa un nodo
  11  *  del árbol, exceptuando el bloque 0 que corresponde al encabezado donde se
  12  *  guardan los parámetros del árbol.
  13  *
  14  *  <pre>
  15  *     Bloque 0   Bloque 1   Bloque 2         Bloque N
  16  *   +----------+----------+----------+-----+----------+
  17  *   |FileHeader|  Nodo  0 |  Nodo  1 | ... | Nodo N-1 |
  18  *   +----------+----------+----------+-----+----------+
  19  *  </pre>
  20  *
  21  * Cada bloque tiene su propio encabezado siguiendo la siguiente
  22  * estructura :
  23  *   <pre>
  24  *   +--------------+-----------------------------------+
  25  *   | BloqueHeader | Area de Claves                    |
  26  *   +--------------+-----------------------------------+
  27  *   </pre>
  28  *
  29  * El area de claves depende del tipo de arbol (INDICE o EXAHUSTIVO)
  30  * y del tipo de Clave (ClaveFija o ClaveVariable).
  31  *
  32  * Los nodos que son "hojas" (es decir, aquellos que no tienen hijos) no
  33  * tienen "punteros", por lo que el area de datos seria algo como :
  34  *  <pre>
  35  *  +--------------+--------------+--------------+--------------+
  36  *  | clave1,dato1 | clave2,dato2 | ............ | claveN,datoN |
  37  *  +--------------+--------------+--------------+--------------+
  38  *  </pre>
  39  *
  40  * El par (claveN,datoN) es representado por la clase BTreeLeafData.
  41  *
  42  * Ahora, los bloques intermedios tienen punteros a los hijos, y
  43  * quedaria algo como :
  44  *  <pre>
  45  *  +---------+----------------------+-------+----------------------+
  46  *  | HijoIzq | clave1,dato1,HijoDer | ..... | claveN,datoN,HijoDer |
  47  *  +---------+----------------------+-------+----------------------+
  48  *  </pre>
  49  *
  50  * El puntore HijoIzq es representado en memoria por la clase BTreeChildData, y
  51  * el resto por BTreeData.
  52  *
  53  * El tamaño de la clave es variable, por lo que la cantidad de claves
  54  * que puede almacenar se basa en la cantidad de espacio libre.
  55  *
  56  * Para saber si hay que romper en dos un nodo, se debe ver si la clave
  57  * a agregar entra en el espacio libre del nodo encontrado como "lugar
  58  * de insercion". Ahora, un problema a resolver es cuando se debe
  59  * juntar nodos, ya que el arbol B este es particular (Preguntar a Cerveto?).
  60  *
  61  *
  62  * \todo :
  63  *  * Ver como manejar las claves de manera transparente a las APIs de
  64  *    agregar y de borrar (EMUFS lo solucionaba bastante bien, se puede
  65  *    tomar una idea simimar)
  66  */
  67
  68 #include <iostream>
  69 #include <string>
  70 #include <list>
  71 #include "common.h"
  72 #include "clave.h"
  73 #include "clave_fija.h"
  74 #include "clave_variable.h"
  75 #include "btree_data.h"
  76 #include "exception.h"
  77
  78 /* alias para codear menos :) */
  79
  80 /** Encabezado del archivo BTree
  81  *
  82  *  Esta estructura es para comodidad de manejo, aunque en disco
  83  *  ocupe block_size de tamaño.
  84  */
  85 struct BTreeFileHeader {
  86         uint block_size;
  87 };
  88
  89 /** Encabezado de un bloque */
  90 struct BTreeNodeHeader {
  91         /** Indica a que nivel corresponde un bloque
  92          *
  93          *  nivel == 0 : una hoja
  94          *  nivel != 0 : nodo intermedio
  95          */
  96         unsigned short level;
  97
  98         /** Espacio libre en el bloque
  99          *
 100          *  El nodo empieza con free_space = block_size - sizeof (BTreeHeader)
 101          */
 102         unsigned int free_space;
 103
 104         /** Cantidad de elementos en el nodo */
 105         unsigned int item_count;
 106 };
 107
 108 /** Resultado de la búsqueda de una clave */
 109 struct BTreeFindResult {
 110         /** Número de nodo que contiene la clave buscada. */
 111         uint node;
 112         /** Encabezado del nodo que contiene la clave. */
 113         BTreeNodeHeader header;
 114 };
 115
 116 /** Modelo del árbol B
 117  *
 118  *  \param filename Nombre del archivo a crear
 119  *  \param block_size Tamaño de bloque a utilizar
 120  *  \param k_t Tipo de clave a utilizar
 121  *  \return Un nuevo arbol B creado o NULL en caso de error
 122  */
 123 class BTree {
 124         public:
 125                 BTree (const std::string &filename, unsigned int block_size, int t_t = TYPE_UNIQUE, int k_t = KEY_FIXED, bool create_new_file = false);
 126                 ~BTree ();
 127
 128                 /** Tipos de clave a usar */
 129                 enum {
 130                         KEY_FIXED,    /**< Utilización de clave de longitud fija */
 131                         KEY_VARIABLE  /**< Utilización de clave de longitud variable */
 132                 };
 133
 134                 enum {
 135                         TYPE_UNIQUE,
 136                         TYPE_SELECTIVE
 137                 };
 138
 139                 /** Agrega una nueva clave al árbol. */
 140                 void AddKey (const Clave &k);
 141                 /** Elimina una clave del árbol. */
 142                 void DelKey (const Clave &k);
 143                 /** Busca si existe una clave en el árbol
 144                  *
 145                  * \return Un BTreeFindResult que el usuario debe liberar.
 146                  */
 147                 BTreeFindResult *FindKey (const Clave &k);
 148
 149         //protected:
 150                 /* Funciones de Alta */
 151                 Clave* AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
 152                 Clave* AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
 153                 Clave* AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
 154
 155                 /* Funciones de Baja */
 156                 void DelKeyR (BTreeData *k, uint node, uint padre);
 157                 void DelKeyFromLeaf (Clave *k, uint node_num, uint padre);
 158                 void DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint right);
 159                 void FindBrothers (uint node_num, uint padre, uint &left, uint &right);
 160                 Clave *ReplaceKeyInFather (uint node_num, uint padre, Clave *k);
 161                 Clave *GetKey (uint node_num, char maxmin);
 162                 void JoinNodes (uint node1, uint node2, uint padre, int);
 163
 164                 /* Funciones de Búsqueda */
 165                 BTreeFindResult *FindKeyR (const Clave *k, uint node);
 166
 167                 /* Funciones de manejo de archivo */
 168                 void WriteFileHeader ();
 169
 170                 /* Manejo de Bloques */
 171                 void WriteBlock (uchar *block, uint num);
 172                 uchar *ReadBlock (uint num);
 173                 uchar *NewBlock (uint &num);
 174
 175                 /* Manejo de headers */
 176                 void ReadNodoHeader (uchar *node, BTreeNodeHeader *header);
 177                 void WriteNodoHeader (uchar *node, BTreeNodeHeader *header);
 178
 179                 /* Manejo de claves en memoria */
 180                 std::list<BTreeData *> ReadKeys (uchar *node, BTreeNodeHeader &node_header);
 181                 void WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list<BTreeData *> &keys);
 182                 void DeleteKeys (std::list<BTreeData *> &keys);
 183
 184                 /* Abreviacion de Claves */
 185                 void AbrevKey (std::list<BTreeData *> &lst);
 186                 void DeAbrevKey (std::list<BTreeData *> &lst);
 187
 188                 std::string filename;
 189                 BTreeFileHeader header;
 190                 int key_type;
 191                 int tree_type;
 192
 193                 /** Apunta al archivo de datos, asi se abre solo 1 vez
 194                  *
 195                  *  \todo Ver si vale la pena
 196                  */
 197                 FILE *fp;
 198
 199
 200                 /* DEBUG */
 201         public:
 202                 void PrintNode (uint num);
 203 };
 204
 205 #endif // _B_TREE_H
 206