A questão geral

Quais são as diferenças entre algoritmos usando estruturas de dados e algoritmos usando bancos de dados?

Algum contexto

Esta é uma pergunta que está me incomodando há algum tempo, e eu não consegui encontrar uma resposta convincente para isso.

Atualmente, estou trabalhando para fortalecer minha compreensão de algoritmos que, é claro, envolvem fortemente estruturas de dados. Essas são estruturas básicas, como Bag, Fila, Pilha, Fila de prioridade e Heap.

Também uso bancos de dados diariamente para armazenar os dados que foram processados ​​e enviados pelo usuário final ou processados ​​pelo programa. Recupero e envio os dados por meio de um DAL, que possui estruturas de dados próprias que são geradas com base nas tabelas no banco de dados.

Minhas perguntas surgem quando eu tenho a opção de classificar os dados usando o banco de dados para enviá-los de volta para mim ordenados de maneira crescente / decrescente ou recuperar e carregar os dados em minha lógica, processar esses dados em uma fila prioritária e classificar heap tudo isso. Ou outro seria procurar registros usando o banco de dados, em vez de carregar um subconjunto dos registros e usar algo como pesquisa binária para encontrar os registros nos quais estou interessado.

Em minha opinião, eu tentaria realizar tantas operações no final do banco de dados antes de enviá-lo, porque a comunicação é cara. Isso também me faz pensar quando você usa algoritmos e estruturas de dados estritamente definidas dentro de sua própria lógica, em vez de processar dados do que os do banco de dados?

Então, aqui estão as perguntas ...

Questões

1. Quais são as diferenças entre estruturas de dados e bancos de dados?
2. Quando usamos algoritmos que usam estruturas de dados definidas exclusivamente dentro da sua própria lógica e não da lógica do banco de dados?
3. @ Harvey post: Quando os métodos no banco de dados se tornam menos eficientes do que os métodos em sua própria lógica?
   • @mirculixx post: O que torna um método eficiente?
4. @ Harvey post: Como o processamento de dados com estruturas de dados é mais rápido do que no banco de dados?

Esclarecimentos

1. @ Post Granant: Os bancos de dados com os quais eu normalmente trabalho são relacionais, e essas questões estão saindo do trabalho com eles. No entanto, acho que essas perguntas são aplicáveis ​​a qualquer estrutura de persistência (quando digo estrutura, quero dizer isso no sentido mais geral).

Eu sei que respostas sem um contexto específico são difíceis. Alimento para o pensamento, conselhos ou pontos de discussão são principalmente o que estou procurando e seria muito apreciado!

As estruturas de dados são, na maior parte:

1. Residente na memória,
2. Transitório,
3. Limitado em tamanho,
4. Não reentre sem adicionar mecanismos de concorrência, como bloqueios ou imutabilidade,
5. Não é compatível com ACID ,
6. Rápido, se escolhido com cuidado.

Os bancos de dados são, na maior parte:

1. Ligado a disco,
2. Persistente,
3. Ampla,
4. Com segurança simultânea,
5. Compatível com ACID, com transações recursos ,
6. Mais lento que as estruturas de dados

As estruturas de dados devem ser passadas de um lugar para outro e usadas internamente em um programa. Quando foi a última vez que você enviou dados de uma página da Web para um servidor da Web usando um banco de dados ou executou um cálculo em um banco de dados que residia inteiramente na memória?

Os sistemas de banco de dados usam estruturas de dados como parte de sua implementação interna. É uma questão de tamanho e escopo; você usa estruturas de dados dentro do seu programa, mas um sistema de banco de dados é um programa por si só.

Quais são as diferenças entre estruturas de dados e bancos de dados?

Em um nível abstrato, não há - um banco de dados é uma estrutura de dados.

Em um nível específico, os bancos de dados geralmente têm o objetivo de persistir dados, geralmente em um formato otimizado para inserções, atualizações, recuperação, junção ou outro objetivo (ou uma combinação).

Por exemplo, se você comparar uma tabela em um RDBMS para dizer uma matriz de dados, a diferença pode estar no tempo de execução do algoritmo, na quantidade de código que você precisa escrever, na quantidade de memória necessária para executar o algoritmo ou a flexibilidade de trabalhar / acessar os dados de fora do seu programa / algoritmo.

Quando usamos algoritmos que usam estruturas de dados definidas exclusivamente dentro da sua própria lógica e não da lógica do banco de dados?

Na tendência eu argumentaria

a) usar um banco de dados se você precisar persistir os dados de maneira acessível além do tempo de execução ou do objetivo do algoritmo específico.

b) usar sua própria estrutura de dados (na memória) se a velocidade do tempo de execução for importante ou se a persistência não for necessária

Por exemplo, se o seu algoritmo processa os registros do cliente, você pode armazenar esses registros (por exemplo, encontrar todos os clientes em uma área específica) para uso posterior por algum outro programa / algoritmo e para uma finalidade totalmente diferente (por exemplo, encontrar os clientes mais valiosos) ) Nesse caso, usar um banco de dados para manter os dados provavelmente é uma boa ideia.

Observe, no entanto, que existe o conceito de bancos de dados na memória que não necessariamente persistem dados, por razões de desempenho. Por exemplo, Redis ou HANA .

Quando os métodos do banco de dados se tornam menos eficientes do que os métodos da sua própria lógica?

A resposta depende muito das circunstâncias e do (tipo de) banco de dados em uso. Eu reformularia a pergunta para "o que torna um método eficiente?" Torna-se então um exercício de avaliar os métodos (= algoritmo) que você usaria para sua própria estrutura de dados versus os métodos usados ​​pelo banco de dados. Veja também o próximo ponto.

Como o processamento de dados com estruturas de dados é mais rápido do que no banco de dados?

Novamente, isso depende dos detalhes. Em geral, o processamento de dados na memória, diretamente acessível ao processo que executa seu algoritmo, é mais rápido do que enviar uma solicitação para outro processo (no mesmo computador ou através de uma rede) e solicitar que você envie os resultados novamente. . No entanto, se os dados já residem no banco de dados, enviar um comando - digamos uma instrução SQL para unir duas tabelas e calcular alguma função agregada - e recuperar apenas um pequeno resumo ou subconjunto dos dados pode ser muito mais eficiente do que transferir primeiro todos os dados e cálculo local dos resultados (usando suas próprias estruturas de dados).

O acesso ao disco é principalmente o mais caro nesta operação, mais frequentemente do que o acesso à rede (http://serverfault.com/questions/238417/are-networks-now-faster-than-disks). A menos que seu banco de dados não esteja localizado em pelo menos uma rede de 1 Gbps e na mesma rede que o servidor de aplicativos da web, o desempenho da rede não importará tanto quanto o desempenho do disco para conjuntos de dados maiores. Ou se seus dados residirem em discos de estado sólido muito rápidos, que serão mais rápidos que o acesso típico à rede. Além disso, os bancos de dados geralmente fornecem um mecanismo IPC, como pipes nomeados, em vez de usar TCP / IP, se o banco de dados residir no mesmo servidor que o servidor de aplicativos.

Se você conseguir manter a maior parte da estrutura de dados completa na memória entre solicitações, essa será geralmente a sua aposta mais rápida. Se não puder, será difícil superar uma boa estrutura de banco de dados com tabelas normalizadas e índices adequados para pesquisa e atualização de desempenho em qualquer coisa que não sejam pequenos conjuntos de registros, especialmente em um sistema com milhões de registros.

Os bancos de dados relacionais geralmente usam uma árvore B + ou uma variante dela sob o capô e têm muitas otimizações, como alinhamento de dados em conjuntos de discos e buffers para registros acessados ​​com freqüência. Isso os torna excelentes no processamento de grandes conjuntos de dados rapidamente, especialmente se houver agregação ou filtragem.

O que você quer dizer com banco de dados? Você quer dizer um banco de dados relacional como MySQL ou SQL Server? Um banco de dados relacional é uma estrutura de metadados que suporta alguns subconjuntos das operações definidas pelo modelo relacional . A teoria do modelo relacional que foi elaborada principalmente por Edgar Codd nos anos 60.

O modelo relacional é de propósito geral e flexível, mas isso significa que ele não pode tirar proveito da estrutura dos dados ou padrões de acesso. As estruturas de dados são úteis quando você sabe algo sobre os dados e como eles serão acessados. Por exemplo, se você souber que os últimos dados que você coloca em uma estrutura de dados serão os primeiros que deseja, poderá usar uma pilha.

Chamei o banco de dados relacional de uma estrutura de metadados, porque geralmente é um grande pacote de software que usa muitas estruturas de dados como pilhas, filas, árvores e listas para criar a estrutura de dados abstrata de uma tabela relacional.