Projeto Índice Árvore-B* - SCC0215

Este repositório reúne a implementação de um sistema em C que indexa arquivos de dados binários usando uma estrutura de Índice Árvore-B* e utiliza esse índice para aprimorar operações de busca (WHERE) e inserção (INSERT). Baseado no primeiro trabalho, este projeto propõe uma solução distinta, aplicando uma Árvore-B* em disco para otimizar desempenho e manutenção de grandes volumes de registros.

Problema Abordado

Em cenários de grandes arquivos de dados binários, consultas e inserções sequenciais podem se tornar custosas, especialmente quando há necessidade de buscas repetidas e junções rápidas. O desafio é:

• Criar e manter um índice em disco que minimize acessos a disco e acelere buscas por valores de chave primária.
• Implementar pesquisas condicionais (WHERE) que se beneficiem do índice quando disponível, com fallback para busca sequencial.
• Gerenciar inserções de forma estática, reutilizando espaços de registros logicamente removidos e atualizando o índice eficientemente.
• Garantir consistência dos arquivos de dados e de índice contra falhas de execução.

Solução Implementada

A implementação segue arquitetura modular, separando responsabilidades em três camadas principais:

1. Manipulação de Arquivos (manipulacao)

   • Abstrai operações sobre o arquivo de dados (ArqDados_t) e o arquivo de índice Árvore-B* (Arvore_t).
   • Gerencia alocação, leitura/gravação de cabeçalhos (status, RRN, nível, número de chaves), navegação de páginas e funções genéricas de I/O.
   • Define tipos opacos e callbacks para ações de inserção, busca e atualização em disco.

2. Camada de Funcionalidades (funcionalidades)

   • create_index: cria o índice Árvore-B* carregando registros não removidos do arquivo de dados, inserindo-os um a um na árvore em disco, usando rotinas de split (1-to-2, 2-to-3) e redistribuição para manter taxa de ocupação mínima.
   • where: executa buscas condicionais por um ou mais campos. Quando o critério inclui a chave indexada, realiza pesquisa em log(n) pelo índice; caso contrário, faz varredura seqüencial.
   • insert_into: insere novos registros no final do arquivo de dados ou em espaços reaproveitados, e atualiza o índice Árvore-B* correspondendo à chave primária de cada inserção.
   • Cada funcionalidade valida consistência dos arquivos antes e depois das operações, ajustando os campos de status dos cabeçalhos.

3. Ponto de Entrada (main.c)

   • Lê o código da funcionalidade (8 para create_index, 9 para where, 10 para insert_into) e invoca a rotina correspondente.

Fluxo de create_index

1. Abrir arquivos de dados (modo rb) e índice (modo w+b), marcar índice como inconsistente.
2. Ler cabeçalho do arquivo de dados e validar status.
3. Percorrer registros válidos, criar raiz da árvore com o primeiro registro e inserir os demais usando insercao_arvore.
4. Aplicar rotinas de split e redistribuição conforme regras de Árvore-B* (ordem m=5).
5. Atualizar cabeçalho do índice (status, RRN do próximo nó, níveis, chaves) e persistir no disco.
6. Exibir saída binária do arquivo de índice via binarioNaTela().

Boas Práticas e Estrutura de Código

• Modularização Estrita: separação clara entre I/O de baixo nível, algoritmos de árvore e lógica de negócio, facilitando manutenção e testes unitários.
• Abstração via Tipos Opaques: ArqDados_t e Arvore_t escondem detalhes de buffer, offsets e manipulação de bytes.
• Uso de Callbacks: callbacks genéricos (FncAcaoRegSeq, FncAcaoRegArv, FncAcaoBranch) permitem reutilização de rotinas de leitura, inserção e finalização.
• Documentação Inline: comentários detalhados em funções, parâmetros e fluxos complexos (split, redistribuição), reforçando compreensão do algoritmo.
• Tratamento Robusto de Erros: validação de status antes de qualquer gravação, mensagens padrão de falha em caso de inconsistências.
• Reutilização de Espaço: abordagem estática para registros removidos, preservando espaço e evitando fragmentação excessiva.

Compilação e Execução

1. Compilar:

   make all

2. Executar (exemplos):

   ./programaTrab 8 dados.bin idCrime inteiro indiceBstar.bin     # Criar índice B*
   ./programaTrab 9 dados.bin idCrime inteiro indiceBstar.bin 3   # WHERE com 3 buscas
   ./programaTrab 10 dados.bin idCrime inteiro indiceBstar.bin 2  # INSERT INTO 2 registros

Licença

Este trabalho faz parte das atividades da disciplina SCC0215 e destina-se a fins educacionais.