Se um índice rowstore é armazenado em uma estrutura de dados b-tree, que tipo de estrutura de dados é usada para um índice columnstore? [duplicado]

Geralmente pensamos em um índice como uma forma de encontrar rapidamente todas as referências a uma determinada informação. Em um livro didático dado um tópico, podemos encontrar todas as páginas que mencionam esse tópico. Em um banco de dados dado um valor de coluna, podemos encontrar todas as linhas que possuem esse valor.

Chamar um columnstore de "índice" nesse sentido é um pouco impróprio. Não se destina a fornecer pesquisa rápida para as linhas de um valor de coluna específico. Em vez disso, destina-se a fornecer rapidamente resultados de agregações em grandes conjuntos de dados. Como tal, é um formato de dados em si. O armazenamento de dados colunar, às vezes chamado de modelo de armazenamento decomposicional (DSM), é bem conhecido e venerável . Muitos DBMS proprietários e de código aberto o oferecem.

A ideia básica de um armazenamento de coluna é que os valores de uma coluna sejam armazenados de forma contígua no disco. Em seguida, um agregado nessa coluna pode extrair com eficiência essa coluna, e somente essa coluna, do disco, reduzindo o número de blocos de disco que devem ser lidos. Além disso, como todos os valores de dados em um bloco são do mesmo domínio, a compactação nesse bloco provavelmente será muito eficiente, reduzindo ainda mais o número de blocos necessários. A compactação pode ser muito melhor do que um ZIP genérico - dicionários, codificações de comprimento de execução e delta podem ser usados.

Por várias razões, é melhor dividir as linhas em grandes grupos antes de comprimi-las e armazená-las. O SQL Server chama esses grupos de "grupos de linhas", que são compostos de "segmentos de coluna". Cada grupo de linhas contém pouco mais de um milhão de linhas. Quando os segmentos são construídos, o servidor extrai alguns metadados, como min, max e (talvez) soma para essa coluna. Esses metadados às vezes são chamados de mapas de zona. Em tempo de execução, esses mapas de zonas podem ser comparados aos predicados de consulta e, se o predicado não estiver entre os valores mínimo e máximo do segmento, o processamento pode evitar totalmente a leitura desses blocos do disco. Isso é chamado de eliminação de segmento e é análogo à eliminação de partição. Além disso, algumas perguntas podem ser respondidas diretamente dos mapas de zonas, por exemplo, "selecione min(coluna) da tabela"

Eu observaria que B-Trees não é a única estrutura para indexação de rowstores, é apenas a única disponível para desenvolvedores de banco de dados usando SQL Server.