Class BTree

java.lang.Object
AEDs3.DataBase.Index.BTree
All Implemented Interfaces:
ForwardIndex
public class BTree extends Object implements ForwardIndex
Classe que representa uma Árvore B, implementando a interface Index. Esta classe fornece métodos para gerenciar uma estrutura de Árvore B, que é uma estrutura de dados auto-balanceada que mantém dados ordenados e permite operações eficientes de inserção, exclusão e busca.

A Árvore B é armazenada em um arquivo, permitindo o armazenamento persistente da estrutura da árvore. Cada nó na Árvore B é representado por uma Página, que contém elementos e páginas filhas. Páginas só são mantidas na memória enquanto necessário.

  • Field Details

    • root

      private BTree.Page root
      A raiz da Árvore B.

    • halfPageCapacity

      private final int halfPageCapacity
      Capacidade de meia página da Árvore B.

    • pageCapacity

      private final int pageCapacity
      Capacidade total de uma página na Árvore B.

    • filePath

      private String filePath
      Caminho do arquivo onde a Árvore B é armazenada.

    • file

      private RandomAccessFile file
      Arquivo de acesso aleatório para manipulação da Árvore B.

  • Constructor Details

    • BTree

      public BTree(String filePath) throws IOException
      Construtor que cria uma Árvore B a partir de um arquivo existente.
      Parameters:
      filePath - O caminho para o arquivo onde a Árvore B está armazenada.
      Throws:
      IOException - Se ocorrer um erro de I/O ao acessar o arquivo.

    • BTree

      public BTree(int order, String filePath) throws IOException
      Construtor que cria uma nova Árvore B com uma ordem especificada e caminho de arquivo.
      Parameters:
      order - A ordem da Árvore B, que determina o número máximo de filhos que cada nó pode ter.
      filePath - O caminho para o arquivo onde a Árvore B será armazenada.
      Throws:
      IOException - Se ocorrer um erro de I/O ao criar o arquivo.

  • Method Details

    • destruct

      public void destruct() throws IOException
      Destrói a Árvore B, fechando o arquivo e deletando-o do sistema de arquivos.
      Specified by:
      destruct in interface ForwardIndex
      Throws:
      IOException - Se ocorrer um erro de I/O ao fechar ou deletar o arquivo.

    • save

      private void save() throws IOException
      Salva todas as páginas carregadas, partindo da raiz e seguindo recursivamente.
      Throws:
      IOException - Se ocorrer um erro de I/O durante a operação de salvamento.

    • unload

      private void unload()
      Descarrega a Árvore B da memória, liberando os recursos associados.

    • search

      public long search(int id) throws IOException
      Busca um registro na Árvore B pelo identificador fornecido.
      Specified by:
      search in interface ForwardIndex
      Parameters:
      id - O identificador do registro a ser buscado.
      Returns:
      A posição do registro no arquivo, ou -1 se o registro não for encontrado.
      Throws:
      IOException - Se ocorrer um erro de I/O durante a operação de busca.

    • search

      private ForwardIndexRegister search(ForwardIndexRegister reg) throws IOException
      Busca um registro na árvore B a partir de um registro de índice fornecido.
      Parameters:
      reg - O registro de índice a ser buscado.
      Returns:
      O registro de índice encontrado ou null se não encontrado.
      Throws:
      IOException - Se ocorrer um erro de I/O durante a busca.

    • search

      private ForwardIndexRegister search(ForwardIndexRegister reg, BTree.Page page) throws IOException
      Busca um registro na árvore B a partir de um registro de índice e uma página fornecidos.
      Parameters:
      reg - O registro de índice a ser buscado.
      page - A página atual onde a busca é realizada.
      Returns:
      O registro de índice encontrado ou null se não encontrado.
      Throws:
      IOException - Se ocorrer um erro de I/O durante a busca.

    • insert

      public void insert(int id, long pos) throws IOException
      Insere um novo registro na Árvore B com o identificador e posição fornecidos.
      Specified by:
      insert in interface ForwardIndex
      Parameters:
      id - O identificador do registro a ser inserido.
      pos - A posição do registro no arquivo.
      Throws:
      IOException - Se ocorrer um erro de I/O durante a operação de inserção.

    • insere

      private void insere(ForwardIndexRegister reg) throws IOException
      Insere um novo registro na árvore B.
      Parameters:
      reg - O registro a ser inserido.
      Throws:
      IOException - Se ocorrer um erro de I/O durante a operação de inserção.

    • insere

      private BTree.Page insere(ForwardIndexRegister reg, BTree.Page page, ForwardIndexRegister[] regRet, boolean[] grown) throws IOException
      Insere um registro em uma página específica da árvore B.
      Parameters:
      reg - O registro a ser inserido.
      page - A página atual onde a inserção é realizada.
      regRet - Array para armazenar o registro retornado.
      grown - Array para indicar se a árvore cresceu.
      Returns:
      A página resultante após a inserção.
      Throws:
      IOException - Se ocorrer um erro de I/O durante a operação de inserção.

    • pageInsert

      private void pageInsert(BTree.Page page, ForwardIndexRegister reg, BTree.Page pageRight) throws IOException
      Insere um registro em uma página específica, ajustando os elementos e filhos.
      Parameters:
      page - A página onde o registro será inserido.
      reg - O registro a ser inserido.
      pageRight - A página à direita do registro inserido.
      Throws:
      IOException - Se ocorrer um erro de I/O durante a operação de inserção.

    • delete

      public void delete(int id) throws IOException
      Remove um registro da Árvore B com o identificador fornecido.
      Specified by:
      delete in interface ForwardIndex
      Parameters:
      id - O identificador do registro a ser removido.
      Throws:
      IOException - Se ocorrer um erro de I/O durante a operação de remoção.

    • delete

      private void delete(ForwardIndexRegister reg) throws IOException
      Método auxiliar para remover um registro da árvore B.
      Parameters:
      reg - O registro a ser removido.
      Throws:
      IOException - Se ocorrer um erro de I/O durante a operação de remoção.

    • delete

      private BTree.Page delete(ForwardIndexRegister reg, BTree.Page page, boolean[] shrunk) throws IOException
      Método recursivo para remover um registro de uma página específica.
      Parameters:
      reg - O registro a ser removido.
      page - A página atual onde a busca e remoção são realizadas.
      shrunk - Array booleano que indica se a página diminuiu de tamanho.
      Returns:
      A página resultante após a remoção.
      Throws:
      IOException - Se ocorrer um erro de I/O durante a operação de remoção.

    • antecessor

      private boolean antecessor(BTree.Page page, int ind, BTree.Page parentPage) throws IOException
      Encontra e substitui o registro pelo seu antecessor.
      Parameters:
      page - A página atual.
      ind - O índice do registro na página.
      parentPage - A página pai.
      Returns:
      true se a página diminuiu de tamanho, caso contrário false.
      Throws:
      IOException - Se ocorrer um erro de I/O durante a operação.

    • reconstruct

      private boolean reconstruct(BTree.Page page, BTree.Page parentPage, int parentIdx) throws IOException
      Reconstrói a árvore após a remoção de um registro, se necessário.
      Parameters:
      page - A página atual.
      parentPage - A página pai.
      parentIdx - O índice da página atual na página pai.
      Returns:
      true se a página diminuiu de tamanho, caso contrário false.
      Throws:
      IOException - Se ocorrer um erro de I/O durante a operação.

    • getHalfPageCapacity

      public int getHalfPageCapacity()
      Obtém a capacidade de meia página da Árvore B. Este é o mesmo valor passado ao construtor na criação do índice.
      Returns:
      A capacidade de meia página, que é a metade do número máximo de elementos que uma página pode conter.

    • listFilePaths

      public String[] listFilePaths()
      Description copied from interface: ForwardIndex
      Lista os caminhos relativos de todos os arquivos associados ao índice atual.
      Specified by:
      listFilePaths in interface ForwardIndex
      Returns:
      Um array de strings contendo os caminhos relativos de todos os arquivos utilizados por este índice.