Armazenando objetos dinâmicos com listas crescentes em disco

Question

Ok, até agora tenho desenvolvido um sistema na memória principal que possui muitos objetos diferentes e cada objeto armazena listas de outros objetos no sistema.Agora quero mover isso para armazenamento persistente.Não estou procurando a resposta óbvia de usar um SGBD porque a questão é que estou escrevendo um banco de dados personalizado para meu sistema.

Agora, para cada objeto, estou atribuindo um ID.Os ids podem ser consultados em uma tabela para encontrar o bloco e o deslocamento da localização dos dados desse objeto.Agora cada objeto possui listas/conjuntos que apontam para outros objetos no sistema.Então obviamente no storage estarão listas de 8 bytes (usando longs para os ids) ids que podem ser usados ​​para encontrar os outros objetos.Agora, minha pergunta aqui é que sei que as listas crescerão com o tempo, então precisam de espaço para crescer.Minha melhor ideia até agora para armazenar as listas para que eu não precise mover os objetos quando elas crescerem é atribuir um ID a cada lista, assim como os objetos, para que possam ser pesquisados ​​em uma tabela, assim como os objetos a serem encontrados. -los no disco.

Agora cada parte da lista terá um espaço alocado definido para armazenar 10 objetos e então no final estará o id da próxima parte da lista se ela contiver mais objetos.Esta parece ser uma maneira decente de fazer isso e de lidar com objetos em constante crescimento, mas estou me perguntando se existem abordagens melhores.Eu armazenaria os índices na memória (se o espaço permitir), portanto, dado um ID de objeto, a pesquisa está na memória, então seria necessária 1 E/S para encontrar seus dados e listar os IDs do disco.então, para cada lista que você deseja percorrer, será necessária outra pesquisa e E/S para cada 10 objetos na lista ou menos, se o bloco estiver armazenado em cache.

O número de E/S não é terrível e eu tentaria manter a localidade das partes da lista para eliminar E/S desnecessárias, mas existe uma maneira melhor de fazer isso?Estou certo em tentar armazenar as listas separadas do objeto ou devo considerar métodos para armazená-las com os dados do objeto.Minha preocupação em fazer isso é que, à medida que uma lista cresce, ela irá para outra lista e precisará ser fragmentada e isso pode ficar mais complicado.Qualquer sugestão será apreciada e obrigado antecipadamente.

Answer 1

Sua ideia de ter essas listas expansíveis é boa.Acho que faltam alguns detalhes em sua explicação (por exemplo:listas ordenadas ou não, o que você quer dizer com tentar separar listas de objetos, um diagrama dessas listas pode ajudar).

Eu manteria um índice classificado na memória para acesso rápido.O índice teria o ID da lista e a localização no disco.Se você estiver interessado em consultas de intervalo, opte por uma abordagem de árvore B; caso contrário, você poderá usar um hashmap para armazenar esses índices.

Uma melhoria adicional, se você estiver pesquisando nas listas, é mantê-las ordenadas...ou pelo menos semi-classificados para que você possa agrupar listas semelhantes no mesmo bloco.Isso aceleraria a pesquisa nas listas se você, de vez em quando, armazenasse em cache na memória os limites de cada pedaço (nós com valores b/w 1-9, 10-25, etc.).A classificação por mesclagem é provavelmente a melhor classificação para listas.Ou melhor ainda, ao inserir nós nas listas, insira-os no local correto para que a lista esteja sempre ordenada.Em seguida, procure com pesquisa binária.Se os dados não forem indexados corretamente e não forem classificados, você irá ao disco várias vezes para consultas e, nesse caso, qualquer pesquisa usada fornecerá um tempo linear devido ao tempo do disco.

Você também pode armazenar em cache os nós de dados dos 10% dos nós/listas mais pesquisados.

Dependendo do tamanho dessas listas (e de quantos pedaços você tem para elas), você pode usar algum RAID para obter algumas leituras/gravações paralelas.