Indici di database e loro notazione Big-O

Question

Sto cercando di capire le prestazioni degli indici di database in termini di notazione Big-O. Senza sapere molto, suppongo che:

• Interrogare su una chiave primaria o su un indice univoco fornirà un tempo di ricerca O (1).
• Interrogare su un indice non univoco fornirà anche un tempo O (1), anche se forse il '1' è più lento rispetto all'indice univoco (?)
• Interrogare su una colonna senza un indice darà un O (N) tempo di ricerca (scansione completa della tabella).

È generalmente corretto? L'interrogazione su una chiave primaria darà prestazioni peggiori di O (1)? La mia preoccupazione specifica è per SQLite, ma sarei interessato a sapere fino a che punto questo varia tra diversi database.

Answer 1

La maggior parte dei database relazionali struttura gli indici come alberi B.

Se una tabella ha un indice di clustering, le pagine di dati vengono memorizzate come nodi foglia dell'albero B. In sostanza, l'indice di cluster diventa la tabella.

Per le tabelle senza un indice di clustering, le pagine di dati della tabella sono memorizzate in un heap. Tutti gli indici non cluster sono alberi B in cui il nodo foglia dell'albero B identifica una determinata pagina nell'heap.

L'altezza caso peggiore di un B-albero è O (log n), e dal momento che la ricerca è in funzione della posizione, le ricerche B-tree correre in qualcosa di simile (in media)

O (log _t n)

dove t è il fattore minimizzazione (ogni nodo deve avere almeno t -1 chiavi e al massimo 2 * t * -1 tasti (ad esempio, 2 * t * bambini).

Questo è il modo in cui l'ho capito

E diversi sistemi di database, ovviamente, potrebbero utilizzare diverse strutture di dati sotto il cofano.

E se la query non utilizza un indice, ovviamente, la ricerca è un'iterazione sull'heap o sull'albero B che contiene le pagine di dati.

Le ricerche sono un po 'più economiche se l'indice utilizzato può soddisfare la richiesta; in caso contrario, è richiesto un lookaside per recuperare il datapage corrispondente in memoria.

Answer 2

Le query indicizzate (univoche o non) sono in genere più O (log n). Molto semplicisticamente, si può pensare che sia simile a una ricerca binaria in una matrice ordinata. Più precisamente, dipende dal tipo di indice. Ma una ricerca b-tree, ad esempio, è ancora O (log n).

Se non c'è indice, quindi, sì, è O (N).

Answer 3

se si selezionano le stesse colonne si cerca allora

• primario o Unqiue sarà O (log n): si tratta di una ricerca di b-tree
• indice non univoco è anche O (log n) + un po ': si tratta di una ricerca di b-tree
• alcun indice = O (N)

Se avete bisogno di informazioni da un altro "fonte" (indice di intersezione, segnalibro/chiave di ricerca, ecc) perché l'indice è non coprente, quindi potresti avere O (n + log n) o O (log n + log n + log n) a causa di più hit di indice + ordinamento intermedio.

Se le statistiche dimostrano che è necessario un alto% di righe (indice ad esempio non molto selettivo) allora l'indice può essere ignorato e diventare una scansione = O (n)

Answer 4

altre risposte invia un buon punto di partenza; ma vorrei solo aggiungere che per ottenere O (1), l'indice primario stesso dovrebbe essere basato su hash (che in genere non è la scelta predefinita); così più comunemente è logaritmico (albero B).

È corretto che gli indici secondari in genere abbiano la stessa complessità, ma prestazioni peggiori, perché l'indice e i dati non sono raggruppati, quindi la costante (numero di ricerche disco) è maggiore.

Answer 5

Dipende da cosa è la tua richiesta.

• Una condizione del modulo Column = Value consente l'utilizzo di un indice basato su hash, che ha O (1) tempo di ricerca. Tuttavia, many databases, including SQLite, do not support them.
• Una condizione utilizzando gli operatori relazionali (<, >, <=, >=) può fare uso di un indice ordinata, tipicamente implementato con un albero binario, che ha O (log n) tempo di ricerca.
• Le espressioni più complesse che non possono utilizzare un indice richiedono tempo O (n).

Poiché si è interessati principalmente a SQLite, si potrebbe voler leggere il suo Query Optimizer Overview che spiega in modo più dettagliato come gli indici sono selezionati.