#ifndef _B_TREE_H
#define _B_TREE_H
-/**
- * La estructura general del archivo seria :
+/** \page page_btree Árbol B
+ *
+ * \section page_model_class Estructura del árbol en memoria.
+ *
+ * La organización de las clases utilizadas es la siguiente :
+ *
+ * \image html clases.png
+ * \image latex clases.eps "Diagrama de Clases" width=10cm
+ *
+ * Para operar con un determinado nodo en memoria, lo que se hace es lo siguiente.
+ * Como primer paso se carga el bloque en memoria llamando a ReadBlock y se lee de él
+ * su encabezado utilizando una llamada a BTree::ReadNodeHeader, que almacena los datos
+ * en una clase BTreeNodeHeader. A continuación se leen las claves, todavía en formato
+ * RAW, y se genera una lista con instancias de BTreeData. Esta lista es generada
+ * con la llamada a BTree::ReadKeys.
+ *
+ * La operación de búsqueda o inserción se realiza en memoria sobre la lista cargada
+ * anteriormente. Cuando se está listo para guardar todo de nuevo en disco se opera
+ * como se explica a continuación.
+ *
+ * Como primer paso se escriben las claves de la lista nuevamente en el bloque en
+ * memoria en formato RAW, para ello se utilizar WriteKeys, que además de pasar
+ * las claves a formato RAW, también actualiza los datos del header (espacio libre
+ * y cantidad de ítems). Luego se escribe el header en formato RAW con BTree::WriteNodeHeader
+ * y por último se baja a disco el bloque con WriteBlock.
+ *
+ * Para liberar la memoria utilizada solo basta llamar a BTree::DeleteKeys y liberar
+ * el bloque RAW utilizado para el nodo.
+ *
+ * \section page_model_estructura Estructura del árbol en disco.
+ *
+ * La estructura del archivo donde se almacena el árbol es una secuencia
+ * de bloques de tamaño fijo parametrizable. Cada bloque representa un nodo
+ * del árbol, exceptuando el bloque 0 que corresponde al encabezado donde se
+ * guardan los parámetros del árbol.
+ *
+ * <pre>
+ * Bloque 0 Bloque 1 Bloque 2 Bloque N
* +----------+----------+----------+-----+----------+
- * |FileHeader| Bloque 0 | Bloque 1 | ... | Bloque N |
+ * |FileHeader| Nodo 0 | Nodo 1 | ... | Nodo N-1 |
* +----------+----------+----------+-----+----------+
- *
+ * </pre>
+ *
* Cada bloque tiene su propio encabezado siguiendo la siguiente
* estructura :
+ * <pre>
* +--------------+-----------------------------------+
- * | BloqueHeader | Area de Claves |
+ * | BloqueHeader | Área de Claves |
* +--------------+-----------------------------------+
+ * </pre>
*
- * El area de claves depende del tipo de arbol (INDICE o EXAHUSTIVO)
- * y del tipo de clave (Longitud fija o variable).
+ * El área de claves depende del tipo de árbol (IDENTIFICACION o CLASIFICACION)
+ * y del tipo de Clave (ClaveFija o ClaveVariable).
*
- * Los nodos que "hojas" (es decir, aquellos que no tienen hijos) no
- * tienen "punteros", por lo que el area de datos seria algo como :
+ * Los nodos que son "hojas" (es decir, aquellos que no tienen hijos) no
+ * tienen "punteros", por lo que el área de datos seria algo como :
+ * <pre>
* +--------------+--------------+--------------+--------------+
* | clave1,dato1 | clave2,dato2 | ............ | claveN,datoN |
* +--------------+--------------+--------------+--------------+
+ * </pre>
+ *
+ * El par (claveN,datoN) es representado por la clase BTreeLeafData.
*
* Ahora, los bloques intermedios tienen punteros a los hijos, y
- * quedaria algo como :
+ * quedaría algo como :
+ * <pre>
* +---------+----------------------+-------+----------------------+
* | HijoIzq | clave1,dato1,HijoDer | ..... | claveN,datoN,HijoDer |
* +---------+----------------------+-------+----------------------+
+ * </pre>
+ *
+ * El puntero HijoIzq es representado en memoria por la clase BTreeChildData, y
+ * el resto por BTreeData.
*
* El tamaño de la clave es variable, por lo que la cantidad de claves
* que puede almacenar se basa en la cantidad de espacio libre.
*
* 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 insercion". Ahora, un problema a resolver es cuando se debe
- * juntar nodos, ya que el arbol B este es particular (Preguntar a Cerveto?).
+ * de inserción".
+ *
+ * \section page_model_op Operaciones Básicas
+ *
+ * En esta sección explicaremos como se realizan las diferentes operaciones
+ * sobre el árbol.
+ *
+ * \subsection page_model_add Agregar una Clave.
+ *
+ * Agregar una clave al árbol es relativamente fácil ya que siempre se agregan
+ * en las hojas.
+ *
+ * El algoritmo comienza a recorrer la raíz buscando la clave inmediatamente
+ * superior (llamada clave de corte) a la que deseamos agregar. Si la raíz es una hoja, la clave es
+ * agregada antes de la clave que corta el algoritmo.
+ *
+ * Si la raíz no es una hoja, se llama recursivamente yendo al nodo hijo de
+ * la clave anterior a la clave de corte, hasta llegar a una hoja y finalmente
+ * agregar la clave.
+ *
+ * En este punto pueden pasar dos cosas. La primera es que la clave entre en el
+ * lugar libre que le queda al nodo, entonces es agregada y retorna liberando
+ * todo lo que quedó pendiente.
+ *
+ * La segunda situación es que la clave no entre y el nodo deba ser separado
+ * en dos. Cuando esto sucede se crea una lista temporal ordenada con las
+ * claves del nodo a partir y la nueva clave a agregar.
+ *
+ * La primer mitad se guarda en un nodo, la clave del medio se deja para retornar
+ * al padre y la segunda mitad se pone en un nuevo nodo. Luego de guardar todo
+ * se le retorna al padre una clave. Éste al detectar que un hijo manda una clave
+ * tratará de agregarla siguiendo el mismo procedimiento que el hijo (si no entra
+ * debe realizar un split), hasta llegar a la raíz.
+ *
+ * La única diferencia entre el split en una hoja y el resto de los nodos, es que
+ * estos últimos hace uso de los datos "hijo izquierdo" e "hijo derecho" también
+ * pasados como parámetros luego del split, a fin de ajustar los punteros necesarios.
+ *
+ * \subsection page_model_del Eliminar una Clave.
+ *
+ * El proceso de eliminar una clave es un poco más complejo y cubre más situaciones
+ * particulares.
+ *
+ * El algoritmo se divide básicamente en 2 casos : eliminar de una hoja y eliminar
+ * de un nodo interno.
+ *
+ * Ambos algoritmos comienzan con una búsqueda en profundidad de la clave a borrar.
+ * en el momento de encontrarla se llama a BTree::DelKeyFromLeaf o BTree::DelKeyFromNode
+ * dependiendo del caso.
+ *
+ * \subsubsection page_model_del_hoja Eliminar de una Hoja.
+ *
+ * Cuando la clave es encontrada en una hoja simplemente se elimina de la hoja.
+ *
+ * Luego debemos verificar que se cumpla la condición de que el nodo tenga al menos
+ * el 50% del espacio ocupado. Si esto no ocurre debemos actuar como se explica a
+ * continuación.
+ *
+ * Como primer intento pedimos prestada una clave a alguno nuestros hermanos. Si
+ * alguno es capaz de pasar una clave, ésta última se reemplaza en el padre y la
+ * clave del padre para al nodo en cuestión. Esto se hace para mantener el ordenamiento
+ * del árbol intacto.
+ *
+ * Si ningún hermano me puede prestar, lo único que nos queda es unir dos nodos.
+ * La unión se realiza con cualquier nodo disponible, siempre preguntando primero
+ * por el derecho y si este no existe, se une con el izquierdo. Luego de unir se
+ * le notifica al padre y se ajustan los punteros correspondientes.
+ *
+ * \subsubsection page_model_del_nodo Eliminar de un Nodo.
*
+ * Cuando la clave a eliminar se encuentra en una hoja se debe tratar de forma
+ * especial. Lo primero que se hace es buscar en todo el árbol la clave
+ * inmediatamente superior. Esto se logra yendo al hijo derecho de la clave a borrar
+ * y luego siempre hacia el hijo izquierdo hasta llegar a una hoja.
*
- * TODO :
- * * Ver como manejar las claves de manera transparente a las APIs de
- * agregar y de borrar (EMUFS lo solucionaba bastante bien, se puede
- * tomar una idea simimar)
+ * La primer clave de la hoja encontrada es reemplazada por la clave del padre y
+ * se llama al borrar de una hoja. Como siempre la clave reemplazada en la hoja queda
+ * en primer lugar, no hay problemas que no esté ordenada al momento de llamar
+ * 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.
+ * Si la clave es encontrada se retorna una estructura del tipo BTreeFindResult
+ * con toda la información útil.
+ *
+ * Si no se encuentra retorna NULL.
*/
#include <iostream>
#include <string>
+#include <list>
#include "common.h"
#include "clave.h"
+#include "clave_fija.h"
+#include "clave_variable.h"
+#include "btree_data.h"
+#include "exception.h"
/* alias para codear menos :) */
-/** Encabezado del archivo BTree */
-typedef struct _btree_file_ {
+/** Encabezado del archivo BTree
+ *
+ * Esta estructura es para comodidad de manejo, aunque en disco
+ * ocupe block_size de tamaño.
+ */
+struct BTreeFileHeader {
+ char magic[7];
uint block_size;
-} BTreeFileHeader;
+ int tree_type;
+ int key_type;
+ uint block_data_counter;
+};
/** Encabezado de un bloque */
-typedef struct _btree_header_ {
+struct BTreeNodeHeader {
/** Indica a que nivel corresponde un bloque
*
* nivel == 0 : una hoja
/** Cantidad de elementos en el nodo */
unsigned int item_count;
-} BTreeNodeHeader;
+};
-/** Crea un nuevo arbol B
+/** Resultado de la búsqueda de una clave */
+struct BTreeFindResult {
+ /** Número de nodo que contiene la clave buscada. */
+ uint node;
+ /** Encabezado del nodo que contiene la clave. */
+ BTreeNodeHeader header;
+};
+
+/** Modelo del árbol B
*
* \param filename Nombre del archivo a crear
* \param block_size Tamaño de bloque a utilizar
+ * \param k_t Tipo de clave a utilizar
* \return Un nuevo arbol B creado o NULL en caso de error
*/
class BTree {
public:
- BTree (const char *filename, unsigned int block_size, bool create_new_file = false);
+ 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 ();
- void AddKey (Clave &k);
- void DelKey (Clave &k);
+ /** Tipos de clave a usar */
+ enum {
+ KEY_FIXED, /**< Utilización de clave de longitud fija */
+ KEY_VARIABLE /**< Utilización de clave de longitud variable */
+ };
- private:
- void write_tree_header ();
- void write_block (uchar *block, uint num);
+ enum {
+ TYPE_IDENTIFICACION,
+ TYPE_CLASIFICACION
+ };
+
+ /** Agrega una nueva clave al árbol. */
+ void AddKey (const Clave &k);
+ /** Elimina una clave del árbol. */
+ void DelKey (const Clave &k);
+ /** Busca si existe una clave en el árbol
+ *
+ * \return Un BTreeFindResult que el usuario debe liberar.
+ */
+ BTreeFindResult *FindKey (const Clave &k);
+
+ int type() const;
+
+ //protected:
+ /* Funciones de Alta */
+ Clave* AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
+ Clave* AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
+ Clave* AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
+
+ /* Funciones de Baja */
+ void DelKeyR (BTreeData *k, uint node, uint padre);
+ void DelKeyFromLeaf (Clave *k, uint node_num, uint padre);
+ void DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint right);
+ void FindBrothers (uint node_num, uint padre, uint &left, uint &right);
+ Clave *ReplaceKeyInFather (uint node_num, uint padre, Clave *k);
+ Clave *GetKey (uint node_num, char maxmin);
+ void JoinNodes (uint node1, uint node2, uint padre, int);
+
+ /* Funciones de Búsqueda */
+ BTreeFindResult *FindKeyR (const Clave *k, uint node);
+
+ /* Funciones de manejo de archivo */
+ void WriteFileHeader ();
+ void ReadFileHeader ();
+ /* Manejo de Bloques */
+ void WriteBlock (uchar *block, uint num);
uchar *ReadBlock (uint num);
+ uchar *NewBlock (uint &num);
+ /* Manejo de headers */
void ReadNodoHeader (uchar *node, BTreeNodeHeader *header);
void WriteNodoHeader (uchar *node, BTreeNodeHeader *header);
+ /* Manejo de claves en memoria */
+ std::list<BTreeData *> ReadKeys (uchar *node, BTreeNodeHeader &node_header);
+ void WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list<BTreeData *> &keys);
+ void DeleteKeys (std::list<BTreeData *> &keys);
+
+ /* Abreviacion de Claves */
+ void AbrevKey (std::list<BTreeData *> &lst);
+ void DeAbrevKey (std::list<BTreeData *> &lst);
+
std::string filename;
BTreeFileHeader header;
+ uint GetNextBlockData ();
+
/** Apunta al archivo de datos, asi se abre solo 1 vez
*
- * \TODO Ver si vale la pena
+ * \todo Ver si vale la pena
*/
FILE *fp;
+ std::list<uint> deleted_nodes;
+ std::list<uint> deleted_block_data;
+
+
+ /* DEBUG */
+ public:
+ void PrintNode (uint num);
};
#endif // _B_TREE_H
projects / z.facultad / 75.52 / treemulator.git / blobdiff