Struttura dati per la ricerca di file

Un Indice invertito sembra essere quello che cerchi. L'idea di base è:

• I messaggi / file vengono salvati su disco nella loro struttura completa.
• Ogni parola nel file ha una riga in una tabella nel database.
• C'è una tabella di link che ti permette di fare un join tra le parole e un ID univoco per ogni messaggio / file.

Ad esempio, ecco le 3 tabelle del database che vorrei creare:

CREATE TABLE words (
    word_id INT PRIMARY KEY,
    word TEXT
)
CREATE TABLE links (
    word_id INT FOREIGN KEY words(word_id),
    file_id INT FOREIGN KEY files(file_id),
)
CREATE TABLE files (
    file_id INT PRIMARY KEY,
    filename TEXT
)

Per trovare tutti i nomi di file che contengono le parole "help" e "me":

SELECT filename
FROM files
INNER JOIN links l1 ON (files.file_id = l1.file_id)
INNER JOIN words w1 ON (l1.word_id = w1.word_id)
INNER JOIN links l2 ON (files.file_id = l2.file_id)
INNER JOIN words w2 ON (l2.word_id = w2.word_id)
WHERE w1.word = "help" AND w2.word = "me"

Che aiuto?

B-Trees suona esattamente come la struttura dei dati che stai cercando.

Per citare l'articolo di Wikipedia:

...the B-tree is optimized for systems that read and write large blocks of data. It is commonly used in databases and filesystems.

Una soluzione di database può avere diverse strutture:

1-Utilizzo del metodo di accesso casuale per leggere il file.

Utilizzando questo approccio, non hai bisogno di un database. È possibile aprire il file e utilizzare fseek (o metodo simile) per spostarsi sulla riga desiderata per eseguire la lettura. Potresti vedere un tutorial qui: Funzione di accesso casuale

2-Utilizzo della tabella caricata del database

Questo approccio richiede che tu esegua un carico prima di accedere ai dati. Ciò complica leggermente la soluzione, ma il carico non dovrebbe essere un problema se si utilizza il caricatore fornito dal database e si rilasciano gli indici prima del caricamento. Per ottenere il massimo le prestazioni utilizzando questo approccio, è possibile creare un indice di clustering sulla chiave desiderata. Anche questo richiederà alcuni secondi, anche se hai milioni di righe. A questo punto, la tua query sarà molto veloce e nulla potrebbe probabilmente sconfiggerlo.

3-Utilizzo del database File esterni (forniti da Oracle e probabilmente da altri database)

Questo approccio consente di accedere alle righe utilizzando SQL senza caricare fisicamente il file nel database. I vantaggi sono la facilità d'uso usando solo SQL e il fatto che nessun carico del database deve essere programmato o eseguito. È possibile scavare ulteriormente e vedere se un tale metodo di accesso consente il partizionamento senza creazione dell'indice (supponendo che i dati siano già in ordine). Potrebbe quindi essere molto veloce.

Suggerirei di provare le soluzioni nell'ordine elencato e testare le prestazioni. Immagino che la soluzione numero 1 dovrebbe essere la più veloce se hai la chiave esatta.

Potresti provare Lucene . È una libreria di ricerca a tutto testo che offre potenti funzionalità tramite una semplice API. È scritto in Java, ma esiste una versione .NET, Lucene.net .

L'ho usato molti su progetti Web / desktop per implementare la funzionalità di ricerca aziendale.