Domanda Come funziona l'indicizzazione del database?


Dato che l'indicizzazione è tanto importante quanto il tuo set di dati aumenta di dimensioni, qualcuno può spiegare come funziona l'indicizzazione a livello indipendente dal database?

Per informazioni sulle query per indicizzare un campo, controlla Come indicizzare una colonna del database.


1872
2017-08-04 10:07


origine


risposte:


Perché è necessario?

Quando i dati vengono archiviati su dispositivi di archiviazione basati su disco, vengono archiviati come blocchi di dati. Questi blocchi sono accessibili nella loro interezza, rendendoli l'operazione di accesso al disco atomico. I blocchi del disco sono strutturati nello stesso modo delle liste concatenate; entrambi contengono una sezione per i dati, un puntatore alla posizione del nodo successivo (o blocco), ed entrambi non devono essere memorizzati in modo contiguo.

A causa del fatto che un numero di record può essere ordinato solo su un campo, possiamo affermare che la ricerca su un campo che non è ordinato richiede una ricerca lineare che richiede N/2 blocca gli accessi (in media), dove N è il numero di blocchi che la tabella si estende. Se questo campo è un campo non chiave (cioè non contiene voci univoche), è necessario cercare l'intero spazio tabella N bloccare gli accessi.

Mentre con un campo ordinato si può usare una ricerca binaria, che ha log2 N bloccare gli accessi. Inoltre, poiché i dati vengono ordinati in base a un campo non chiave, non è necessario cercare il resto della tabella per i valori duplicati, una volta che viene trovato un valore più alto. Quindi l'aumento delle prestazioni è notevole.

Cos'è l'indicizzazione?

L'indicizzazione è un modo di ordinare un numero di record su più campi. La creazione di un indice su un campo in una tabella crea un'altra struttura dati che contiene il valore del campo e un puntatore al record a cui si riferisce. Questa struttura dell'indice viene quindi ordinata, consentendo di eseguire ricerche binarie su di essa.

Lo svantaggio dell'indicizzazione è che questi indici richiedono spazio aggiuntivo sul disco poiché gli indici sono memorizzati insieme in una tabella utilizzando il motore MyISAM, questo file può raggiungere rapidamente i limiti di dimensione del file system sottostante se molti campi all'interno della stessa tabella sono indicizzati .

Come funziona?

In primo luogo, analizziamo uno schema di tabella di database di esempio;

Nome campo Tipo di dati Dimensione su disco
id (chiave primaria) Unsigned INT 4 byte
firstName Char (50) 50 byte
lastName Char (50) 50 byte
emailAddress Char (100) 100 byte

Nota: char è stato utilizzato al posto di varchar per consentire una dimensione accurata sul valore del disco. Questo database di esempio contiene cinque milioni di righe e non è indicizzato. Verranno ora analizzate le prestazioni di diverse query. Queste sono una query che usa il id (un campo chiave ordinato) e uno che usa il nome di battesimo (un campo non composto non chiave).

Esempio 1 - ordinati vs campi non ordinati

Dato il nostro database di esempio di r = 5,000,000 record di dimensioni fisse che danno una lunghezza record di R = 204 byte e sono memorizzati in una tabella utilizzando il motore MyISAM che utilizza la dimensione di blocco predefinita B = 1,024byte. Il fattore di blocco del tavolo sarebbe bfr = (B/R) = 1024/204 = 5 record per blocco del disco. Il numero totale di blocchi necessari per contenere la tabella è N = (r/bfr) = 5000000/5 = 1,000,000 blocchi.

Una ricerca lineare sul campo id richiederebbe una media di N/2 = 500,000 blocca gli accessi per trovare un valore, dato che il campo id è un campo chiave. Ma poiché il campo id è anche ordinato, una ricerca binaria può essere condotta richiedendo una media di log2 1000000 = 19.93 = 20 bloccare gli accessi. Immediatamente possiamo vedere che questo è un miglioramento drastico.

Ora il nome di battesimo il campo non è né ordinato né un campo chiave, quindi una ricerca binaria è impossibile, né i valori sono univoci, e quindi la tabella richiederà la ricerca fino alla fine per un'esatta N = 1,000,000 bloccare gli accessi. È questa situazione che l'indicizzazione mira a correggere.

Dato che un record di indice contiene solo il campo indicizzato e un puntatore al record originale, è ovvio che sarà più piccolo del record multi-campo a cui punta. Pertanto, l'indice stesso richiede meno blocchi del disco rispetto alla tabella originale, che pertanto richiede meno accessi ai blocchi per scorrere l'iterazione. Lo schema per un indice sul nome di battesimo il campo è descritto di seguito;

Nome campo Tipo di dati Dimensione su disco
firstName Char (50) 50 byte
(puntatore del record) Speciali 4 byte

Nota: I puntatori in MySQL hanno una lunghezza di 2, 3, 4 o 5 byte, a seconda delle dimensioni della tabella.

Esempio 2  - indicizzazione

Dato il nostro database di esempio di r = 5,000,000 registra con una lunghezza record dell'indice di R = 54 byte e utilizzando la dimensione di blocco predefinita B = 1,024 byte. Il fattore di blocco dell'indice sarebbe bfr = (B/R) = 1024/54 = 18 record per blocco del disco. Il numero totale di blocchi necessari per contenere l'indice è N = (r/bfr) = 5000000/18 = 277,778 blocchi.

Ora una ricerca usando il nome di battesimo campo può utilizzare l'indice per aumentare le prestazioni. Ciò consente una ricerca binaria dell'indice con una media di log2 277778 = 18.08 = 19 bloccare gli accessi. Per trovare l'indirizzo del record attuale, che richiede un ulteriore accesso al blocco da leggere, portando il totale a 19 + 1 = 20 bloccare gli accessi, ben lontano dai 1.000.000 di accessi al blocco richiesti per trovare a nome di battesimo corrisponde nella tabella non indicizzata.

Quando dovrebbe essere usato?

Dato che la creazione di un indice richiede spazio su disco aggiuntivo (277.778 blocchi in più rispetto all'esempio precedente, un aumento del ~ 28%) e che troppi indici possono causare problemi derivanti dai limiti di dimensione del file system, occorre prestare attenzione per selezionare il corretto campi da indicizzare.

Poiché gli indici sono utilizzati solo per accelerare la ricerca di un campo corrispondente all'interno dei record, è ovvio che i campi di indicizzazione utilizzati solo per l'output sarebbero semplicemente uno spreco di spazio su disco e tempo di elaborazione quando si esegue un'operazione di inserimento o cancellazione, e quindi dovrebbe essere evitato. Anche data la natura di una ricerca binaria, la cardinalità o l'unicità dei dati è importante. L'indicizzazione su un campo con cardinalità pari a 2 dividerebbe i dati a metà, mentre una cardinalità di 1.000 restituirebbe circa 1.000 record. Con una cardinalità così bassa l'efficacia è ridotta a un ordinamento lineare e Query Optimizer eviterà di utilizzare l'indice se la cardinalità è inferiore al 30% del numero di record, rendendo effettivamente l'indice uno spreco di spazio.


2846
2017-08-04 10:41



La prima volta che ho letto questo è stato molto utile per me. Grazie.

Da allora ho acquisito alcune informazioni sul lato negativo della creazione di indici: se scrivi in ​​una tabella (UPDATE o INSERT) con un indice, in realtà ci sono due operazioni di scrittura nel file system. Uno per i dati della tabella e un altro per i dati dell'indice (e il ricorrere di esso (e - se raggruppato - il ricorso ai dati della tabella)). Se la tabella e l'indice si trovano sullo stesso disco rigido, ciò richiede più tempo. Quindi una tabella senza un indice (un heap), consentirebbe operazioni di scrittura più veloci. (se avessi due indici avresti finito con tre operazioni di scrittura, e così via)

Tuttavia, la definizione di due posizioni diverse su due dischi rigidi diversi per dati indice e dati tabella può ridurre / eliminare il problema di un aumento del costo del tempo. Ciò richiede la definizione di gruppi di file aggiuntivi con file corrispondenti sui dischi rigidi desiderati e la definizione di posizione tabella / indice come desiderato.

Un altro problema con gli indici è la loro frammentazione nel tempo man mano che i dati vengono inseriti. REORGANIZE aiuta, devi scrivere routine per averlo fatto.

In alcuni scenari un heap è più utile di una tabella con indici,

ad esempio: - Se hai molte scritture rivali, solo una lettura letta al di fuori dell'orario di lavoro per la segnalazione.

Inoltre, una differenziazione tra indici cluster e non cluster è piuttosto importante.

Mi ha aiutato:- Cosa significa in realtà l'indice Clustered e Non clustered?


175
2018-04-30 14:31



Un indice è solo una struttura dati che rende la ricerca più veloce per una colonna specifica in un database. Questa struttura di solito è una b-tree o una tabella hash ma può essere qualsiasi altra struttura logica.

Per maggiori informazioni, consiglio: Come funzionano gli indici di database? E come aiutano gli indici?


130
2018-02-20 14:40



Ora, diciamo che vogliamo eseguire una query per trovare tutti i dettagli di tutti i dipendenti che si chiamano 'Abc'?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

Cosa succederebbe senza un indice?

Il software del database dovrebbe letteralmente guardare ogni singola riga nella tabella Employee per vedere se Employee_Name per quella riga è 'Abc'. E poiché vogliamo che ogni riga con il nome "Abc" al suo interno, non possiamo semplicemente smettere di cercare una volta che troviamo solo una riga con il nome "Abc", perché potrebbero esserci altre righe con il nome abc. Quindi, ogni riga fino all'ultima riga deve essere cercata, il che significa che migliaia di righe in questo scenario dovranno essere esaminate dal database per trovare le righe con il nome 'Abc'. Questo è ciò che viene chiamato a scansione completa della tabella

Come un indice di database può aiutare le prestazioni

L'intero punto di avere un indice è di accelerare le query di ricerca essenzialmente riducendo il numero di record / righe in una tabella che devono essere esaminati. Un indice è una struttura di dati (più comunemente un albero B) che memorizza i valori per una colonna specifica in una tabella.

Come funziona l'indice B-trees?

Il motivo per cui gli alberi B sono la struttura dati più popolare per gli indici è dovuto al fatto che sono efficienti in termini di tempo, poiché le operazioni di ricerca, eliminazione e inserimento possono essere eseguite in tempo logaritmico. E un altro motivo importante per cui gli alberi B sono più comunemente usati è perché i dati che sono memorizzati all'interno dell'albero B possono essere ordinati. L'RDBMS determina in genere quale struttura dati viene effettivamente utilizzata per un indice. Tuttavia, in alcuni scenari con determinati RDBMS, è possibile specificare la struttura dati che si desidera venga utilizzata dal database quando si crea l'indice stesso.

Come funziona un indice della tabella hash?

Il motivo per cui gli indici hash vengono utilizzati è perché le tabelle hash sono estremamente efficienti quando si tratta di cercare solo i valori. Pertanto, le query che confrontano l'uguaglianza con una stringa possono recuperare i valori molto velocemente se utilizzano un indice hash.

Ad esempio, la query che abbiamo discusso in precedenza potrebbe trarre vantaggio da un indice hash creato nella colonna Employee_Name. Il modo in cui un indice hash funzionerebbe è che il valore della colonna sarà la chiave nella tabella hash e il valore effettivo associato a quella chiave sarebbe solo un puntatore ai dati della riga nella tabella. Dato che una tabella hash è fondamentalmente un array associativo, una voce tipica apparirebbe come "Abc => 0x28939", dove 0x28939 è un riferimento alla riga della tabella in cui Abc è memorizzato. Cercare un valore come "Abc" in un indice tabella hash e recuperare un riferimento alla riga in memoria è ovviamente molto più veloce della scansione della tabella per trovare tutte le righe con il valore "Abc" nella colonna Employee_Name.

Gli svantaggi di un indice di hash

Le tabelle hash non sono strutture dati ordinate e ci sono molti tipi di query a cui gli indici hash non possono nemmeno aiutare. Ad esempio, supponiamo di voler scoprire tutti i dipendenti che hanno meno di 40 anni. Come hai potuto farlo con un indice di tabella hash? Beh, non è possibile perché una tabella hash è utile solo per cercare coppie di valori chiave - il che significa query che controllano l'uguaglianza

Cosa c'è esattamente all'interno di un indice del database? Quindi, ora sai che un indice di database viene creato su una colonna in una tabella e che l'indice memorizza i valori in quella specifica colonna. Ma è importante capire che un indice del database non memorizza i valori nelle altre colonne della stessa tabella. Ad esempio, se creiamo un indice nella colonna Employee_Name, ciò significa che i valori delle colonne Employee_Age e Employee_Address non vengono memorizzati anche nell'indice. Se abbiamo archiviato tutte le altre colonne nell'indice, sarebbe come creare un'altra copia dell'intera tabella, che occuperebbe troppo spazio e sarebbe molto inefficiente.

Come fa un database a sapere quando usare un indice? Quando viene eseguita una query come "SELECT * FROM Employee WHERE Employee_Name = 'Abc'", il database controlla se c'è un indice sulle colonne interrogate. Supponendo che la colonna Employee_Name abbia un indice creato su di esso, il database dovrà decidere se ha effettivamente senso usare l'indice per trovare i valori ricercati - perché ci sono alcuni scenari in cui è effettivamente meno efficiente usare l'indice del database e più efficiente solo per eseguire la scansione dell'intero tavolo.

Qual è il costo di avere un indice di database?

Prende spazio - e più grande è il tuo tavolo, più grande è il tuo indice. Un'altra performance colpita dagli indici è il fatto che ogni volta che aggiungi, cancelli o aggiorni le righe nella tabella corrispondente, le stesse operazioni dovranno essere eseguite nel tuo indice. Ricorda che un indice deve contenere gli stessi dati fino al minuto di qualunque cosa si trovi nelle colonne della tabella che l'indice copre.

Come regola generale, un indice dovrebbe essere creato su una tabella solo se i dati nella colonna indicizzata verranno interrogati frequentemente.

Guarda anche

  1. Quali colonne generano generalmente buoni indici?
  2. Come funzionano gli indici di database

93
2017-08-13 18:36



Esempio classico "Indice nei libri"

Considera un "Libro" di 1000 pagine, diviso per 100 sezioni, ciascuna sezione con X pagine.

Semplice, eh?

Ora, senza una pagina indice, per trovare una particolare sezione che inizia con la lettera "S", non hai altra scelta che scansionare l'intero libro. vale a dire: 1000 pagine

Ma con una pagina indice all'inizio, ci sei. E ancora, per leggere qualsiasi sezione particolare che conta, basta guardare la pagina indice, ancora e ancora, ogni volta. Dopo aver trovato l'indice di corrispondenza puoi saltare in modo efficiente alla sezione saltando altre sezioni.

Ma poi, oltre a 1000 pagine, avrai bisogno di un altro ~ 10 pagine per visualizzare la pagina indice, quindi totalmente 1010 pagine.

Pertanto, l'indice è una sezione separata che memorizza i valori della colonna indicizzata + puntatore alla riga indicizzata in un ordine ordinato per ricerche efficienti.

Le cose sono semplici nelle scuole, non è vero? : P


82
2018-04-23 14:43



Descrizione semplice !!!!!!!!!!

L'indice non è altro che una struttura dati che memorizza i valori per una colonna specifica in una tabella. Un indice viene creato su una colonna di una tabella.

Esempio, abbiamo una tabella di database chiamata Utente con tre colonne: Nome, Età e Indirizzo. Supponiamo che la tabella User abbia migliaia di righe.

Ora, diciamo che vogliamo eseguire una query per trovare tutti i dettagli di tutti gli utenti che si chiamano "John". Se eseguiamo la seguente query.

SELECT * FROM User 
WHERE Name = 'John'

Il software di database dovrebbe letteralmente guardare ogni singola riga nella tabella Utente per vedere se il Nome per quella riga è 'Giovanni'. Questo richiederà molto tempo.
Questo è il punto in cui l'indice ci aiuta "l'indice viene utilizzato per accelerare le query di ricerca riducendo sostanzialmente il numero di record / righe in una tabella che deve essere esaminata".
Come creare un indice

CREATE INDEX name_index
ON User (Name)

Un indice è costituito da valori di colonna (ad esempio: John) di una tabella e tali valori sono memorizzati in una struttura di dati.
Così ora il database utilizzerà l'indice per trovare dipendenti di nome John perché l'indice sarà presumibilmente ordinato alfabeticamente in base al nome degli utenti. E, poiché è ordinato, significa che cercare un nome è molto più veloce perché tutti i nomi che iniziano con una "J" saranno proprio uno accanto all'altro nell'indice!


46
2017-08-02 01:30



Solo un rapido suggerimento .. Poiché l'indicizzazione ti costa scritture e spazio di archiviazione aggiuntivi, quindi se l'applicazione richiede più operazioni di inserimento / aggiornamento, potresti voler utilizzare tabelle senza indici, ma se richiede più operazioni di recupero dei dati, devi andare per indicizzato tavolo.


21
2018-01-14 06:44



Basti pensare all'indice del database come indice di un libro.  Se hai un libro sui cani e vuoi trovare informazioni su, diciamo, pastori tedeschi, puoi ovviamente sfogliare tutte le pagine del libro e trovare ciò che stai cercando, ma questo naturalmente richiede tempo e non molto veloce. Un'altra opzione è che puoi semplicemente andare alla sezione Indice del libro e trovare ciò che stai cercando usando il Nome dell'entità che stai cercando (in questo caso, Pastori tedeschi) e anche guardando il numero di pagina per trova rapidamente ciò che stai cercando. Nel Database, il numero di pagina viene definito puntatore che indirizza il database all'indirizzo sul disco in cui si trova l'entità. Usando la stessa analogia con il pastore tedesco, potremmo avere qualcosa del genere ("Pastore tedesco", 0x77129) dove 0x77129 è l'indirizzo sul disco in cui sono memorizzati i dati delle righe per Pastore tedesco.

In breve, un indice è una struttura di dati che memorizza i valori per una colonna specifica in una tabella in modo da accelerare la ricerca di query.


16
2017-12-21 17:16



L'indice SQL è qualcosa correlato ad accelerare la ricerca nel database SQL. L'indice consente al programmatore di recuperare i dati dal database molto velocemente. Supponi di essere uno studente o un lettore di libri. Il tuo libro contiene 50.000 pagine. Il primo giorno leggi qualche argomento "ABC" il giorno dopo vuoi leggere qualche altro argomento "xyz". non passerai mai manualmente pagina per pagina. Quello che farai in questa situazione è usare l'indice del libro per cercare l'argomento specifico e poi saltare direttamente al tuo argomento. L'indice ha risparmiato un sacco di tempo per cercare argomenti. Lo stesso nell'indice SQL, Index consente di cercare milioni di record molto velocemente dal database.


10
2018-02-15 10:17