Graduação em Ciência da Computação Centro de Informática

...

B.1 Definições

B.2 Propriedades

---------------------------------------------------------------

1. Introdução

A World Wide Web pode ser vista como uma biblioteca virtual, que contém uma grande quantidade e variedade de informações. Os mecanismos de busca fazem o papel de um catálogo dessa grande biblioteca, eles copiam partes da Web e as indexam para ajudar os usuários a encontrarem informações de forma mais rápida do que simplesmente “navegando” pela Web (Brewington et al, 2000).

Para recuperar informação contida na base de dados, gerada a partir da cópia local de um subconjunto da WWW pelos mecanismos de busca, é necessária a criação de estruturas de acesso auxiliares, chamadas de Índices. Esses índices têm como função aumentar a velocidade na qual a informação é recuperada em resposta a consultas. Essas estruturas fornecem um caminho secundário de acesso, proporcionando uma maneira alternativa de localizar registros sem afetar as posições físicas do registro na base de dados. Os índices fornecem uma maneira eficiente de acessar os dados da base a partir de uma chave candidata[4], e é nesta chave (campo) que a construção do índice se baseia.

Para atender a uma consulta em que se procura um ou mais registros, primeiramente o sistema acessa o índice, e neste há um ponteiro indicando a localização do bloco ou blocos na base de dados onde o(s) registro(s) se encontra(m).

Há várias estruturas de dados que se propõem a resolver esse problema. Os tipos mais comuns de índices são os baseados em arquivos ordenados (índices de um nível), em árvores (índices multinível) e índices baseados em hashing.

Índices baseados em arquivos ordenados usam a mesma idéia dos índices remissivos encontrados em livros, onde é fornecida uma lista de palavras importantes, em ordem alfabética, indicando uma lista de páginas onde há ocorrências daqueles termos. Sem o auxílio do índice remissivo, ter-se-ia que olhar página por página do livro a procura da palavra desejada.

As estruturas de dados que se baseiam nesta abordagem funcionam analogamente: o índice armazena cada valor do campo a ser indexado (chave candidata ou campo indexado) assim como uma lista de ponteiros para os endereços de todos os blocos do arquivo da base de dados onde aqueles atributos se localizam. O campo indexado se encontra ordenado, podendo assim ser feita uma busca binária no índice.

Uma implementação de índice baseadas em arquivos ordenados bastante difundida entre mecanismos de busca é o arquivo invertido (Frakes, W. B et al., 1992), o qual consiste em registros de tamanho fixo contendo o ponteiro para o endereço do bloco onde se encontra a lista de ocorrências do atributo indexado. Ao invés de se realizar uma busca binária no índice, é feito um acesso direto visto que é possível localizar o ponteiro certo através de uma conta baseada no tamanho fixo do registro e no atributo indexado. Embora essa abordagem tenha acessos a disco da ordem de O(2), uma vez que só dois acessos a disco são necessários para se recuperar a informação desejada, ela se torna de complicada manutenção quando a base cresce muito, pois sempre tem-se que reconstruir o índice novamente.

Estruturas de índices baseadas em árvore e hashing não precisam ser reconstruídas todas as vezes que uma atualização se faz necessária. Este trabalho deter-se-á a descrever e demonstrar a aplicação de estruturas de dados baseadas em árvores e em hashing em um mecanismo de busca.

O restante deste documento está organizado da seguinte forma: no Capítulo 2 são definidas estruturas de dados baseada em árvores (estruturas multinível). No Capítulo 3, é definida uma estrutura de dado baseada em hashing, a Extensible Hashtable (Fagin et al., 1979). As implementações das estruturas de dados encontram-se no Capítulo 4. No Capítulo 5, é discutida a aplicação, em um mecanismo de busca, das implementações das estruturas estudadas neste documento. As conclusões sobre os resultados obtidos, problemas encontrados durante o trabalho, e indicações de trabalhos futuros são apresentadas no capítulo 6.

---------------------------------------------------------------

2. Índices Multinível

É possível construir-se índices multinível a partir de índices de apenas um nível. Por exemplo, um arquivo de índice ordenado de chaves distintas pode ser chamado de primeiro nível, e este apontar para um outro arquivo de índice ordenado. Como o índice do primeiro nível é um índice primário, suas chaves podem ser ponteiros para cada bloco do índice do segundo nível. Esse processo pode ser aplicado indefinidamente.

2.1 Índices Dinâmicos Multinível

Enquanto índices de um ou dois níveis auxiliam em acelerar o processo de recuperação de informação, existem estruturas de dados mais genéricas que são comumente implementadas em SGBDs comerciais por serem mais flexíveis e escaláveis. A estrutura de dados mais comum para esse propósito é a B-Tree (Bayer, R e McCreight, E., 1972). A B-Tree, em essência:

- Automaticamente mantém os níveis balanceados para a quantidade de dados que está sendo indexada, e

- Gerencia o espaço usado por seus blocos para que ele sempre esteja ocupado com pelo menos a metade de sua capacidade.

Uma variação desta estrutura que também será apresentada neste trabalho será a B+Tree (Wedekind, H., 1974), que hoje é bastante utilizada em SGBDs (Garcia-Molina, H. et al, 2000) e em alguns sistemas de arquivos (XFS, 1994; JFS, 2000).

2.2 B-Trees

B-Trees são árvores de busca desenvolvidas para trabalharem em discos magnéticos ou qualquer outro dispositivo de armazenamento de acesso direto em memória secundária. Em uma aplicação comum de uma B-Tree, a quantidade de dados é tão grande que provavelmente não caberia na memória principal. A B-Tree copia blocos específicos para a memória principal quando necessário e os grava no disco se os blocos tiverem sido alterados.

As B-Trees são similares às red-black trees (Bayer, R., 1972), mas sua estrutura minimiza operações de I/O. A diferença mais significante entre a B-Tree e a red-black tree está no fato de que cada nó da B-Tree pode ter vários filhos, ou seja, o branching factor da B-Tree pode ser bastante grande. B-Trees