• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

afilipebarbosa

Qual a melhor estrutura a utilizar num banco de dados/sistema de arquivos!!

25 mensagens neste tópico

Boas,

Gostava de saber qual a estrutura de dados que acham mais eficaz para utilizar num banco de dados (tendo em conta que a procura nesse banco de dados seja bastante eficiente, a inserção se possível eficiente, e a remoção de eficiência desprezável).

Aguardo as vossas opiniões...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

MSSQL, Oracle.

Ele não quer SGBD!!

afilipebarbosa isso que dizes é muito vago, podias dar mais informação?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Na realidade creio que o que pretendes é mesmo um SGBD, pois os mesmo estão optimizados para essas operações.

Podes implementar as mesmas estruturas que os SGBDs, mas isso é reinventar a roda...

Podes, por exemplo, ter os dados num ficheiro (ou em vários) com uma estrutura de indexação ao lado para aumentar a performance das pesquisa (árvores binárias dão normalmente bons resultados nesta aplicação).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Peço desculpa realmente não me expliquei bem, o que pretendia é que me dissessem qual estrutura de dados que acham mais eficaz para utilizar num banco de dados (arvores binárias, arvores B+, tabela de hash, etc), pois das que conheço as arvores B+ são as mais eficaz, gostava de saber a vossa opinião.

Kt a resposta do Warrior (Hash Table), embora seja uma boa solução pra acesso a dados de uma forma bastante eficaz, para o efeito que pretendo, arranjar essa função de hash é um problema muito complexo, dai eu estar a tentar arranjar outras soluções.

De qualquer forma obrigado.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

as duas melhores opções são normalmente tabelas de hash ou árvores binárias, as árvores binárias são mais úteis quando é necessária ordenação dos dados e quando estamos constantemente a introduzir dados, mas as tabelas de hash ganham (normalemente) em tempo de acesso (é claro que isto depende do tipo de tabelas de hash que usas).

já agora é para implementar em que linguagem? em C, implementar tabelas de hash parece-me mais fácil do que implementar árvores binárias (equilibradas).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Peço desculpa realmente não me expliquei bem, o que pretendia é que me dissessem qual estrutura de dados que acham mais eficaz para utilizar num banco de dados (arvores binárias, arvores B+, tabela de hash, etc), pois das que conheço as arvores B+ são as mais eficaz, gostava de saber a vossa opinião.

Kt a resposta do Warrior (Hash Table), embora seja uma boa solução pra acesso a dados de uma forma bastante eficaz, para o efeito que pretendo, arranjar essa função de hash é um problema muito complexo, dai eu estar a tentar arranjar outras soluções.

De qualquer forma obrigado.

Sim aconselho-te arvores B ou arvores B+, os SGBD mais eficientes usam essas estruturas com o objectivo de criar indices multiplos, etc...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tudo depende até onde vai a relação dificuldade de implementação/eficiência.

Um vector permanentemente ordenado é muito fácil de programar e permite inserção em O(n) e procura em O(log n)

Se o número de inserções for muito superior ao número de pesquisas, podes inserir em O(1) e procurar em O(n log n)..

Tudo depende do objectivo mesmo..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se o número de inserções for muito superior ao número de pesquisas, podes inserir em O(1) e procurar em O(n log n)..

esse último O(n log n) está correcto?

não sei em que estrutura de dados estás a pensar, mas até numa lista ligada em que inseres à cabeça consegues inserções em O(1) e pesquisas em O(n)...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tudo depende até onde vai a relação dificuldade de implementação/eficiência.

Um vector permanentemente ordenado é muito fácil de programar e permite inserção em O(n) e procura em O(log n)

Se o número de inserções for muito superior ao número de pesquisas, podes inserir em O(1) e procurar em O(n log n)..

Tudo depende do objectivo mesmo..

Pois, mas la esta, com vectores ordenados, a inserção e remoção são muito dispendiosas...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se o número de inserções for muito superior ao número de pesquisas, podes inserir em O(1) e procurar em O(n log n)..

esse último O(n log n) está correcto?

não sei em que estrutura de dados estás a pensar, mas até numa lista ligada em que inseres à cabeça consegues inserções em O(1) e pesquisas em O(n)...

Claro, que estupidez..

Pensei em ordenar primeiro não sei porquê, já não fazia sentido neste caso.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A implementação estou a pensar em fazer em C, mas quando eu falei em dificuldade nas tabelas de hash, não me referia a implementação das mesmas em C, mas sim de arranjar um função de Hash que me desse uma chave única para cada valor (um função bijectiva), pois caso contrario, no meu problema ia ter muitas colisões logo não ia ser eficaz ao ponto que queria (ou caso utilizasse o vector de apontadores, ia voltar ao problema das listas).

Quanto as arvores B+, era solução que estava a pensar, embora tenha recorrido a este fórum pra saber a vossa opinião, pois podia existir alguma outra solução mais eficaz, de qualquer forma agradeço os vossos comentários pois é sempre uma boa referencia.

Obrigado.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Para o caso das funções Hash tens de resolver as colisões.

É impossivel arranjar uma função hash sem colisões, a não ser que uses um intervalo de valores limitado.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Acho muito estranho não conseguires arranjar uma função de hash +- indicada.

Quer dizer, podes arranjar uma função de hash para qualquer coisa, seja strings, valores, ou mesmo imagens/binários.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Usa árvores binárias, é a melhor solução que tens.

Há uma razão para as bds usares essa estrutura: é a melhor. :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Usa árvores binárias, é a melhor solução que tens.

Há uma razão para as bds usares essa estrutura: é a melhor. :)

Mas onde é k tu keres dizer que há vantagem em usar arvores binarias? em quê,concretamente, no SGBD?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas,

Warrior é verdade que eu consigo arranjar função de hash, mas imagina a seguinte situação:

A minha chave e uma string que está limitada entre [1;20] (caracteres), então ia ter um vector em memoria ou ficheiro com todas a combinações possíveis. Isto era muito bom se eu utilizasse tds essas chaves então não estava desperdiçar espaço e tinha acesso directo a informação através da tabela (com uma função de hash bijectiva). O problema ta kd não sei kual o numero de chaves que vou utilizar, embora tivesse um bom acesso em procuras estava a gastar espaço desnecessário. (Posso sempre utilizar uma função de Hash não bijectiva, mas voltava as colisões tornando-se assim de certa forma inferior as arvores :).

È perante esta situação que estou a pensar em utilizar as arvores B+, embora menos eficientes, mas não desperdiço espaço.

De qualquer forma obrigado a tds, é sempre bom ver as vossas opiniões.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se o espaço for uma preocupação.. é a decisão correcta. (daí os SGBDs não usarem Hashing)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Usa árvores binárias, é a melhor solução que tens.

Há uma razão para as bds usares essa estrutura: é a melhor. :P

Mas onde é que tu keres dizer que há vantagem em usar arvores binarias? em quê,concretamente, no SGBD?

As árvores binárias são uma das estruturas mais usadas/comuns pelos SGBDs para aumentar a performance na pesquisa de dados.

Repara num índice construído sobre uma árvore binária: permite que quando se aplica um filtro onde uma coluna que tem um índice se encontrem os registos de forma rápida e eficiente.

Um exemplo:

- uma escola tem 1000 alunos;

- o número de aluno tem um índice;

- o índice é construído sobre uma árvore binária que:

  + tem como nó raiz o número 500;

  + a divisão é feita pela metade;

Isto quer dizer que temos 500 como raíz, o nó filho da esquerda é o 250 e os da direita 750;

Uma pequisa que procure os alunos com número > 750, por exemplo 823, em apenas uma travessia da árvore, descendo da raíz (500) para o nó que contém número maiores que 500 (750), eliminamos imediatamente 3/4 (75%) de resultados que sabemos que não necessitamos de pesquisar. A juntar a isto, temos o facto de que uma árvore binária é uma estrutura extremamente leve (nós e apontadores) em memória e rápida de manipular.

Por tudo isto (e mais algumas coisas), as árvores binárias são uma excelente estrutura para este tipo de aplicações.

Lembro que os SGBDs usam esta estrutura em formas optimizadas que não a forma "simples" que aqui descrevi.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu sei o que são árvores binárias lol, o k tu keres dizer é que a pesquisa é binária, tendo no pior caso log2  N. Mas não é comum existir nos SGBW's, se conheceres algum avisa,eu sinceramente nao conheço... Por isso é que são usadas arvores B ou B+ para teres multiplos indices,etc... E quanto á pesquisa binária, ocorre sim em SGBD's baseados em ficheiros ordenados, ou indices baseados em ficheiros ordenados, mas NÃO com arvores binárias e sim com um vector ordenado por blocos. Mais eficiente para acesso é o hash, mas tem as suas desvantagens como ja disseram aqui. A MELHOR e mais UTILIZADA estrutura de dados são as arvores B e B+ com apontadores para blocos,bal,bla... Investiga sobre isso, e vais ver k tenho razao. :P

abraço.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu sei o que são árvores binárias lol, o que tu keres dizer é que a pesquisa é binária, tendo no pior caso log2  N. Mas não é comum existir nos SGBW's, se conheceres algum avisa,eu sinceramente nao conheço... Por isso é que são usadas arvores B ou B+ para teres multiplos indices,etc... E quanto á pesquisa binária, ocorre sim em SGBD's baseados em ficheiros ordenados, ou indices baseados em ficheiros ordenados, mas NÃO com arvores binárias e sim com um vector ordenado por blocos. Mais eficiente para acesso é o hash, mas tem as suas desvantagens como ja disseram aqui. A MELHOR e mais UTILIZADA estrutura de dados são as arvores B e B+ com apontadores para blocos,bal,bla... Investiga sobre isso, e vais ver que tenho razao. :P

abraço.

Hummm... Acho que não me fiz entender ou então tu não percebeste...

A tua explicação não é mais do que uma "instanciação" do exemplo que usei para ilustrar o porquê de da escolha de uma estrutura como são as árvores binárias.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu sei o que são árvores binárias lol, o que tu keres dizer é que a pesquisa é binária, tendo no pior caso log2  N. Mas não é comum existir nos SGBW's, se conheceres algum avisa,eu sinceramente nao conheço... Por isso é que são usadas arvores B ou B+ para teres multiplos indices,etc... E quanto á pesquisa binária, ocorre sim em SGBD's baseados em ficheiros ordenados, ou indices baseados em ficheiros ordenados, mas NÃO com arvores binárias e sim com um vector ordenado por blocos. Mais eficiente para acesso é o hash, mas tem as suas desvantagens como ja disseram aqui. A MELHOR e mais UTILIZADA estrutura de dados são as arvores B e B+ com apontadores para blocos,bal,bla... Investiga sobre isso, e vais ver que tenho razao. ;)

abraço.

Hummm... Acho que não me fiz entender ou então tu não percebeste...

A tua explicação não é mais do que uma "instanciação" do exemplo que usei para ilustrar o porquê de da escolha de uma estrutura como são as árvores binárias.

=x eu nao percebo onde é k as arvores binarias têm vantagem, nao estarás tu a confundir arvores B ou B+  com arvores binárias? é k são bem diferentes...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu sei o que são árvores binárias lol, o que tu keres dizer é que a pesquisa é binária, tendo no pior caso log2  N. Mas não é comum existir nos SGBW's, se conheceres algum avisa,eu sinceramente nao conheço... Por isso é que são usadas arvores B ou B+ para teres multiplos indices,etc... E quanto á pesquisa binária, ocorre sim em SGBD's baseados em ficheiros ordenados, ou indices baseados em ficheiros ordenados, mas NÃO com arvores binárias e sim com um vector ordenado por blocos. Mais eficiente para acesso é o hash, mas tem as suas desvantagens como ja disseram aqui. A MELHOR e mais UTILIZADA estrutura de dados são as arvores B e B+ com apontadores para blocos,bal,bla... Investiga sobre isso, e vais ver que tenho razao. ;)

abraço.

Hummm... Acho que não me fiz entender ou então tu não percebeste...

A tua explicação não é mais do que uma "instanciação" do exemplo que usei para ilustrar o porquê de da escolha de uma estrutura como são as árvores binárias.

=x eu nao percebo onde é que as arvores binarias têm vantagem, nao estarás tu a confundir arvores B ou B+  com arvores binárias? é que são bem diferentes...

Sim, tens razão, não são a mesma coisa.

Quanto ao uso de árvores binárias nas BDs, estou em crer que o MySQL faz uso delas em certas situações, mas estamos aqui a falar da excepção e não da regra.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora