https://news.mit.edu/sites/default/files/styles/news_article__image_gallery/public/images/202111/server-rack.jpg?itok=gqbKeJ5A

Descoberta pode aumentar o desempenho no armazenamento de dados

Postado em 21 de novembro de 2021 por

Categorias: Desenvolvimento Web

Etiquetas:

Segundo artigo publicado no inicio do ano e apresentado em fevereiro no Simpósio de Fundamentos de Ciência da Computação em Boulder – Colorado, a descoberta pode levar o armazenamento e a recuperação de dados mais eficientes em computadores.

O trio de pesquisadores, que inclui William Kuszmaul – estudante de doutorado em Ciências da Computação no MIT, destaca que a descoberta está ligada as chamadas “tabelas de sondagem linear” que foram introduzidas em 1954 e estão entre as estruturas de dados mais antigas, simples e rápidas disponíveis até o momento. As estruturas de dados fornecem maneiras de organizar e armazenar dados em computadores, sendo as tabelas hash uma das abordagens mais comumente empregada. Em uma tabela hash de teste linear, as posições em que as informações podem ser armazenadas estão ao longo de uma matriz linear.

Tomando por exemplo que um banco de dados seja projetado para armazenar os números da Previdência Social de 10.000 pessoas, sugere Kuszmaul. “Pegamos seu número de Seguro Social, x, e então calcularemos a função hash de x, h (x), que dá a você um número aleatório entre um e 10.000.” O próximo passo é pegar aquele número aleatório, h (x), ir para aquela posição na matriz e colocar x, o número da Previdência Social, naquele local.

Se já houver algo ocupando aquele lugar, Kuszmaul diz, “basta avançar para a próxima posição livre e colocá-lo lá. É daí que vem o termo ‘sondagem linear’, à medida que você continua avançando linearmente até encontrar um ponto aberto. ” Para recuperar mais tarde esse número da Previdência Social, x, basta ir ao local designado, h (x), e se não estiver lá, você segue em frente até encontrar x ou chegar a uma posição livre e concluir que x é não em seu banco de dados.

Existe um protocolo um pouco diferente para a exclusão de um item, como um número do Seguro Social. Se você acabou de deixar um espaço vazio na tabela de hash após excluir as informações, isso pode causar confusão quando você tentar encontrar outra coisa mais tarde, já que o local vago pode sugerir erroneamente que o item que você está procurando não pode ser encontrado em o banco de dados. Para evitar esse problema, Kuszmaul explica, “você pode ir até o local onde o elemento foi removido e colocar um pequeno marcador chamado ‘lápide’, que indica que costumava haver um elemento aqui, mas ele já foi embora”.

Esse procedimento geral foi seguido por mais de meio século. Mas em todo esse tempo, quase todo mundo que usa tabelas de hash de sondagem linear presumiu que, se você permitir que eles fiquem muito cheios, longos trechos de locais ocupados correrão juntos para formar “clusters”. Como resultado, o tempo que leva para encontrar um lugar livre aumentaria dramaticamente – quadraticamente, na verdade – levando tanto tempo que se tornaria impraticável. 

Leia mais no original em inglês:  https://news.mit.edu/2021/theoretical-breakthrough-hash-tables-could-boost-data-storage-1116

Deixe um comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *