/** \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
* estructura :
* <pre>
* +--------------+-----------------------------------+
- * | BloqueHeader | Area de Claves |
+ * | BloqueHeader | Área de Claves |
* +--------------+-----------------------------------+
* </pre>
*
- * El area de claves depende del tipo de arbol (INDICE o EXAHUSTIVO)
+ * El área de claves depende del tipo de árbol (IDENTIFICACION o CLASIFICACION)
* y del tipo de Clave (ClaveFija o ClaveVariable).
*
* 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 :
+ * tienen "punteros", por lo que el área de datos seria algo como :
* <pre>
* +--------------+--------------+--------------+--------------+
* | clave1,dato1 | clave2,dato2 | ............ | claveN,datoN |
* 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 puntore HijoIzq es representado en memoria por la clase BTreeChildData, y
+ * 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
*
* 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.
+ *
+ * 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.
*
- * \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)
+ * 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 "clave_fija.h"
#include "clave_variable.h"
#include "btree_data.h"
+#include "exception.h"
/* alias para codear menos :) */
*/
struct BTreeFileHeader {
uint block_size;
+ int tree_type;
+ int key_type;
};
/** Encabezado de un bloque */
*/
class BTree {
public:
- BTree (const std::string &filename, unsigned int block_size, int k_t = KEY_FIXED, 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 ();
/** Tipos de clave a usar */
KEY_VARIABLE /**< Utilización de clave de longitud variable */
};
+ enum {
+ TYPE_IDENTIFICACION,
+ TYPE_CLASIFICACION
+ };
+
/** Agrega una nueva clave al árbol. */
void AddKey (const Clave &k);
/** Elimina una clave del árbol. */
*/
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);
/* Funciones de Baja */
void DelKeyR (BTreeData *k, uint node, uint padre);
void DelKeyFromLeaf (Clave *k, uint node_num, uint padre);
- void DelKeyFromOther (const Clave &k, BTreeFindResult *r);
- void FindB (uint node_num, uint padre, uint &left, uint &right);
+ 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);
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
*/
FILE *fp;
+ std::list<uint> deleted_nodes;
/* DEBUG */
projects / z.facultad / 75.52 / treemulator.git / blobdiff