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_class Estructura del árbol en memoria.
   8  *
   9  * La organización de las clases utilizadas es la siguiente :
  10  *
  11  * \image html clases.png
  12  * \image latex clases.eps "Diagrama de Clases" width=10cm
  13  *
  14  * Para operar con un determinado nodo en memoria, lo que se hace es lo siguiente.
  15  * Como primer paso se carga el bloque en memoria llamando a ReadBlock y se lee de él
  16  * su encabezado utilizando una llamada a BTree::ReadNodeHeader, que almacena los datos
  17  * en una clase BTreeNodeHeader. A continuación se leen las claves, todavía en formato
  18  * RAW, y se genera una lista con instancias de BTreeData. Esta lista es generada
  19  * con la llamada a BTree::ReadKeys.
  20  *
  21  * La operación de búsqueda o inserción se realiza en memoria sobre la lista cargada
  22  * anteriormente. Cuando se está listo para guardar todo de nuevo en disco se opera
  23  * como se explica a continuación.
  24  *
  25  * Como primer paso se escriben las claves de la lista nuevamente en el bloque en
  26  * memoria en formato RAW, para ello se utilizar WriteKeys, que además de pasar
  27  * las claves a formato RAW, también actualiza los datos del header (espacio libre
  28  * y cantidad de ítems). Luego se escribe el header en formato RAW con BTree::WriteNodeHeader
  29  * y por último se baja a disco el bloque con WriteBlock.
  30  *
  31  * Para liberar la memoria utilizada solo basta llamar a BTree::DeleteKeys y liberar
  32  * el bloque RAW utilizado para el nodo.
  33  *
  34  * \section page_model_estructura Estructura del árbol en disco.
  35  *
  36  *  La estructura del archivo donde se almacena el árbol es una secuencia
  37  *  de bloques de tamaño fijo parametrizable. Cada bloque representa un nodo
  38  *  del árbol, exceptuando el bloque 0 que corresponde al encabezado donde se
  39  *  guardan los parámetros del árbol.
  40  *
  41  *  <pre>
  42  *     Bloque 0   Bloque 1   Bloque 2         Bloque N
  43  *   +----------+----------+----------+-----+----------+
  44  *   |FileHeader|  Nodo  0 |  Nodo  1 | ... | Nodo N-1 |
  45  *   +----------+----------+----------+-----+----------+
  46  *  </pre>
  47  *
  48  * Cada bloque tiene su propio encabezado siguiendo la siguiente
  49  * estructura :
  50  *   <pre>
  51  *   +--------------+-----------------------------------+
  52  *   | BloqueHeader | Área de Claves                    |
  53  *   +--------------+-----------------------------------+
  54  *   </pre>
  55  *
  56  * El área de claves depende del tipo de árbol (IDENTIFICACION o CLASIFICACION)
  57  * y del tipo de Clave (ClaveFija o ClaveVariable).
  58  *
  59  * Los nodos que son "hojas" (es decir, aquellos que no tienen hijos) no
  60  * tienen "punteros", por lo que el área de datos seria algo como :
  61  *  <pre>
  62  *  +--------------+--------------+--------------+--------------+
  63  *  | clave1,dato1 | clave2,dato2 | ............ | claveN,datoN |
  64  *  +--------------+--------------+--------------+--------------+
  65  *  </pre>
  66  *
  67  * El par (claveN,datoN) es representado por la clase BTreeLeafData.
  68  *
  69  * Ahora, los bloques intermedios tienen punteros a los hijos, y
  70  * quedaría algo como :
  71  *  <pre>
  72  *  +---------+----------------------+-------+----------------------+
  73  *  | HijoIzq | clave1,dato1,HijoDer | ..... | claveN,datoN,HijoDer |
  74  *  +---------+----------------------+-------+----------------------+
  75  *  </pre>
  76  *
  77  * El puntero HijoIzq es representado en memoria por la clase BTreeChildData, y
  78  * el resto por BTreeData.
  79  *
  80  * El tamaño de la clave es variable, por lo que la cantidad de claves
  81  * que puede almacenar se basa en la cantidad de espacio libre.
  82  *
  83  * Para saber si hay que romper en dos un nodo, se debe ver si la clave
  84  * a agregar entra en el espacio libre del nodo encontrado como "lugar
  85  * de inserción".
  86  *
  87  * \section page_model_op Operaciones Básicas
  88  *
  89  * En esta sección explicaremos como se realizan las diferentes operaciones
  90  * sobre el árbol.
  91  *
  92  * \subsection page_model_add Agregar una Clave.
  93  *
  94  * Agregar una clave al árbol es relativamente fácil ya que siempre se agregan
  95  * en las hojas.
  96  *
  97  * El algoritmo comienza a recorrer la raíz buscando la clave inmediatamente
  98  * superior (llamada clave de corte) a la que deseamos agregar. Si la raíz es una hoja, la clave es
  99  * agregada antes de la clave que corta el algoritmo.
 100  *
 101  * Si la raíz no es una hoja, se llama recursivamente yendo al nodo hijo de
 102  * la clave anterior a la clave de corte, hasta llegar a una hoja y finalmente
 103  * agregar la clave.
 104  *
 105  * En este punto pueden pasar dos cosas. La primera es que la clave entre en el
 106  * lugar libre que le queda al nodo, entonces es agregada y retorna liberando
 107  * todo lo que quedó pendiente.
 108  *
 109  * La segunda situación es que la clave no entre y el nodo deba ser separado
 110  * en dos. Cuando esto sucede se crea una lista temporal ordenada con las
 111  * claves del nodo a partir y la nueva clave a agregar.
 112  *
 113  * La primer mitad se guarda en un nodo, la clave del medio se deja para retornar
 114  * al padre y la segunda mitad se pone en un nuevo nodo. Luego de guardar todo
 115  * se le retorna al padre una clave. Éste al detectar que un hijo manda una clave
 116  * tratará de agregarla siguiendo el mismo procedimiento que el hijo (si no entra
 117  * debe realizar un split), hasta llegar a la raíz.
 118  *
 119  * La única diferencia entre el split en una hoja y el resto de los nodos, es que
 120  * estos últimos hace uso de los datos "hijo izquierdo" e "hijo derecho" también
 121  * pasados como parámetros luego del split, a fin de ajustar los punteros necesarios.
 122  *
 123  * \subsection page_model_del Eliminar una Clave.
 124  *
 125  * El proceso de eliminar una clave es un poco más complejo y cubre más situaciones
 126  * particulares.
 127  *
 128  * El algoritmo se divide básicamente en 2 casos : eliminar de una hoja y eliminar
 129  * de un nodo interno.
 130  *
 131  * Ambos algoritmos comienzan con una búsqueda en profundidad de la clave a borrar.
 132  * en el momento de encontrarla se llama a BTree::DelKeyFromLeaf o BTree::DelKeyFromNode
 133  * dependiendo del caso.
 134  *
 135  * \subsubsection page_model_del_hoja Eliminar de una Hoja.
 136  *
 137  * Cuando la clave es encontrada en una hoja simplemente se elimina de la hoja.
 138  *
 139  * Luego debemos verificar que se cumpla la condición de que el nodo tenga al menos
 140  * el 50% del espacio ocupado. Si esto no ocurre debemos actuar como se explica a
 141  * continuación.
 142  *
 143  * Como primer intento pedimos prestada una clave a alguno nuestros hermanos. Si
 144  * alguno es capaz de pasar una clave, ésta última se reemplaza en el padre y la
 145  * clave del padre para al nodo en cuestión. Esto se hace para mantener el ordenamiento
 146  * del árbol intacto.
 147  *
 148  * Si ningún hermano me puede prestar, lo único que nos queda es unir dos nodos.
 149  * La unión se realiza con cualquier nodo disponible, siempre preguntando primero
 150  * por el derecho y si este no existe, se une con el izquierdo. Luego de unir se
 151  * le notifica al padre y se ajustan los punteros correspondientes.
 152  *
 153  * \subsubsection page_model_del_nodo Eliminar de un Nodo.
 154  *
 155  * Cuando la clave a eliminar se encuentra en una hoja se debe tratar de forma
 156  * especial. Lo primero que se hace es buscar en todo el árbol la clave
 157  * inmediatamente superior. Esto se logra yendo al hijo derecho de la clave a borrar
 158  * y luego siempre hacia el hijo izquierdo hasta llegar a una hoja.
 159  *
 160  * La primer clave de la hoja encontrada es reemplazada por la clave del padre y
 161  * se llama al borrar de una hoja. Como siempre la clave reemplazada en la hoja queda
 162  * en primer lugar, no hay problemas que no esté ordenada al momento de llamar
 163  * al algoritmo de borrado en una hoja. De acá en más todo sigue como fue descripto
 164  * en el borrado en una hoja.
 165  *
 166  * \subsubsection page_model_problema El problema de la Clave Mayor.
 167  *
 168  * Este es un problema que hemos encontrado en la actual implementación de árbol
 169  * B con claves variables.
 170  *
 171  * Este puede ocurrir únicamente cuando sucede una junta de nodos. Lo que ocurre
 172  * se ejemplifica a continuación. Supongamos por un momento que tenemos dos
 173  * nodos a unir cuya suma de tamaños ocupados es N. Ahora supongamos que la clave
 174  * del padre, que debe ser unida con los nodos es de tamaño M.
 175  *
 176  * Si por algun caso particular de las claves N+M es mayor al tamaño del bloque,
 177  * la junta no podrá ser realizada.
 178  *
 179  * Hemos detectado este problema seguido en árboles con bloques de 128 o 256, y muy
 180  * rara vez en nodos de 512 o superiores, por lo que no hemos tomado medida alguna
 181  * más que documentar su existencia.
 182  *
 183  * \subsection page_model_find Búsqueda de una Clave.
 184  *
 185  * Esta operación se realiza haciendo una búsqueda en profundidad en el árbol.
 186  * Si la clave es encontrada se retorna una estructura del tipo BTreeFindResult
 187  * con toda la información útil.
 188  *
 189  * Si no se encuentra retorna NULL.
 190  */
 191
 192 #include <iostream>
 193 #include <string>
 194 #include <list>
 195 #include "common.h"
 196 #include "clave.h"
 197 #include "clave_fija.h"
 198 #include "clave_variable.h"
 199 #include "btree_data.h"
 200 #include "exception.h"
 201
 202 /* alias para codear menos :) */
 203
 204 /** Encabezado del archivo BTree
 205  *
 206  *  Esta estructura es para comodidad de manejo, aunque en disco
 207  *  ocupe block_size de tamaño.
 208  */
 209 struct BTreeFileHeader {
 210         uint block_size;
 211         int tree_type;
 212         int key_type;
 213 };
 214
 215 /** Encabezado de un bloque */
 216 struct BTreeNodeHeader {
 217         /** Indica a que nivel corresponde un bloque
 218          *
 219          *  nivel == 0 : una hoja
 220          *  nivel != 0 : nodo intermedio
 221          */
 222         unsigned short level;
 223
 224         /** Espacio libre en el bloque
 225          *
 226          *  El nodo empieza con free_space = block_size - sizeof (BTreeHeader)
 227          */
 228         unsigned int free_space;
 229
 230         /** Cantidad de elementos en el nodo */
 231         unsigned int item_count;
 232 };
 233
 234 /** Resultado de la búsqueda de una clave */
 235 struct BTreeFindResult {
 236         /** Número de nodo que contiene la clave buscada. */
 237         uint node;
 238         /** Encabezado del nodo que contiene la clave. */
 239         BTreeNodeHeader header;
 240 };
 241
 242 /** Modelo del árbol B
 243  *
 244  *  \param filename Nombre del archivo a crear
 245  *  \param block_size Tamaño de bloque a utilizar
 246  *  \param k_t Tipo de clave a utilizar
 247  *  \return Un nuevo arbol B creado o NULL en caso de error
 248  */
 249 class BTree {
 250         public:
 251                 BTree (const std::string &filename, unsigned int block_size, int t_t = TYPE_IDENTIFICACION, int k_t = KEY_FIXED, bool create_new_file = false);
 252                 ~BTree ();
 253
 254                 /** Tipos de clave a usar */
 255                 enum {
 256                         KEY_FIXED,    /**< Utilización de clave de longitud fija */
 257                         KEY_VARIABLE  /**< Utilización de clave de longitud variable */
 258                 };
 259
 260                 enum {
 261                         TYPE_IDENTIFICACION,
 262                         TYPE_CLASIFICACION
 263                 };
 264
 265                 /** Agrega una nueva clave al árbol. */
 266                 void AddKey (const Clave &k);
 267                 /** Elimina una clave del árbol. */
 268                 void DelKey (const Clave &k);
 269                 /** Busca si existe una clave en el árbol
 270                  *
 271                  * \return Un BTreeFindResult que el usuario debe liberar.
 272                  */
 273                 BTreeFindResult *FindKey (const Clave &k);
 274
 275                 int type() const;
 276
 277         //protected:
 278                 /* Funciones de Alta */
 279                 Clave* AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
 280                 Clave* AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
 281                 Clave* AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
 282
 283                 /* Funciones de Baja */
 284                 void DelKeyR (BTreeData *k, uint node, uint padre);
 285                 void DelKeyFromLeaf (Clave *k, uint node_num, uint padre);
 286                 void DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint right);
 287                 void FindBrothers (uint node_num, uint padre, uint &left, uint &right);
 288                 Clave *ReplaceKeyInFather (uint node_num, uint padre, Clave *k);
 289                 Clave *GetKey (uint node_num, char maxmin);
 290                 void JoinNodes (uint node1, uint node2, uint padre, int);
 291
 292                 /* Funciones de Búsqueda */
 293                 BTreeFindResult *FindKeyR (const Clave *k, uint node);
 294
 295                 /* Funciones de manejo de archivo */
 296                 void WriteFileHeader ();
 297
 298                 /* Manejo de Bloques */
 299                 void WriteBlock (uchar *block, uint num);
 300                 uchar *ReadBlock (uint num);
 301                 uchar *NewBlock (uint &num);
 302
 303                 /* Manejo de headers */
 304                 void ReadNodoHeader (uchar *node, BTreeNodeHeader *header);
 305                 void WriteNodoHeader (uchar *node, BTreeNodeHeader *header);
 306
 307                 /* Manejo de claves en memoria */
 308                 std::list<BTreeData *> ReadKeys (uchar *node, BTreeNodeHeader &node_header);
 309                 void WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list<BTreeData *> &keys);
 310                 void DeleteKeys (std::list<BTreeData *> &keys);
 311
 312                 /* Abreviacion de Claves */
 313                 void AbrevKey (std::list<BTreeData *> &lst);
 314                 void DeAbrevKey (std::list<BTreeData *> &lst);
 315
 316                 std::string filename;
 317                 BTreeFileHeader header;
 318
 319                 /** Apunta al archivo de datos, asi se abre solo 1 vez
 320                  *
 321                  *  \todo Ver si vale la pena
 322                  */
 323                 FILE *fp;
 324                 std::list<uint> deleted_nodes;
 325
 326
 327                 /* DEBUG */
 328         public:
 329                 void PrintNode (uint num);
 330 };
 331
 332 #endif // _B_TREE_H
 333