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

[pic 1]

Universidade Federal de Pernambuco

Graduação em Ciência da Computação

Centro de Informática

[pic 2]

[pic 3]

Aluno: Mariano Cravo Teixeira Neto ([e-mail])

Professora: Ana Carolina Salgado ([e-mail])

Julho de 2001

---

Resumo

Devido ao desenvolvimento tecnológico dos dispositivos de armazenamento digital, as bibliotecas digitais tornaram-se capazes de disponibilizar grandes volumes de dados. A World Wide Web, com seus bilhões de páginas, pode ser vista como uma grande biblioteca onde seus documentos são páginas web. Nessa coleção, cuja quantidade de documentos é enorme, torna-se complexo procurar documentos pela inviabilidade de varrer cada documento, uma vez que é necessário satisfazer a restrições de tempo.

Para atender a essas restrições, diversas ferramentas de busca na Internet (como o Google^[1], Radix^[2] e Altavista^[3]) fazem uso de estruturas de dados especialmente desenvolvidas para recuperação de documentos. Tais ferramentas de busca mantêm um índice local que torna possível procurar e recuperar documentos armazenados em memória secundária. Esse índice pode ser construído através do uso de diferentes estruturas, como arquivos de acesso direto, hashtables e árvores.

O objetivo deste trabalho é estudar e aplicar estruturas de dados desenvolvidas para indexar documentos armazenados em memória secundária que podem chegar à ordem de grandeza de 109 chaves em um ambiente de busca para Internet.

Para tal, serão implementadas e avaliadas estruturas de índices dinâmicos, como B-Trees e variantes, e estruturas de hashing como Extensible Hashtables. Dessa maneira será possível realizar experimentos com o intuito de avaliar o desempenho de cada uma dessas estruturas de índice.

---

Agradecimentos

        Agradeço, em primeiro lugar, à professora Ana Carolina Salgado, pela orientação e interesse no desenvolvimento do meu trabalho. Agradeço, também, ao Bright, atual Grupo Radix, Pedro Falcão, e ao professor Silvio Meira, por terem acreditado na minha capacidade profissional. Ainda, agradeço a Luciano Barbosa, Thiago Santos e Fernando Trinta pelas sugestões sobre a produção deste documento, e a Marcelo Nery, Oscar Gomes e Saulo Medeiros pela ajuda durante a implementação deste trabalho.

---

Índice

RESUMO        

AGRADECIMENTOS        

ÍNDICE        

1. INTRODUÇÃO        

2. ÍNDICES MULTINÍVEL        

2.1 Índices Dinâmicos Multinível        

2.2 B-Trees        

2.2.1 B-Tree: Definições        

2.2.2 Características da B-Tree        

2.3 B+Tree        

2.3.1 B+Tree: Definições        

2.3.2 Características da B+Tree        

3. ÍNDICES DINÂMICOS BASEADOS EM HASHING        

3.1 Definições        

3.1.1 Busca        

3.1.2 Inserção e Splitting        

3.2 Características        

4. IMPLEMENTAÇÕES DOS ÍNDICES        

4.1 Linguagem Utilizada        

4.2 Características        

4.2.1 B-Tree        

4.2.2 B+Tree        

4.2.3 Extensible Hashtable        

5. APLICAÇÃO DOS ÍNDICES EM UM MECANISMO DE BUSCA        

5.1 Arquitetura de um Mecanismo de Busca        

5.2 Base de Índices        

5.2.1 Servidor de Códigos        

5.2.2 Listas de Posições (Position Lists)        

6. CONCLUSÕES E TRABALHOS FUTUROS        

REFERÊNCIAS        

APÊNDICE A: INVERTED FILES        

Inverted File (Arquivo Invertido)        

APÊNDICE B: RED-BLACK TREES        

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.