O UNIX pesquisa por diretórios usando a pesquisa binária?

2

Atualmente, estou lendo o livro Advance UNIX Programming, de W. Richard Stevens, e li que todos os arquivos no UNIX têm um número e que os nomes dos arquivos são criados apenas para conveniência do usuário. Quando um diretório é inserido, o sistema pesquisa o número do nome digitado.

Eu pensei comigo mesmo, como eles pesquisam o número? Os arquivos são armazenados classificados por nome para que possam encontrá-los por pesquisa binária? Ou apenas acrescentam novos arquivos ao final da lista?

    
por Mipster 24.09.2016 / 07:59

4 respostas

4

Existem muitos formatos diferentes de sistemas de arquivos e eles fazem diferentes comprometimentos entre o desempenho em diferentes cenários (diretórios grandes versus diretórios pequenos, leitura versus escrita, acesso simultâneo,…), simplicidade de design (probabilidade de erros, esforço de desenvolvimento,…) sobrecarga (espaço usado para outras coisas além de conteúdo de arquivo), etc.

Sistemas de arquivos mais antigos (por exemplo, UFS, FFS , ext2 , original ext3 ,…) tendem a armazenar diretórios como uma matriz de entradas ( cada entrada contém um nome de arquivo, um número de inode e possivelmente alguns metadados adicionais) e para fazer uma pesquisa linear. Novos arquivos são adicionados na primeira entrada gratuita da matriz; se não houver entrada livre, o array será ampliado primeiro. Isso resulta em desempenho ruim com diretórios grandes.

Novos sistemas de arquivos (por exemplo, ext3 com a opção dir_index , ext4 , zfs , btrfs , reiserfs , HFS , HFS + ,…) tendem a armazenar diretórios como uma estrutura de dados com pesquisa de tempo logarítmico, algum tipo de árvore de pesquisa balanceada, tabela de hash ou uma combinação dos dois (árvore de pesquisa balanceada de hashes) - normalmente alguma variante de um B-tree . Isso torna o código do sistema de arquivos mais complexo, mas mantém um bom desempenho com diretórios grandes.

    
por 24.09.2016 / 21:53
2

O número é chamado inode . Ext4, um dos mais populares tipos de sistemas de arquivos Linux, faz uso de um hash tree, veja kernel.org - Ext4 Layout do disco .

Mais detalhes sobre árvores de hash em wikipedia .

    
por 24.09.2016 / 11:10
2

Isso depende do sistema de arquivos. Há muito tempo atrás, o diretório Unix era essencialmente um arquivo que consistia de 16 registros de bytes, dois bytes para o número interno e 14 bytes para o nome do arquivo. Essa é a razão para o limite de 14 caracteres antigos nos nomes de arquivos. Os registros não foram classificados, portanto, foi necessária uma pesquisa linear no arquivo.

Sistemas de arquivos mais modernos como o Ext4 do Linux têm uma tabela de hash para acelerar a pesquisa.

    
por 24.09.2016 / 11:23
0

Alerta de pedante: a descrição não está completa. Os nomes dos arquivos não podem ser descritos apenas como uma conveniência para os usuários. Os nomes dos arquivos acabaram sendo extremamente importantes em sistemas baseados em Unix.

Os números de inodes não podem ter significado porque são escolhidos pelo módulo do sistema de arquivos. Originalmente, eles identificaram um slot na tabela de inode armazenado no disco. As outras partes do sistema precisam acessar arquivos que tenham um significado específico, por ex. /dev/tty1 ou /etc/passwd .

Sem manter você em uma palavra específica, "conveniência" é trivial demais para descrever o mecanismo, que é usado para fornecer a interface do usuário para selecionar comandos como cat ou ed pelo nome.

Se não houvesse diretórios de nomes de arquivos, você logo teria que inventar alguns registros muito semelhantes de nomes para os números de inode para suportar esses usos.

As entradas de diretório . e .. também têm um significado especial. Sistemas de arquivos virtuais, como proc , fornecem seu próprio significado usando nomes de arquivos, por ex. disponibilizando /proc/1/comm para fornecer informações sobre o processo 1. O VFS também permite o uso de sistemas de arquivos diferentes, que não precisam ser baseados em unix e podem não funcionar com o mesmo conceito exato de números de inodes.

O ZFS parece achar que os nomes de arquivos e os metadados de inode, como permissões, pertencem a uma camada separada. Eu ainda tenho que entender que vantagem isso proporciona. Parece ser mais uma maneira de fornecer diferentes botões de desempenho para objetos equivalentes a arquivos quando usados para armazenar sistemas de arquivos aninhados.

Também os usuários geralmente não podem abrir arquivos pelo número do inode. Se pudessem, você não conseguiria controlar o acesso a um arquivo por meio das permissões do diretor de conteúdo {y, i}} ...

Talvez outra maneira de ver o último ponto seja que é um recurso de diretórios. Todo o princípio de um diretório é mapear nomes de arquivos, sem que eles realmente não tenham efeito algum.

Espere, você diz, eles ainda teriam um efeito como um contêiner para referências a arquivos também conhecidos como "hard links". Você pode ter arquivos listados em vários diretórios; remover um arquivo de um diretório ( unlink ) não o exclui, se ainda permanecer em outro diretório. Hard links são uma parte interessante da implementação do Unix, mas a AFAIK nunca encontrou utilidade alguma! Eles são geralmente considerados apenas como uma oportunidade para confusão. Um exemplo de exposição de um detalhe de implementação, porque tornou muito fácil fornecer recursos interessantes, sem realmente considerar se o recurso era necessário. Semelhante ao "erro de bilhões de dólares", embora essa falha de projeto em particular não tenha sido tão perigosa.

Dito isto, vale a pena observar a maneira como os diretórios garantem a existência dos arquivos que eles contêm. Se você quisesse implementar algum outro sistema para identificar arquivos, você teria que considerar a possibilidade de que a exclusão de um arquivo deixaria uma entrada referente a um arquivo inexistente, ou até mesmo um arquivo novo e não relacionado ao qual foi atribuído o mesmo inode. número mais tarde.

    
por 25.09.2016 / 01:18