Olá, esta é a implementação de uma Arvore B+ (baseada em arquivo) que eu fiz em C. É totalmente funcional. O código atual não está compilado. Funciona em diversos sistemas operacionais com suporte a C standard. (a extensão é cpp, mas o código foi escrito em C) mas para isso talvez seja necessário mudar a quantidade de chaves por pagina (struct no) para que fique exatamente do tamanho de um setor ou cluster de disco.
http://sourceforge.net/projects/btreeindextodbf/
aqui o código fonte para a visualização:
http://btreeindextodbf.svn.sourceforge.net/viewvc/btreeindextodbf/
Aproveito para comentar um pequeno problema que ocorreu. Quando eu fui
testar o código rodando em um pendriver (durante uma apresentação) para
indexar um milhão de registros o código demorou muito para ser executado
(muito mesmo eu não esperei terminar) enquanto que no disco rigido ela
demora em média 2 minutos para indexar um milhão de registros. Já usei a
página do tamanho do cluster é (4096 bytes) e do tamanho do setor (512
bytes), nenhum dos dois casos deu certo no pendriver, no entanto, quando
testei com uma quantidade irrisória de apenas quatro chaves por pagina
consegui executar com "sucesso" no pendriver para 1 milhão de registros.
Pude observar também que a unidade de armazenamento no pendriver (bem
como no hd) é do tamanho do cluster. Criando um arquivo com um caractere
e clicando em propriedades do arquivo aparece la "Tamanho: 1 byte,
Tamanho em disco: 4096 bytes". Para saber o tamanho do cluster e do
setor no windows xp eu fui no ms dos e digitei: "fsutil fsinfo ntfsinfo
c:" (esse comando não serve para o pendriver).
A arvore funciona perfeitamente no meu hd, todas as funções auxiliares
foram testadas separadamente antes da finalização do algoritmo. Quase
todas as alocações tem um free associado, com excessão da raiz que é
mantida em memória durante a criação do índice gerando um lixo de
memória correspondente à altura da arvore. A raiz é re-utilizada
constantemente em um loop para criar o indice para um arquivo dbf já
existente. Por isso é mantida em memória ram e gravada no disco em caso
de modificação.
Para o problema da indexação de multiplos campos no banco de dados eu
optei por concatenar as n chaves ex: "CidadeBairroNome" e usar como uma
chave única. No entanto a chave pode ficar muito grande. Para resolver
isso eu criei funções para truncar essas palavras em algo com:
"CidBaiNom", no entanto isso também é um problema pois podem ocorrer por
exemplo "Cida" e "Cide", ou seja, o caractere diferenciador ser o
próximo caractere e eu ter escolhido uma quantidade muito reduzida de
caracteres.
Eu não sei se seria viável ter um arquivo separado contendo somente as
chaves do nó porque, embora eu tivesse uma altura menor na arvore, eu
teria o custo adicional de acessar o disco para buscar a chave (busca
binária). Em um nó com 4 chaves eu teria a mais pelo menos mais 2
acessos a disco, totalizando 3 acessos (carregar o nó + carregar as
chaves), seria como se tivesse uma arvore avl em disco (muito estranho).. eh pensando bem não é uma boa idéia não.
Espero que gostem do meu código, está totalmente em português legivel, programado no Dev-C++ e testado no Visual Studio.
OBS: No segundo link desse post tem uma versão compilada do código. Para executar com um milhão de registros é necessário executar antes "InsereRegistros.exe" que esta na pasta "Um milhao de registros" que gera "banco.dbf" a partir do arquivo "modelo.dbf" que contem apenas 4 registros.
