Come funziona la scala del tempo della query del database con le dimensioni del database?

Question

Sono stato di recente sull'OEIS (Enciclopedia online delle sequenze Intere) di recente, cercando di cercare una particolare sequenza che avevo avuto.

Ora, questo database è abbastanza grande.Il sito web afferma che se è stata stampata l'edizione del 2006 (! 5 anni), occuperebbe 750 volumi di testo.

Sono sicuro che è lo stesso tipo di problema che Google deve maneggiare anche Google.Ma hanno anche un sistema distribuito in cui sfruttano il bilanciamento del carico.

trascurando il bilanciamento del carico Tuttavia, quanto tempo impiega per eseguire una query rispetto alle dimensioni del database?

o in altre parole, qual è la complessità del tempo di una query rispetto alla dimensione del DB?

Modifica: per rendere le cose più specifiche, supponiamo che la query di input stia semplicemente cercando una stringa di numeri come:

1, 4, 9, 16, 25, 36, 49

.

Answer 1

dipende fortemente dalla query, dalla struttura del database, dalla contesa e così via. Ma in generale la maggior parte dei database troverà un modo per utilizzare un indice e quell'indice sarà un tipo di struttura ad albero (vedere http://en.wikipedia.org/wiki/b-tree per un'opzione) nel qual caso il tempo di accesso è proporzionale al registro (N), altrimenti un hash in cui è il tempo di accesso Proporzionale a O (1) in media (vedere http://en.wikipedia.org/wiki/hash_function #Hash_tables per una spiegazione di come funzionano).

Quindi la risposta è in genere o (1) o o (registro (n)) a seconda del tipo di struttura dei dati.

Questo potrebbe farti chiedere perché non usiamo sempre le funzioni hash. Ci sono molteplici ragioni. Le funzioni di hash rendono difficile recuperare le gamme di valori. Se la funzione hash non riesce a distribuire bene i dati, è possibile che il tempo di accesso diventa o (n). Hash ha bisogno di ridimensionare occasionalmente, che è potenzialmente molto costoso. E il registro (N) cresce abbastanza lentamente da poterlo trattare come ragionevolmente vicino a costante su tutti i set di dati pratici. (Da 1000 a 1 petabyte varia di un fattore di 5.) E frequentemente i dati richiesti attivamente mostrano una sorta di località, quali alberi fanno un migliore lavoro di tenuta nella RAM. Di conseguenza gli alberi sono in qualche modo più comunemente visti in pratica. (Anche se gli hash non sono affatto rari.)

Answer 2

Dipende da una serie di fattori tra cui l'implementazione del motore del database, la strategia di indicizzazione, le specifiche della query, l'hardware disponibile, la configurazione del database, ecc.

Non c'è modo di rispondere a una domanda così generale.

Answer 3

Un database correttamente progettato e implementato con terabyte di dati può effettivamente sovraperformare un piccolo database gravemente progettato (particolarmente uno senza indicizzazione e uno che utilizza query e cose non sargabili gravemente sargabili e cose come i sottostizie correlate).Questo è il motivo per cui chiunque si aspetta di avere grandi quantità di dati necessari per assumere un esperto sul design del database per i database di grandi dimensioni per fare il design iniziale non oltre quando il database è grande.Potrebbe anche essere necessario investire nel tipo di attrezzatura che è necessario gestire anche le dimensioni.