ottimizza il database leggibile dall'uomo con l'indice

3

Ho bisogno di memorizzare una grande quantità di dati - circa 10 milioni di voci nel formato

unique hash (64 chars), value 1 (5 chars), value 2 (9 chars)

leggerò e cancellerò (ma non aggiornerò) questi dati in rapida successione. per esempio, potrei scrivere 10 linee, poi leggere 3 e cancellare 3 linee, prima di passare a più di scrittura e letture ...

è un programma desktop a thread singolo in modo che le letture vengano avviate solo dopo che le scritture e le eliminazioni sono state completate. Vorrei evitare l'uso di un database in modo che i dati possano essere leggibili dal file system e in modo che le persone che scaricano e utilizzano il mio programma possono vederlo e ispezionarlo da soli. mi aspetto che i miei utenti eseguano un sistema operativo Linux e il mio programma sia scritto in python.

Ho trovato tre possibili opzioni su come memorizzare questi dati:

opzione 1

inserisci i dati in un unico file. dal momento che gli hash sono unici, posso organizzarli in ordine crescente come un indice in modo da dare log2 N di volte in lettura. l'eliminazione e l'inserimento avverranno spesso e rallenterebbero il processo verso il basso quando N diventasse grande.

opzione 2

usa l'hash univoco come nome file e inserisci i valori in questo file. questa sarebbe la mia opzione preferita fintanto che non ci sono evidenti inconvenienti in termini di prestazioni? so che alcuni file system rallentano quando un numero elevato di file esiste in una singola directory . e davvero non posso fare ipotesi su quale sistema di file useranno gli utenti del mio programma. Ho bisogno di scegliere una soluzione che sia veloce su tutti i file system.

opzione 3

usa l'hash univoco per creare una directory in cui archiviare i valori. Ad esempio, se un record ha hash abcd , creerò dir e file base_dir/a/b/c/d.txt . questo risolve il problema relativo alle prestazioni del file system? o è così grave come l'opzione 2 a seconda del tipo di file system che l'utente sta utilizzando?

questione

quindi in realtà sto solo cercando aiuto per decidere quale opzione scegliere. anche se hai altre opzioni che sono superiori a quelle che ho elencato qui mi piacerebbe ascoltarle. forse qualche software di database come mysqli che danneggia i dati in un testo leggibile? sarebbe davvero l'ideale, ma immagino che la maggior parte dei database utilizzi il binario per l'efficienza ...

    
posta mulllhausen 16.07.2014 - 16:02
fonte

1 risposta

2

Esiste una soluzione abbastanza ovvia: un archivio di file con hash diretto.

Per gestire i tuoi suggerimenti:

  1. Accesso lento, eliminazione e inserimento orribilmente lenti. Dimenticalo.
  2. Nessun file system può darti un milione di file in tempi ragionevoli. Dimenticalo.
  3. fattibile ma complicato per elaborare uno schema decente. Non è la mia scelta.

Per un archivio di file con hash diretto si divide il file in bucket (ad esempio 4000 byte, con 80 chiavi). Crea una funzione hash dell'hash univoco che distribuisce le chiavi in modo uniforme tra i bucket. Metti ogni record in quel bucket. Alloca un certo numero di bucket di overflow per le chiavi quando il bucket a cui appartengono è pieno.

È possibile trovare qualsiasi record in poco più di O (1) con un singolo calcolo e una singola lettura (bucket), seguita dalla ricerca nel bucket per il record corretto. È possibile aggiungere o eliminare un record con una scrittura aggiuntiva. Il tuo obiettivo è di circa l'80-90% pieno, a seconda di quanto è buona la tua funzione è quella di distribuire le chiavi in bucket. se è troppo pieno, devi andare troppo spesso in un secchio di troppo pieno e questo costa delle prestazioni.

Puoi facilmente trovare i dettagli su come implementare questo tipo di schema. È una tecnica molto vecchia dai giorni pre-database. Molto veloce, abbastanza semplice e perfetto per il tuo problema.

    
risposta data 16.07.2014 - 16:36
fonte

Leggi altre domande sui tag