Contexto
Esta questão refere-se aos detalhes de implementação de baixo nível de índices em sistemas de banco de dados SQL e NoSQL. A estrutura real do índice (árvore B+, hash, SSTable, etc.) é irrelevante, pois a questão se refere especificamente às chaves armazenadas em um único nó de qualquer uma dessas implementações.
Fundo
Em bancos de dados SQL (por exemplo, MySQL) e NoSQL (CouchDB, MongoDB, etc.), quando você cria um índice em uma coluna ou campo de dados de documento JSON, o que você está realmente fazendo com que o banco de dados faça é criar essencialmente uma lista classificada de todos os esses valores junto com um deslocamento de arquivo no arquivo de dados principal onde reside o registro pertencente a esse valor.
(Para simplificar, posso estar descartando outros detalhes esotéricos de impls específicos)
Exemplo de SQL Clássico Simples
Considere uma tabela SQL padrão que tenha 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 onde 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 sobre 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 4 KB 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 retornamos ao disco conforme necessário.
Consulta de exemplo
Usando as informações da seção anterior, digamos que uma consulta chegue para "id=2", a pesquisa de índice de banco de dados clássica é a seguinte:
- Leia a raiz do índice (neste caso, 1 bloco)
- Pesquisa binária no bloco classificado para encontrar a chave
- Obtenha o deslocamento do arquivo de dados do valor
- Procure o registro no arquivo de dados usando o deslocamento
- Devolva os dados ao chamador
Configuração da pergunta...
Ok, aqui é onde a pergunta vem junto ...
A etapa 2 é a parte mais importante que permite que essas consultas sejam executadas em tempo O(logn)... as informações devem ser classificadas, MAS você deve ser capaz de percorrer a lista de maneira rápida... mais especificamente, você deve ser capaz de pular para deslocamentos bem definidos à vontade para ler o valor da chave de índice nessa posição.
Depois de ler no bloco, você tem que conseguir pular para a 170ª posição imediatamente, ler o valor da chave e ver se o que você procura é GT ou LT naquela posição (e assim por diante e assim por diante...)
A única maneira de pular os dados no bloco dessa maneira é se os tamanhos dos valores das chaves estiverem todos bem definidos, como nosso exemplo acima (4 bytes e depois 8 bytes por chave).
PERGUNTA
Ok, então é aqui que estou travando com 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 comprimento como você implementa os valores-chave que estão dentro dos blocos da estrutura de índice a partir da qual você constrói seus índices?
Por exemplo, digamos que você use um contador sequencial 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ê crie o índice no banco de dados no dia 1, quando houver apenas 4 tweets no banco de dados, o CouchDB pode ser 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 realmente de comprimento variável como um "tweet_message" ou algo assim.
Com as próprias chaves tendo comprimento totalmente variável e o banco de dados não tendo como adivinhar de forma inteligente 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ê em um bloco de chaves, não apenas não tem ideia de quantas chaves estão realmente no bloco, mas também não tem ideia de como pular para o meio da lista para fazer um binário pesquise sobre eles.
É aqui que estou ficando todo tropeçado.
Com campos de tipo estático em bancos de dados SQL clássicos (como bool, int, char, etc.), entendo que o índice pode apenas predefinir o tamanho da chave e cumpri-lo ... mas neste mundo de armazenamentos de dados de documentos, estou perplexo como eles estão modelando com eficiência esses dados no disco de forma que ainda possam ser verificados em tempo de O(logn) e gostaria de receber qualquer esclarecimento aqui.
Por favor, deixe-me saber se quaisquer esclarecimentos são necessários!
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 se deparou com uma sugestão maravilhosamente simples e eficiente de que, na prática, é muito fácil de implementar e usar, ao mesmo tempo em que oferece grandes ganhos de desempenho ao evitar a desserialização de valores-chave com os quais você não se importa.
Eu examinei 3 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 dentro de seu ambiente de execução (erlang/C).
É isso que considero tão brilhante na sugestão de Greg; um tamanho de bloco normal de 2048 normalmente teria 50 ou menos deslocamentos, resultando em um bloco muito pequeno de números que precisaria ser lido.
Atualização (possíveis desvantagens da sugestão de Greg)
Para continuar este diálogo comigo mesmo, percebi as seguintes desvantagens...
Se cada "bloco" for encabeçado 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 correto ou um bloco que continha vários cabeçalhos.
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 caibam em um único bloco e precisem ser sobrecarregadas 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 da chave.
A solução para tudo isso é ter um tamanho de bloco de banco de dados fixo que não seja 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 4 KB (normalmente o mais ideal de qualquer maneira) e escreve 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 estar o cabeçalho de deslocamentos. Se for um tipo de "transbordamento", imediatamente após o cabeçalho do bloco estarão os dados de chave brutos.
Atualização (possível up-side incrível)
Depois que o bloco é lido como uma série de bytes e os deslocamentos decodificados; tecnicamente, você poderia simplesmente codificar a chave que está procurando em bytes brutos e, em seguida, fazer comparações diretas no fluxo de bytes.
Uma vez encontrada a chave que você está procurando, o ponteiro pode ser decodificado e seguido.
Outro efeito colateral incrível da ideia de Greg! O potencial para otimização de tempo de CPU aqui é grande o suficiente para que definir um tamanho de bloco fixo possa valer a pena apenas para obter tudo isso.
Você pode armazenar seu índice como uma lista de deslocamentos de tamanho fixo no bloco que contém seus dados principais. Por exemplo:
(bem, os dados-chave 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 de chave são de comprimento variável.