Como são índices regulares e compostos implementado em RDB?

Question

Em bases de dados como MySQL ou Oracle, como são índices implementado? Acho índices regulares são armazenados como B-árvores, mas não conseguiu encontrar nada sobre índices compostos que índice em várias colunas. Estou procurando os nomes das estruturas de dados usadas para que eu possa pesquisá-las.

De modo mais geral, onde posso encontrar mais informações sobre tais detalhes de implementação de banco de dados? Eu estou indo tomar um curso sobre que muito mais tarde na universidade, mas estou curioso agora.

Answer 1

índices compostos também usar B-Trees, eles só concatenar as colunas indexadas para determinar a chave. Como um nó lado, sabe Oracle também outros tipos de índice, isto é, índices de bitmap. Mas isso não depende do número de colunas indexadas.

Answer 2

B-árvores. Cada índice é armazenado como uma árvore-B -. Mesmo os compostos

Se você estiver olhando para fazer mais pesquisas sobre como os índices são organizados, olhar para B árvores + e B * árvores. Para o SQL Server, de Kalen Delaney Dentro SQL Server: O mecanismo de armazenamento é uma excelente livro sobre as porcas e parafusos do SQL Server, incluindo a sua organização índice. Então você deve definitivamente verificar isso.

A Pontos comentarista fora que a Oracle pode usar índices de bitmap, que são estruturados de forma muito diferente do que árvores-B, mas esses são raramente usados ??para bancos de dados relacionais tradicionais - eles são usados ??com mais freqüência para aplicações do tipo OLAP e, em casos onde precisam de acesso rápido em um grupo não-seletivo de dados.

EDIT: SQL Server, por exemplo, usa agora columnstore Índices . Se você fazer qualquer trabalho com grandes cargas de trabalho de tipo BI, é definitivamente vale a pena olhar para estes, como eles armazenam seus dados de uma forma totalmente diferente de um B-Tree.

SQL Server também usa um mecanismo diferente agora para memória tabelas optimizadas bem, e é algo que é muito útil para consultas do tipo OLTP.