4. Estruturas de Dados e Métodos de Acesso Multidimensionais

As Árvores-B foram muito importantes para a indústria de bancos de dados. Praticamente todos os SGBDs, dos anos 70 até hoje, implementam alguma uma variação dessas árvores como principal método de indexação. Esse tipo de árvore encontra-se presente em SGBDs relacionais como MySQL, PostgreSQL, Oracle e Microsoft SQL Server, bem como em sistemas não-relacionais, como Apache CouchDB, MongoDB, Oracle Berkeley DB, OrientDB e Neo4J, entre outros. No entanto, essa estrutura suporta de maneira eficiente dados unidimensionais.

Quando tratamos de dados multidimensionais, como no caso das geometrias associadas às feições geográficas, precisamos de estruturas de dados capazes de responder buscas num espaço multidimensional. Na literatura encontramos diversas estruturas de índices para essa finalidade [17]. Nesta seção iremos aprender sobre estruturas como as Árvores-R [18] e suas variantes [4], as Árvore-k-d [5] [6] e as Quad-trees [15] [37].

• 4.1. Aproximações Geométricas
• 4.2. Árvores-R
• 4.3. Árvores-R no PostgreSQL com PostGIS
• 4.4. Árvores de Partição do Espaço
• 4.5. Árvores de Partição do Espaço no PostgreSQL com PostGIS
• 4.6. Busca dos Vizinhos Mais Próximos
• 4.7. Considerações Finais