Quais são as diferenças entre as árvores B e as árvores B +?

293

Em uma árvore b, você pode armazenar chaves e dados nos nós interno e folha , mas em uma árvore b + você precisa armazenar os dados apenas nos nós folha .

Existe alguma vantagem de fazer o acima em uma árvore b +?

Por que não usar árvores b em vez de árvores b + em todos os lugares, pois intuitivamente elas parecem muito mais rápidas?

Quero dizer, por que você precisa replicar a chave (dados) em uma árvore b +?

database data-structures simplfuzz
fonte
37
Eu acho que o que eles estão dizendo é "Árvore B" vs. Árvore B +. Eles significam um hífen, não um sinal de menos.
stu

Respostas:

421

A imagem abaixo ajuda a mostrar as diferenças entre as árvores B + e as árvores B.

Vantagens das árvores B +:

  • Como as árvores B + não têm dados associados aos nós internos, mais chaves podem caber em uma página da memória. Portanto, exigirá menos falhas de cache para acessar os dados que estão em um nó folha.
  • Os nós das folhas das árvores B + estão vinculados, portanto, fazer uma varredura completa de todos os objetos em uma árvore requer apenas uma passagem linear por todos os nós das folhas. A árvore AB, por outro lado, exigiria uma travessia de todos os níveis da árvore. Esse percurso de árvore inteira provavelmente envolverá mais falhas de cache do que o percurso linear das folhas B +.

Vantagem de árvores B:

  • Como as árvores B contêm dados com cada chave, os nós acessados ​​com frequência podem ficar mais próximos da raiz e, portanto, podem ser acessados ​​mais rapidamente.

Árvore B e B +

Rose Perrone
fonte
2
Existe alguma restrição ao número de entradas no nó da folha?
TLE
38
@TLE Boa pergunta! Sim. Um disco rígido acessa no mínimo uma página de memória de cada vez, portanto, queremos encaixar todos os ponteiros em uma única página de memória. Queremos exigir apenas uma leitura de disco por acesso em folha, portanto, não queremos atribuir mais do que o tamanho da página de ponteiros a uma folha. Se preenchermos uma folha com um tamanho de página de ponteiros, e desejarmos adicionar outro ponteiro a essa folha, criaremos dois filhos desse nó e forneceremos metade dos ponteiros da folha para cada novo filho. Obviamente, pode haver alguma mudança de ordem para garantir que a altura da árvore seja mantida no mínimo. Isso ajuda?
21119 Rose Perrone
o último ponteiro de cada nó folha da árvore B deve apontar para o próximo nó folha, certo?
007 camino
8
Sinto muito por esbarrar em um tópico tão antigo, mas o comentário do @ Babyburger sobre como o comentário do camino estava correto não é realmente verdade; de fato, uma árvore B não tem nós de folhas conectados. A B +, com certeza.
Jason
Obrigado pela excelente resposta, qual é um caso de uso em que uma varredura completa dos objetos seria necessária em uma árvore B / B + em um contexto de banco de dados? Como é usado principalmente para indexação, as pesquisas quase nunca precisam varrer toda a árvore corretamente e, em vez disso, percorrer o caminho do índice, está correto?
Siddhartha
113

A principal vantagem das árvores B + sobre as árvores B é que elas permitem incluir mais ponteiros para outros nós, removendo os ponteiros dos dados, aumentando assim o fanout e potencialmente diminuindo a profundidade da árvore.

A desvantagem é que não há saídas antecipadas quando você pode encontrar uma correspondência em um nó interno. Porém, como as duas estruturas de dados têm grandes fanouts, a grande maioria das suas correspondências ocorrerá nos nós das folhas, tornando a árvore B + em média mais eficiente.

Vic E
fonte
1
Prefiro a resposta de Jeff, porque enfatiza a diferença de eficiência ao fazer uma varredura completa.
21119 Rose Perrone
Estou realmente confuso porque atravessar uma árvore b usando uma travessia em ordem lerá todos os valores na ordem classificada no tempo O (n). Se cada nó da árvore tiver o tamanho ideal para o tamanho da página física, parece que as coisas não ficam mais ideais. Por outro lado, o custo para chegar ao primeiro valor (menor) em uma árvore b + é O (log n) e, depois, percorrer todas as folhas é O (n), de modo que o custo total é O (log n + n). Isso é mais trabalho e mais leituras de disco, o que faz sentido porque a árvore possui todos esses dados extras. Eu não entendo.
Eric
O que seria outra palavra para 'fanout' na frase acima?
Jorge Bucaran
3
@JorgeBucaran Fanout = número de arestas que sai de um nó
bantmen
33

As árvores B + são muito mais fáceis e com melhor desempenho para fazer uma varredura completa, como em todos os dados indexados pela árvore, uma vez que os nós dos terminais formam uma lista vinculada. Para fazer uma varredura completa com uma B-Tree, é necessário fazer uma travessia completa da árvore para encontrar todos os dados.

As árvores B, por outro lado, podem ser mais rápidas quando você faz uma busca (procurando por um dado específico por chave), especialmente quando a árvore reside na RAM ou em outro armazenamento sem bloco. Como você pode elevar nós comumente usados ​​na árvore, são necessárias menos comparações para obter os dados.

Jeff Mc
fonte
1
Você concorda que uma árvore B + seria usada para situações nas quais pode haver uma leitura seqüencial em todos os dados, portanto, será possível atravessar as folhas. Considerando que a árvore B seria ideal para situações de acesso aleatório?
perfil completo de JDPeckham
31
  1. Em uma árvore B, as chaves e os dados são armazenados nos nós internos ou nas folhas. Mas em uma árvore B +, os dados são armazenados apenas nos nós das folhas.
  2. A varredura completa de uma árvore B + é muito fácil, pois todos os dados são encontrados nos nós das folhas. A varredura completa de uma árvore B requer uma travessia completa.
  3. Em uma árvore B, os dados podem ser encontrados em nós folha ou nós internos. A exclusão de nós internos é muito complicada. Em uma árvore B +, os dados são encontrados apenas nos nós das folhas. A exclusão dos nós das folhas é fácil.
  4. A inserção na árvore B é mais complicada que a árvore B +.
  5. As árvores B + armazenam chaves de pesquisa redundantes, mas a árvore B não tem valor redundante.
  6. Em uma árvore B +, os dados do nó folha são ordenados como uma lista vinculada sequencial, mas em uma árvore B o nó folha não pode ser armazenado usando uma lista vinculada. Muitas implementações de sistemas de banco de dados preferem a simplicidade estrutural de uma árvore B +.
androidcodehunter
fonte
15

Exemplo dos conceitos de sistema do banco de dados

B + -árvore Árvore B +

árvore B correspondente Btree

camino
fonte
5
Eu não acho que uma árvore B tenha links para os filhos do nó. Por exemplo, forma o Clearview bucketpara o Mianus Bucket. Não faria muito sentido fazer isso de qualquer maneira, porque entre os dois você tem o Downtown bucketque muito deve ser pesquisado no caso de querer fazer uma Verificação de Índice em uma árvore B (requer retrocesso). Onde você conseguiu isso?
Evan Carroll
1
@EvanCarroll Database System Concepts 5, talvez você precisa confirmar com o autor :)
camino
11

Defina "muito mais rápido". Assintoticamente, eles são iguais. As diferenças estão em como eles usam o armazenamento secundário. Os artigos da Wikipedia sobre árvores B e árvores B parecem bastante confiáveis.

Charlie Martin
fonte
2
Eu concordo com Charlie. Como um nó de uma árvore B representa uma página ou bloco de memória secundária, a passagem de um nó para outro requer uma mudança de página demorada.
11

Adegoke A, Amit

Acho que um ponto crucial que falta às pessoas é a diferença entre dados e indicadores, conforme explicado nesta seção.

Ponteiro: ponteiro para outros nós.

Dados: - No contexto de índices de banco de dados, os dados são apenas mais um ponteiro para dados reais (linha) que residem em outro lugar.

Portanto, no caso da árvore B, cada nó possui três chaves de informações, ponteiros para dados associados às chaves e ponteiro para nós filhos.

Na árvore B +, o nó interno mantém chaves e ponteiros no nó filho, enquanto o nó folha mantém chaves e ponteiros nos dados associados. Isso permite mais número de chaves para um determinado tamanho de nó. O tamanho do nó é determinado principalmente pelo tamanho do bloco.

A vantagem de ter mais chave por nó é explicada bem acima, portanto, pouparei meu esforço de digitação.

Saket
fonte
10

As árvores B + são especialmente boas no armazenamento baseado em bloco (por exemplo: disco rígido). com isso em mente, você obtém várias vantagens, por exemplo (do alto da minha cabeça):

  • fanout alta / baixa profundidade: isso significa que você precisa obter menos blocos para acessar os dados. com os dados misturados com os ponteiros, cada leitura recebe menos ponteiros; portanto, você precisa de mais pesquisas para chegar aos dados

  • armazenamento em bloco simples e consistente: um nó interno possui N ponteiros, nada mais, um nó folha possui dados, nada mais. isso facilita a análise, depuração e até reconstrução.

  • alta densidade de chaves significa que os nós principais estão quase certamente no cache; em muitos casos, todos os nós internos são armazenados em cache rapidamente, portanto, apenas o acesso aos dados precisa ir para o disco.

Javier
fonte
2
principalmente para árvores in-memory; mas existem outras opções populares, como árvores preto-vermelho, listas de pulos e outras.
Javier
As árvores B também são projetadas para armazenamento baseado em bloco eficiente, limitando o número assintótico de acessos de nós. Caso contrário, se estiver usando um meio de armazenamento semelhante à memória com acesso aleatório, pode-se usar uma árvore binária de auto-equilíbrio, como uma árvore vermelho-preta, para obter melhores resultados.
Dionyziz
seu primeiro ponto não deveria dizer "menos procura" em vez de "mais procura". Menor profundidade -> menor procura
Jesse
1
@Jesse: alta fanout => baixa profundidade => menos procura, mas de dados e ponteiros de mistura meios menos ponteiros => baixo fanout => mais profundidade => mais procura
Javier
1
@AdegokeA: uma árvore B + tem dois tipos de nós: nós internos com apenas chaves e ponteiros, sem dados; e nós de folha, com dados e sem ponteiros. que permite o número máximo de chaves em cada nó interno. se você armazenar dados em um nó interno, poderá ajustar menos indicadores e sua árvore ficará mais alta.
Javier
5

Na Árvore B +, como apenas os ponteiros são armazenados nos nós internos, seu tamanho se torna significativamente menor que os nós internos da árvore B (que armazenam os dados + chave). Portanto, os índices da árvore B + podem ser buscados no armazenamento externo em uma única leitura de disco, processada para encontrar o local do destino. Se for uma árvore B, é necessária uma leitura do disco para cada processo de tomada de decisão. Espero ter esclarecido meu argumento! :)

VS7
fonte
4

**

A principal desvantagem do B-Tree é a dificuldade de atravessar as chaves seqüencialmente. A Árvore B + retém a propriedade de acesso aleatório rápido da Árvore B, permitindo também o acesso sequencial rápido

** ref: Estruturas de Dados Usando C // Autor: Aaro M Tenenbaum

http://books.google.co.in/books?id=X0Cd1Pr2W0gC&pg=PA456&lpg=PA456&dq=drawback+of+B-Tree+is+the+diffitivity+of+Traversing+the+keys+sequentially&source=bl&ots=pGcPQSEJMS&sig= F9MY7zEXYAMVKl_Sg4W-0LTRor8 & hl = pt-BR & sa = X & ei = nD5AUbeeH4zwrQe12oCYAQ & ved = 0CDsQ6AEwAg # v = onepage & q = desvantagem 20% de% 20B-Tree% 20is% 20% 20d%

Kapil Kumar
fonte
1
Esta deveria ter sido a resposta correta. Em resumo: localidade de referência.
Theodore Zographos
2

Tomemos um exemplo - você tem uma tabela com enormes dados por linha. Isso significa que toda instância do objeto é grande.

Se você usa a árvore B aqui, passa a maior parte do tempo digitalizando as páginas com dados - o que é inútil. Nos bancos de dados, esse é o motivo do uso de Árvores B + para evitar a verificação de dados do objeto.

Árvores B + separam chaves dos dados.

Mas se o tamanho dos seus dados for menor, você poderá armazená-los com a chave, que é o que a árvore B faz.

Amit
fonte
1
"Se você usa a árvore B aqui, passa a maior parte do tempo digitalizando as páginas com dados" - não é necessário. Os nós da árvore B podem manter apenas "ponteiros" nos dados do disco, não nos dados em si.
TT_
2

A principal diferença entre a árvore B e a árvore B + é que a árvore B elimina o armazenamento redundante dos valores das chaves de pesquisa. Como as chaves de pesquisa não são repetidas na árvore B, talvez não seja possível armazenar o índice usando menos nós da árvore No entanto, como a chave de pesquisa que aparece nos nós não folheados não aparece em nenhum outro lugar na árvore B, somos forçados a incluir um campo de ponteiro adicional para cada chave de pesquisa em um nó não foliar. Existem vantagens de espaço para a árvore B, pois a repetição não ocorre e pode ser usada para índices grandes.

Maria
fonte
1
Interessante, os pensamentos sobre repetição são únicos entre as respostas aqui e fazem mais sentido do que a travessia em ordem da árvore b +, sendo mais eficiente do que a travessia em ordem da árvore b. Tanto quanto eu posso dizer, isso não está certo, ou não toda a história, pois a ordem de uma árvore b é O (n) e encontrar o menor nó em uma árvore b + é O (log n) e, em seguida, atravessar cada folha é O (n) além disso. No entanto, se você estava indexando algo com um pequeno intervalo de valores, como um campo booleano, a árvore b + faz muito mais sentido do que uma árvore b devido ao seu tratamento duplicado.
Eric
1

Uma árvore B + é uma árvore balanceada, na qual todo caminho da raiz da árvore até uma folha tem o mesmo comprimento e cada nó não-folha da árvore tem entre [n / 2] e [n] filhos, onde n é fixo para uma árvore em particular. Ele contém páginas de índice e páginas de dados. As árvores binárias têm apenas dois filhos por nó pai, as árvores B + podem ter um número variável de filhos para cada nó pai

Vivek Rakholiya
fonte
1
Apenas para maior clareza, as árvores B não são binárias. De fato, as árvores B e B + estão mais próximas umas das outras na construção e no uso do que as árvores binárias. Os artigos wiki pode ajudar a limpar as definições - árvore B + , B Árvore e árvore binária
uutsav
1

Um possível uso das árvores B + é que elas são adequadas para situações em que a árvore cresce tanto que não cabe na memória disponível. Portanto, você geralmente espera fazer várias E / Ss.
Muitas vezes acontece que uma árvore B + é usada mesmo quando ela se encaixa na memória e, em seguida, seu gerenciador de cache pode mantê-la lá permanentemente. Mas este é um caso especial, não o geral, e a política de armazenamento em cache é separada da manutenção da árvore B +, como tal.

Além disso, em uma árvore B +, as páginas folha são vinculadas juntas em uma lista vinculada (ou lista duplamente vinculada), que otimiza as travessias (para pesquisas de intervalo, classificação etc.). Portanto, o número de ponteiros é uma função do algoritmo específico usado.

programador de pilha
fonte
Isto é, em resposta à pergunta que por que não usar árvores-B em vez de árvores B + em todos os lugares :)
programador pilha
3
Mas você descreveu apenas um lado, tanto quanto sabemos, com sua resposta, as árvores-b podem funcionar exatamente da mesma maneira. O OP pediu para explicar as diferenças e você falou apenas de um e não do outro. Você não pode ter um diagrama de Venn com um círculo!
Malfist 15/05/09