Á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.

Introdução

• A discussão a seguir menciona, ocasionamente, os dois tipos de memória de um computador típico:  a memória interna (ou principal) e a memória externa (ou secundária, usualmente um disco rígido ou memória de estado sólido).  A memória interna tem alta velocidade mas pouca capacidade enquanto a memória externa tem baixa velocidade mas grande capacidade.  Vamos nos referir à primeira como memória rápida e à segunda como memória lenta.  Suporemos que o tempo de acesso à memória rápida é desprezível quando comparada com o tempo de acesso à memória lenta.
• Suponha dada uma tabela de símbolos ordenada T. Imagine que T tem um número enorme de chaves, tão grande que não cabe na memória rápida do computador. Para manipular essa tabela de símbolos, é preciso dividí-la em segmentos T₁, T₂, … , T_n, cada segmento sendo uma tabela de símbolos pequena o suficiente para caber com folga na memória rápida. É natural definir os segmentos de modo que todas as chaves em um segmento sejam menores que todas as chaves no segmento seguinte.
• Para procurar uma chave nessa tabela de símbolos fracionada precisamos de um índice, ou seja, uma tabela de símbolos auxiliar que indique em qual dos segmentos T₁, T₂, … , T_n está a chave procurada. Diremos que a tabela de símbolos auxiliar é interna e as tabelas de símbolos T₁ , T₂, … , T_n são externas.
• A tabela de símbolos interna, digamos A, é organizada da seguinte maneira. As chaves de A são k₁, k₂, … , k_n, sendo k_i a menor chave de T_i . O valor que a tabela A associa com a chave k_i é uma referência a T_i.
• Para procurar por uma chave x, escolha o maior i tal que k_i ≤ x, use a tabela interna A para localizar T_i , e então procure por x em T_i . Se um tal i não existe, x não está na tabela de símbolos original T.
• Que acontece se a tabela interna A for grande demais para caber na memória rápida?  Em outras palavras, que acontece se A for muito maior que qualquer T_i ?   Nesse caso, aplique a A a mesma ideia de segmentação que aplicamos a T e repita, recursivamente, se necessário.  Isso resulta em uma árvore cujos nós são tabelas de símbolos. Esta é a origem do conceito de árvore B.
• Convém impor restrições ao número de chaves em cada nó da árvore. Escolha um inteiro positivo par M, e organize as coisas de modo que cada nó da árvore tenha no máximo M−1 chaves e no mínimo M/2 chaves. (A raiz é excepcional: basta que ela tenha duas ou mais chaves.)
• Exemplo de uma árvore B com M = 6.  As chaves são *, B, C, …  , X, Y. As chaves são comparadas em ordem alfabética (assim, * é a menor das chaves.)  Um nó com m chaves é chamado m-nó.

  

• Nossos exemplos usam valores pequenos de M, como 4 ou 6.  Um valor mais realistas pode ficar em torno de 1000.  Na prática, cada nó é um arquivo (= file), armazenado na memória lenta, ou uma página na teia WWW.

Árvores B

• Definição (Bayer e McCreight, 1972):  Para qualquer inteiro positivo par M, uma árvore B (B-tree) de ordem M é uma árvore com as seguintes propriedades:
  • cada nó contém no máximo M−1 chaves,
  • a raiz contém no mínimo 2 chaves e cada um dos demais nós contém no mínimo M/2 chaves,
  • cada nó que não seja uma folha tem um filho para cada uma de suas chaves,
  • todos os caminhos da raiz até uma folha têm o mesmo comprimento (ou seja, a árvore é perfeitamente balanceada).
• Uma árvore B de ordem 4 é essencialmente uma árvore 2-3 (embora existam algumas difereças que destacaremos adiante).
• Aplicações. Árvores B são a estrutura subjacente a muitos sistemas de arquivos e bancos de dados.  Por exemplo,
  • o sistema de arquivos NTFS do Windows,
  • o sistema de arquivos HFS do Mac,
  • os sistemas de arquivos ReiserFS, XFS, Ext3FS, JFS do Linux, e
  • os bancos de dados ORACLE, DB2, INGRES, SQL e PostgreSQL.

Nós versus páginas

• Usaremos a palavra página para designar um nó de uma árvore B.  As folhas da árvore são páginas externas e os demais nós são páginas internas.
• As páginas externas armazenam a TS do cliente. Elas associam chaves com valores do cliente.
• As páginas internas implementam as TSs auxiliares. Elas associam chaves com outras páginas (internas ou externas) da maneira já indicada acima:  o valor associado com uma chave k em uma página interna A é uma referência à página que é raiz da subárvore que contém todas as chaves maiores-ou-iguais a k e (se k não é a última chave) menores que a chave seguinte da página A.
• Conjuntos ordenados: Deste ponto em diante, para simplificar a discussão, vamos tratar apenas de árvores B que implementam a abstração SET, ou seja, um conjunto de chaves comparáveis sem valores associados às chaves.
• As páginas de nossas árvores B serão implementadas por uma classe Page, bem mais rica que a classe Node que usamos para representar os nós de árvores binárias. Além de variáveis de instância, cada Page terá vários métodos para operar sobre a página.  Eis a API da classe:

  public class Page<Key>
  	Page(boolean bottom)	cria e abre uma página (externa ou interna)
  void	close()	fecha esta página
  void	insert(Key key)	insere a chave key nesta página (externa)
  void	enter(Page p)	insere nesta página (interna) um par que     associa a menor chave de p com p
  boolean	isExternal()	esta página é externa?
  boolean	holds(Key key)	a chave key está nesta página?
  Page	next(Key key)	a subárvore que poderia conter key
  boolean	hasOverflowed	esta página transbordou (já tem M chaves)?
  Page	split()	transfere as maiores M/2 chaves desta página     para uma nova página
  Iterable<Key>	keys()	iterador para as chaves desta página

• Documentação adicional (que deveria, a rigor, fazer parte da API):
  • O construtor Page() cria uma nova página. A página é externa se o argumento for true.
  • A operação de abertura de uma página traz a página da memória lenta para a rápida.
  • A operação close() transfere a página da memória rápida para a lenta.
  • Se this é uma página externa (que já está aberta), a operação this.insert(key) acrescenta a this a chave key. Com isso, a página this pode violar o limite de M−1 chaves, mas isso será corrigido por uma futura invocação de split().
  • Se this é uma página interna (aberta) e p é uma página qualquer, a operação this.enter(p) abre a página p e insere na página this o par (key, p), sendo key a menor chave em p.
  • Se this é uma página interna, a operação this.next(key) produz a página associada a key em this.
  • A operação split() é invocada quando a página já tem M chaves (ou seja, já transbordou). A operação cria uma nova página para a qual são transferidas as M/2 maiores chaves da página original. A nova página é externa se a original era externa e interna em caso contrário.
• Implementar a classe Page é um bom exercício.

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

• Exemplo. Busca pela chave E em uma árvore B de ordem 6 que armazena as chaves *, B, C, …  , W, X.  A menor das chaves é * e as demais chaves são comparadas alfabeticamente:

  

• Exemplo. Inserção da chave A em uma árvore B de ordem 6 que armazena as chaves *, B, C, … , W, X.  A menor das chaves é * e as demais chaves são comparadas alfabeticamente:

  

Implementação de árvore B

• A inserção de uma chave é mais complexa quando a nova chave é menor que a menor chave da árvore.  Para evitar esse caso especial, faremos com que a árvore tenha, desde sua criação, uma chave sentinela menor que qualquer chave que um cliente venha a inserir (veja a chave * nos exemplos acima).
• Algoritmo 6.12: A classe BTreeSET implementa uma TS do tipo SET (sem valores associados às chaves, portanto).  A operação de inserção é chamada add() e a operação de busca é chamada contains(). Suporemos que o cliente jamais insere uma chave menor que a chave mínima da árvore:

  public class BTreeSET<Key extends Comparable<Key>> {
  
     private Page root = new Page(true);
  
     public BTreeSET(Key sentinel) { 
        add(sentinel); 
     }
  
     public boolean contains(Key key) { 
        return contains(root, key); 
     }
  
     private boolean contains(Page h, Key key) {
        if (h.isExternal()) return h.holds(key);
        return contains(h.next(key), key);
     }
  
     public void add(Key key) {
        add(root, key);
        if (root.hasOverflowed()) {
           Page lefthalf = root;
           Page righthalf = root.split();
           root = new Page(false);
           root.enter(lefthalf);
           root.enter(righthalf);
        }
     }
  
     public void add(Page h, Key key) {
        if (h.isExternal()) { 
           h.insert(key); 
           return; 
        }
        Page next = h.next(key);
        add(next, key);
        if (next.hasOverflowed())
           h.enter(next.split());
        next.close();
     }
  }
  

• Documentação adicional (que deveria, a rigor, fazer parte da API de BTreeSET):
  • A operação privada add() com argumentos h e key insere a chave key na subárvore cuja raiz é h. (Supõe-se que key não é menor que a chave mínima da árvore.)  A chave é inserida na página externa apropriada (e isso pode levar à criação uma nova página externa). Na subárvore resultante, todas as páginas terão entre M/2 e M−1 chaves exceto a página h, que poderá ter até M chaves.
  • A operação pública add() com argumento key insere a chave key na árvore. (Supõe-se que key não é menor que a chave mínima da árvore.)  A chave é inserida na página externa apropriada (e isso pode envolver a criação uma nova página externa). Se a raiz transbordar, ela será dividida em duas e uma nova raiz será criada tendo como filhos as duas metades da raiz original.
• Exemplo. A figura mostra a evolução do conjunto de páginas externas de uma árvore B de ordem 8. Cada linha da figura (há mais de 160 delas) mostra o resultado da inserção de uma chave em alguma página externa. Cada pequena barra horizontal representa uma página externa; a porção preta da barra é a parte ocupada da página e a porção branca é a parte desocupada. Cada barra vermelha representa uma página externa cheia que está prestes a receber uma nova chave e transbordar.  Começamos com uma só página externa (cheia) e terminamos com 22 páginas externas. A figura tem alguns erros que cabe a você encontrar.

  

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 M e N.
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

• O consumo de tempo de cada operação na memória rápida é muito menor que o tempo necessário para trazer uma página da memória lenta para a rápida ou levar uma página da memória rápida para a lenta. Assim, faz sentido ignorar o custo das operações na memória rápida e contar apenas o número de sondagens.
• Uma sondagem é o primeiro acesso a uma página durante uma busca ou inserção.
• Proposição. Uma busca ou inserção em uma árvore B de ordem M com N chaves envolve entre  log_M N  e  log_M/2 N  sondagens.
• Prova: O número de sondagens é igual à altura da árvore. No melhor caso, todas as páginas internas têm M−1 filhos. No pior caso, todas as páginas internas (exceto a raiz) têm M/2 filhos.
• Se M é da ordem de 1000, por exemplo, a altura da árvore não pasa de 4 se N for menor que 62 bilhões.

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.