Como os bancos de dados armazenam valores de chave de índice (em disco) para campos de comprimento variável?

Contexto

Esta pergunta refere-se aos detalhes de implementação de baixo nível de índices nos sistemas de banco de dados SQL e NoSQL. A estrutura real do índice (árvore B +, hash, SSTable etc.) é irrelevante, pois a pergunta refere-se especificamente às chaves armazenadas em um único nó de qualquer uma dessas implementações.

fundo

Nos bancos de dados SQL (por exemplo, MySQL) e NoSQL (CouchDB, MongoDB, etc.), quando você cria um índice em uma coluna ou campo de dados do documento JSON, o que você realmente está fazendo com que o banco de dados faça é criar essencialmente uma lista classificada de todos os esses valores, juntamente com um arquivo, são deslocados para o arquivo de dados principal em que reside o registro referente a esse valor.

(Por uma questão de simplicidade, talvez eu esteja ignorando outros detalhes esotéricos de impls específicos)

Exemplo simples de SQL clássico

Considere uma tabela SQL padrão que possui uma chave primária int simples de 32 bits na qual criamos um índice; terminaremos com um índice em disco das chaves inteiras classificadas e associadas a um deslocamento de 64 bits no arquivo de dados em que o registro vive, por exemplo:

id   | offset
--------------
1    | 1375
2    | 1413
3    | 1786

A representação em disco das chaves no índice é mais ou menos assim:

[4-bytes][8-bytes] --> 12 bytes for each indexed value

Seguindo as regras básicas de otimização de E / S de disco com sistemas de arquivos e sistemas de banco de dados, digamos que você armazene chaves em blocos de 4KB no disco, o que significa:

4096 bytes / 12 bytes per key = 341 keys per block

Ignorando a estrutura geral do índice (árvore B +, hash, lista classificada etc.), lemos e gravamos blocos de 341 chaves por vez na memória e voltamos ao disco conforme necessário.

Consulta de exemplo

Usando as informações da seção anterior, digamos que uma consulta entre "id = 2", a pesquisa clássica do índice de banco de dados é a seguinte:

1. Leia a raiz do índice (neste caso, 1 bloco)
2. Pesquisa binária no bloco classificado para encontrar a chave
3. Obter o deslocamento do arquivo de dados do valor
4. Procure o registro no arquivo de dados usando o deslocamento
5. Retornar os dados para o chamador

Pergunta Setup ...

Ok, aqui é onde a pergunta se reúne ...

O passo 2 é a parte mais importante que permite que essas consultas sejam executadas no tempo O (logn) ... as informações precisam ser classificadas, mas você precisa ser capaz de percorrer a lista de maneira rápida ... mais especificamente, você deve ser capaz de pular para compensações bem definidas à vontade para ler o valor da chave de índice nessa posição.

Depois de ler no bloco, você deve poder saltar para a 170ª posição imediatamente, ler o valor-chave e ver se o que você está procurando é GT ou LT nessa posição (e assim por diante ...)

A única maneira de você pular os dados no bloco dessa maneira é se os tamanhos dos valores das chaves estiverem todos bem definidos, como no nosso exemplo acima (4 bytes depois 8 bytes por chave).

QUESTÃO

Ok, aqui é onde estou ficando preso com um design de índice eficiente ... para colunas varchar em bancos de dados SQL ou, mais especificamente, campos de forma totalmente livre em bancos de dados de documentos como CouchDB ou NoSQL, onde qualquer campo que você deseja indexar pode ser qualquer length Como você implementa os valores-chave que estão dentro dos blocos da estrutura de índice dos quais você constrói seus índices?

Por exemplo, digamos que você use um contador seqüencial para um ID no CouchDB e esteja indexando tweets ... você terá valores que vão de "1" a "100.000.000.000" depois de alguns meses.

Digamos que você construa o índice no banco de dados no dia 1, quando houver apenas 4 tweets no banco de dados, o CouchDB pode ficar tentado a usar a seguinte construção para os valores-chave dentro dos blocos de índice:

[1-byte][8-bytes] <-- 9 bytes
4096 / 9 = 455 keys per block

Em algum momento, isso é interrompido e você precisa de um número variável de bytes para armazenar o valor da chave nos índices.

O ponto é ainda mais evidente se você decidir indexar um campo de tamanho realmente variável, como um "tweet_message" ou algo assim.

Com as próprias chaves sendo de tamanho totalmente variável e o banco de dados não tendo como adivinhar inteligentemente algum "tamanho máximo de chave" quando o índice é criado e atualizado, como essas chaves são realmente armazenadas dentro dos blocos que representam segmentos dos índices nesses bancos de dados ?

Obviamente, se suas chaves são de tamanho variável e você lê um bloco de chaves, não apenas você não tem idéia de quantas chaves estão realmente no bloco, mas também não sabe como pular para o meio da lista para fazer um binário procure neles.

É aqui que estou ficando todo tropeçado.

Com campos de tipo estático nos bancos de dados SQL clássicos (como bool, int, char, etc.), entendo que o índice pode apenas pré-definir o comprimento da chave e cumpri-lo ... mas neste mundo de armazenamentos de dados de documentos, estou perplexo com a forma como eles estão modelando eficientemente esses dados no disco, de modo que ainda possam ser verificados no tempo O (logn) e agradeceriam qualquer esclarecimento aqui.

Entre em contato se precisar de esclarecimentos!

Atualização (resposta de Greg)

Por favor, veja meus comentários anexados à resposta de Greg. Depois de mais uma semana de pesquisa, acho que ele realmente encontrou uma sugestão maravilhosamente simples e com bom desempenho de que a prática é fácil de implementar e usar, ao mesmo tempo em que proporciona grandes vitórias de desempenho ao evitar a desserialização de valores-chave com os quais você não se importa.

Analisei três implementações de DBMS separadas (CouchDB, kivaloo e InnoDB) e todas elas lidam com esse problema desserializando o bloco inteiro na estrutura de dados interna antes de pesquisar os valores em seu ambiente de execução (erlang / C).

Isso é o que eu acho tão brilhante na sugestão de Greg; um tamanho normal de bloco de 2048 normalmente teria 50 ou menos deslocamentos, resultando em um bloco muito pequeno de números que precisariam ser lidos.

Atualização (possíveis desvantagens da sugestão de Greg)

Para melhor continuar esse diálogo comigo, percebi as seguintes desvantagens disso ...

1. Se cada "bloco" estiver com dados de deslocamento, você não poderá permitir que o tamanho do bloco seja ajustado na configuração posteriormente, pois poderá acabar lendo dados que não começaram com um cabeçalho corretamente ou um bloco que continha vários cabeçalhos.

2. Se você estiver indexando grandes valores de chave (digamos que alguém esteja tentando indexar uma coluna de char (8192) ou blob (8192)), é possível que as chaves não se encaixem em um único bloco e precisem ser excedidas em dois blocos lado a lado . Isso significa que seu primeiro bloco teria um cabeçalho de deslocamento e o segundo bloco começaria imediatamente com os dados principais.

A solução para tudo isso é ter um tamanho fixo de bloco de banco de dados que não é ajustável e desenvolver estruturas de dados de bloco de cabeçalho em torno dele ... por exemplo, você fixa todos os tamanhos de bloco em 4KB (normalmente o mais ideal de qualquer maneira) e escreve um número muito pequeno cabeçalho do bloco que inclui o "tipo de bloco" no início. Se for um bloco normal, imediatamente após o cabeçalho do bloco deve ser o cabeçalho das compensações. Se for do tipo "estouro", imediatamente após o cabeçalho do bloco serão dados-chave brutos.

Atualização (potencial impressionante)

Depois que o bloco é lido como uma série de bytes e os deslocamentos decodificados; tecnicamente, você pode simplesmente codificar a chave que está procurando em bytes brutos e, em seguida, fazer comparações diretas no fluxo de bytes.

Quando a chave que você procura é encontrada, o ponteiro pode ser decodificado e seguido.

Outro efeito colateral impressionante da ideia de Greg! O potencial para otimização do tempo da CPU aqui é grande o suficiente para que a configuração de um tamanho de bloco fixo valha a pena apenas para obter tudo isso.

Você pode armazenar seu índice como uma lista de compensações de tamanho fixo no bloco que contém seus dados principais. Por exemplo:

+--------------+
| 3            | number of entries
+--------------+
| 16           | offset of first key data
+--------------+
| 24           | offset of second key data
+--------------+
| 39           | offset of third key data
+--------------+
| key one |
+----------------+
| key number two |
+-----------------------+
| this is the third key |
+-----------------------+

(bem, os dados principais seriam classificados em um exemplo real, mas você entendeu).

Observe que isso não reflete necessariamente como os blocos de índice são realmente construídos em qualquer banco de dados. Este é apenas um exemplo de como você pode organizar um bloco de dados de índice em que os dados principais são de tamanho variável.