#ifndef _B_TREE_H
#define _B_TREE_H
-/**
- * La estructura general del archivo seria :
+/** \page page_btree Árbol B
+ *
+ * \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 |
* +--------------+-----------------------------------+
+ * </pre>
*
* El area de claves depende del tipo de arbol (INDICE o EXAHUSTIVO)
- * y del tipo de clave (Longitud fija o variable).
+ * y del tipo de Clave (ClaveFija o ClaveVariable).
*
- * Los nodos que "hojas" (es decir, aquellos que no tienen hijos) no
+ * Los nodos que son "hojas" (es decir, aquellos que no tienen hijos) no
* tienen "punteros", por lo que el area 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 :
+ * <pre>
* +---------+----------------------+-------+----------------------+
* | HijoIzq | clave1,dato1,HijoDer | ..... | claveN,datoN,HijoDer |
* +---------+----------------------+-------+----------------------+
+ * </pre>
+ *
+ * El puntore 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.
* juntar nodos, ya que el arbol B este es particular (Preguntar a Cerveto?).
*
*
- * TODO :
+ * \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)
*/
+#include <iostream>
#include <string>
+#include <list>
+#include "common.h"
+#include "clave.h"
+#include "clave_fija.h"
+#include "clave_variable.h"
+#include "btree_data.h"
/* alias para codear menos :) */
-typedef unsigned char uchar;
-/** Encabezado del archivo BTree */
-typedef struct _btree_file_ {
- unsigned int block_size;
-} BTreeFileHeader;
+/** Encabezado del archivo BTree
+ *
+ * Esta estructura es para comodidad de manejo, aunque en disco
+ * ocupe block_size de tamaño.
+ */
+struct BTreeFileHeader {
+ uint block_size;
+};
/** 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;
-} BTreeHeader;
+};
+
+/** 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;
+};
-/** Crea un nuevo arbol B
+/** 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 k_t = KEY_FIXED, bool create_new_file = false);
~BTree ();
- void AddKey ();
- void DelKey ();
+ /** 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);
+ /** 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);
+
+ //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 ();
+
+ /* 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;
+ int key_type;
/** 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;
+
+
+ /* DEBUG */
+ public:
+ void PrintNode (uint num);
};
#endif // _B_TREE_H
projects / z.facultad / 75.52 / treemulator.git / blobdiff