non - sql indici tabelle




Come funziona l'indicizzazione del database? (6)

Descrizione semplice!

L'indice non è altro che una struttura di 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 User con tre colonne: Name , Age e Address . Supponiamo che la tabella User contenga migliaia di righe.

Diciamo ora 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 del database dovrebbe letteralmente guardare ogni singola riga nella tabella User per vedere se il Name per quella riga è 'John'. Questo richiederà molto tempo.

È qui che l' index ci aiuta: l' indice viene utilizzato per accelerare le query di ricerca essenzialmente riducendo il numero di record / righe in una tabella che deve essere esaminata .

Come creare un indice:

CREATE INDEX name_index
ON User (Name)

Un index costituito da valori di colonna (ad es. John) da una tabella e tali valori sono memorizzati in una struttura di dati .

Quindi ora il database utilizzerà l'indice per trovare i dipendenti di nome John perché l'indice sarà presumibilmente ordinato in ordine alfabetico 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 uno accanto all'altro nell'indice!

Dato che l'indicizzazione è così importante all'aumentare delle dimensioni del set di dati, qualcuno può spiegare come funziona l'indicizzazione a livello di database indipendente?

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


Basti pensare all'indice del database come all'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 quello che stai cercando, ma questo ovviamente richiede tempo e non molto veloce.

Un'altra opzione è che, potresti semplicemente andare alla sezione Indice del libro e quindi trovare quello che stai cercando utilizzando il Nome dell'entità che stai cercando (in questo caso, Pastori tedeschi) e anche guardando il numero di pagina per trova rapidamente quello che stai cercando.

Nel database, il numero di pagina viene indicato come un puntatore che indirizza il database all'indirizzo sul disco in cui si trova l'entità. Usando la stessa analogia di German Shepherd, potremmo avere qualcosa del genere ("German Shepherd", 0x77129) dove 0x77129 è l'indirizzo sul disco in cui sono memorizzati i dati di riga per German Shepherd.

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


La prima volta che ho letto questo mi è stato molto utile. 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à hai due operazioni di scrittura nel file system. Uno per i dati della tabella e un altro per i dati dell'indice (e il loro ricorso (e - se raggruppati - il ricorso ai dati della tabella)). Se la tabella e l'indice si trovano sullo stesso disco rigido, ciò costa più tempo. Pertanto una tabella senza un indice (un heap) consentirebbe operazioni di scrittura più rapide. (se avessi due indici, finiresti con tre operazioni di scrittura e così via)

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

Un altro problema con gli indici è la loro frammentazione nel tempo quando vengono inseriti i dati. REORGANIZE aiuta, è necessario scrivere routine per farlo.

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

ad esempio: - Se hai molte scritture concorrenti ma solo una notte leggi fuori dall'orario di lavoro per la segnalazione.

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

Mi ha aiutato: - Cosa significano realmente gli indici cluster e non cluster?


Ora, diciamo che vogliamo eseguire una query per trovare tutti i dettagli di tutti i dipendenti che sono chiamati "Abc"?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

Cosa accadrebbe 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 ogni riga con il nome "Abc" al suo interno, non possiamo smettere di cercare una volta trovata 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 scansione completa della tabella

In che modo un indice del database può aiutare le prestazioni

Il punto fondamentale di avere un indice è velocizzare 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 di dati più popolare per gli indici è dovuto al fatto che sono efficienti in termini di tempo, poiché è possibile effettuare ricerche, eliminazioni e inserimenti in tempo logaritmico. Inoltre, un altro dei principali motivi per cui gli alberi B vengono utilizzati più comunemente è perché i dati memorizzati all'interno dell'albero B possono essere ordinati. Il RDBMS determina in genere quale struttura di dati viene effettivamente utilizzata per un indice. Ma, in alcuni scenari con determinati RDBMS, puoi effettivamente specificare quale struttura di dati vuoi che il tuo database utilizzi quando crei l'indice stesso.

Come funziona un indice della tabella hash?

Il motivo per cui vengono utilizzati gli indici hash è perché le tabelle hash sono estremamente efficienti quando si tratta solo di cercare valori. Quindi, le query che confrontano per uguaglianza con una stringa possono recuperare valori molto velocemente se usano 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 mappato a quella chiave sarebbe solo un puntatore ai dati di riga nella tabella. Poiché una tabella hash è fondamentalmente un array associativo, una voce tipica assomiglierebbe a "Abc => 0x28939", dove 0x28939 è un riferimento alla riga della tabella in cui è memorizzato Abc. Cercare un valore come "Abc" in un indice di una tabella hash e recuperare un riferimento alla riga in memoria è ovviamente molto più veloce della scansione della tabella per trovare tutte le righe con un valore di "Abc" nella colonna Employee_Name.

Gli svantaggi di un indice hash

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

Cosa si trova esattamente all'interno di un indice del database? Quindi, ora sai che un indice del database viene creato su una colonna in una tabella e che l'indice memorizza i valori in quella colonna specifica. Tuttavia, è importante comprendere che un indice del database non memorizza i valori nelle altre colonne della stessa tabella. Ad esempio, se creiamo un indice sulla colonna Employee_Name, ciò significa che anche i valori delle colonne Employee_Age e Employee_Address non vengono memorizzati nell'indice. Se memorizzassimo semplicemente 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 utilizzare un indice? Quando viene eseguita una query come "SELECT * FROM Employee WHERE Employee_Name = 'Abc'", il database verificherà se è presente un indice sulle colonne da interrogare. Supponendo che la colonna Employee_Name abbia un indice creato su di esso, il database dovrà decidere se ha effettivamente senso utilizzare l'indice per trovare i valori ricercati, perché ci sono alcuni scenari in cui è effettivamente meno efficiente utilizzare l'indice del database e più efficiente solo per scansionare l'intera tabella.

Qual è il costo di avere un indice del database?

Occupa spazio - e più grande è il tuo tavolo, più grande è il tuo indice. Un altro risultato in termini di prestazioni con gli indici è il fatto che ogni volta che aggiungi, elimini o aggiorni le righe nella tabella corrispondente, le stesse operazioni dovranno essere fatte al tuo indice. Ricorda che un indice deve contenere gli stessi dati fino al minuto di qualsiasi cosa si trovi nelle colonne della tabella coperte dall'indice.

Come regola generale, un indice deve 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 del database

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


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 in modo molto simile agli elenchi collegati; entrambi contengono una sezione per i dati, un puntatore alla posizione del nodo (o blocco) successivo ed entrambi non devono essere archiviati in modo contiguo.

A causa del fatto che un certo 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 accessi al blocco N/2 (in media), dove N è il numero di blocchi che la tabella occupa. Se quel campo è un campo non chiave (ovvero non contiene voci univoche), è necessario cercare l'intero tablespace agli accessi a N blocchi.

Considerando che con un campo ordinato, può essere utilizzata una ricerca binaria, che ha accessi al blocco log2 N log2. Inoltre, poiché i dati vengono ordinati in base a un campo non chiave, non è necessario cercare valori duplicati nel resto della tabella, una volta trovato un valore più elevato. Pertanto l'aumento delle prestazioni è notevole.

Che cos'è l'indicizzazione?

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

Il lato negativo dell'indicizzazione è che questi indici richiedono spazio aggiuntivo sul disco poiché gli indici sono memorizzati insieme in una tabella usando 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?

Innanzitutto, delineamo uno schema di tabella del database di esempio;

Field name       Data type      Size on disk
id (Primary key) Unsigned INT   4 bytes
firstName        Char(50)       50 bytes
lastName         Char(50)       50 bytes
emailAddress     Char(100)      100 bytes

Nota : char è stato usato al posto di varchar per consentire una dimensione accurata sul valore del disco. Questo database di esempio contiene cinque milioni di righe ed è non indicizzato. Verranno ora analizzate le prestazioni di diverse query. Si tratta di una query che utilizza l' id (un campo chiave ordinato) e uno che utilizza firstName (un campo non ordinato non chiave).

Esempio 1 : campi ordinati o non ordinati

Dato il nostro database di esempio di r = 5,000,000 record di dimensioni fisse che forniscono una lunghezza record di R = 204 byte e vengono memorizzati in una tabella utilizzando il motore MyISAM che utilizza la dimensione del blocco predefinita B = 1,024 byte. Il fattore di blocco della tabella sarebbe bfr = (B/R) = 1024/204 = 5 record per blocco del disco. Il numero totale di blocchi richiesti 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 accessi a blocco per trovare un valore, dato che il campo ID è un campo chiave. Ma poiché anche il campo ID è ordinato, è possibile condurre una ricerca binaria che richiede una media di log2 1000000 = 19.93 = 20 accessi a blocchi. Immediatamente possiamo vedere che questo è un drastico miglioramento.

Ora il campo firstName 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 esatto accesso N = 1,000,000 blocchi. È 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, è logico che sarà più piccolo del record a più campi a cui punta. Quindi l'indice stesso richiede un numero inferiore di blocchi del disco rispetto alla tabella originale, che pertanto richiede meno accessi ai blocchi per scorrere. Lo schema per un indice nel campo firstName è delineato di seguito;

Field name       Data type      Size on disk
firstName        Char(50)       50 bytes
(record pointer) Special        4 bytes

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

Esempio 2 - indicizzazione

Dato il nostro database di esempio di r = 5,000,000 record con una lunghezza record di indice di R = 54 byte e utilizzando la dimensione del 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 richiesti per contenere l'indice è N = (r/bfr) = 5000000/18 = 277,778 blocchi.

Ora una ricerca che utilizza il campo firstName può utilizzare l'indice per aumentare le prestazioni. Ciò consente una ricerca binaria dell'indice con una media di log2 277778 = 18.08 = 19 accessi a blocchi. Per trovare l'indirizzo del record effettivo, che richiede un ulteriore accesso al blocco per la lettura, portando il totale a 19 + 1 = 20 accessi al blocco, un grido lontano dai 1.000.000 di accessi al blocco richiesti per trovare una corrispondenza firstName 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ù dall'esempio precedente, un aumento del ~ 28%) e che troppi indici possono causare problemi derivanti dai limiti di dimensione dei file system, è necessario usare un pensiero attento per selezionare il corretto campi da indicizzare.

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





database-indexes