Vantagem das árvores B+ sobre as OCS?
parece que ambos têm a complexidade média de o (logN) para a maioria das operações de nota, Mas B+ árvores também têm um adicional (negligenciável?) o tempo de busca em cada nó-filho, onde os OCS obviamente só levam O(1) tempo para descobrir para que nó-filho avançar.
Quais as vantagens do mundo real que tornam as árvores B+ mais populares em bases de dados do que TSC?2 answers
A principal vantagem da árvore B+ (e das árvores B em geral) sobre as árvores binárias de busca é que elas brincam bem com caches. Se você tem uma árvore de busca binária cujos nós são armazenados em ordem mais ou menos Aleatória na memória, então cada vez que você segue um ponteiro, a máquina terá que puxar um novo bloco de memória para o cache do processador, que é dramaticamente mais lento do que acessar a memória já em cache.
A B+ - tree e a b-tree funcionam por cada nó armazenar um enorme número de chaves ou valores e ter um grande número de crianças. Eles são normalmente embalados juntos de uma forma que torna possível para um único nó se encaixar bem no cache (ou, se armazenado no disco, para ser puxado do disco em uma única operação de leitura). Você então tem que fazer mais trabalho para encontrar uma chave dentro do nó ou determinar qual criança para ler a seguir, mas porque todos os acessos de memória feita em um único nó pode ser feito sem voltar para o disco, os tempos de acesso são muito pequenos. Isto significa que mesmo que em princípio a BST possa ser melhor em termos de Número de acessos de memória, A B+-árvore e a b-árvore podem ser melhores em termos de Tempo de execução desses acessos de memória.
O caso de uso típico para uma árvore B+ou B-árvore está em um banco de dados, onde há uma enorme quantidade de informação e os dados são tão numerosos que nem todos eles podem caber na memória principal. Assim, os dados podem então ser armazenados em uma B+-árvore ou B-árvore em um disco rígido em algum lugar. Presente minimiza o número de leituras de disco necessárias para puxar os dados durante as pesquisas. Alguns sistemas de arquivos (como ext4, eu acredito) usam B-árvores, bem como pela mesma razão - eles minimizam o número de pesquisas de disco necessário, que é o gargalo real.
Espero que isto ajude!O armazenamento de dados na vida real (por exemplo, em DB) requer que muitos dados sejam armazenados. Uma vez que a recuperação de dados é a operação básica da preocupação, é bastante demorado ler os dados do disco do que a RAM.
Este é o senão...A BST armazena dados menores num nó em comparação com B + árvores. Isto resulta no aumento da altura de BST do que B+ árvores. Então eles são armazenados no disco em vez de RAM.
Cada vez que os dados têm de ser recuperados da árvore, os dados de o disco tem de ser carregado para a memória principal(que é, naturalmente, um processo demorado), enquanto que, no caso de árvores B+, os dados já existe na memória RAM, e o nó obrigatório é obtida diretamente, e com os dados obtidos a partir desse nó, que pode conter muitos filhos(mas o tempo para a recuperação de dados é menor no caso de árvores B+, porque não há necessidade de carregamento de dados do disco para a RAM).