Árvores B (B-trees)

Livro de Sedgewick e Wayne: seção 6.2 (B-trees), cap.6, p.866-874.  Website do livro: resumo da sec.6.2 (ainda não está pronto), slides.  O código BTree.java no website algs4.cs.​princeton.edu/​code/ é diferente do código BTreeSET.java no livro impresso.

Árvores B são estruturas usada para implementar TSs (tabelas de símbolos) muito grandes. Uma árvore B pode ser vista como um índice (análogo ao índice de um livro) para uma coleção de pequenas TSs:  o índice diz em qual das pequenas TSs está a chave que você procura. Pode-se dizer que uma árvore B é uma TS de TSs.

Resumo:

Pré-requisitos:

Introdução

Árvores B

Nós versus páginas

Exercícios 1

  1. (SW 6.15)  Escreva uma implementação da classe Page que represente cada página como um objeto BinarySearchST.  Suponha que as páginas são arquivos no seu disco rígido. Repita o exercício supondo que as páginas são arquivos na teia WWW.

Busca e inserção

Implementação de árvore B

Exercícios 2

  1. O código de BTreeSET funciona corretamente se as páginas têm menos que M/2 chaves ou a raiz tem menos que 2 chaves?
  2. (SW 6.16)  Estenda BTreeSET a uma implementação BTreeST mais geral, que associe valores a chaves. Inclua as operações min(), max(), floor(), ceiling(), deleteMin(), deleteMax(), select(), rank(), e as versões de dois argumentos de size() e get().
  3. (SW 6.17)  Use StdDraw para visualizar a evolução de uma árvore B à medida que ela cresce, como no exemplo acima.
  4. (SW 6.21)  Escreva um programa que calcule o número médio de páginas externas de uma árvore B de ordem M construída com N inserções aleatórias a partir de uma árvore vazia. Execute seu programa para valores razoáveis de MN.
  5. (SW 6.22)  Se seu sistema tem memória virtual, projete e execute experimentos para comparar o desempenho de árvores B com o desempenho da busca binária para buscas aleatórias em uma TS enorme.

Desempenho

Exercícios 3

  1. (SW 6.23)  Para a implementação de Page que usa BinarySearchST (veja exercício SW 6.15), faça experimentos para determinar o valor de M que produz a busca mais rápida por chaves aleatórias em uma TS enorme implementada em uma árvore B. Restrinja os valores de M a múltiplos de 100.
  2. (SW 6.24)  Faça experimentos para comparar os tempos da busca aleatória em grandes tabelas de símbolos usando as seguintes implementações:  árvore B residente na memória rápida (usando o valor de M determinado na exercício SW 6.23), hashing com sondagem linear, árvores rubro-negras.

Perguntas e respostas