Domanda

Dato che l'indicizzazione è così importante man mano che 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, consulta Come indicizzo una colonna del database.

È stato utile?

Soluzione

Perché è necessario?

Quando i dati vengono archiviati su dispositivi di archiviazione basati su disco, vengono archiviati come blocchi di dati.A questi blocchi si accede nella loro interezza, rendendoli l'operazione di accesso al disco atomico.I blocchi del disco sono strutturati più o meno allo stesso modo degli elenchi collegati;entrambi contengono una sezione per i dati, un puntatore alla posizione del nodo (o blocco) successivo ed entrambi non necessitano di essere archiviati in modo contiguo.

Dato che più record possono essere ordinati solo su un campo, possiamo affermare che la ricerca su un campo non ordinato richiede una Ricerca Lineare che richiede N/2 bloccare gli accessi (in media), dove N è il numero di blocchi su cui si estende la tabella.Se il campo è un campo non chiave (ad es.non contiene voci univoche), è necessario effettuare la ricerca nell'intero tablespace N bloccare gli accessi.

Mentre con un campo ordinato è possibile utilizzare 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 valori duplicati nel resto della tabella, una volta trovato un valore più alto.Pertanto l'aumento delle prestazioni è sostanziale.

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 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 archiviati insieme in una tabella utilizzando il motore MyISAM, questo file può raggiungere rapidamente i limiti di dimensione del file system sottostante se vengono indicizzati molti campi all'interno della stessa tabella .

Come funziona?

Innanzitutto, delineamo uno schema di tabella di 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 utilizzato al posto di varchar per consentire una dimensione precisa 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 utilizza il file id (un campo chiave ordinato) e uno che utilizza il file nome di battesimo (un campo non ordinato non chiave).

Esempio 1 - campi ordinati e non ordinati

Dato il nostro database di esempio di r = 5,000,000 record di dimensione fissa che forniscono una lunghezza record di R = 204 byte e vengono archiviati 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 di disco.Il numero totale di blocchi necessari per mantenere 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 bloccare gli accessi 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 bloccare gli accessi.Possiamo subito vedere che si tratta di un drastico miglioramento.

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 valore esatto N = 1,000,000 bloccare gli accessi.È questa situazione che l’indicizzazione mira a correggere.

Dato che un record indice contiene solo il campo indicizzato e un puntatore al record originale, è ovvio che sarà più piccolo del record multicampo a cui punta.Pertanto l'indice stesso richiede meno blocchi del disco rispetto alla tabella originale, che quindi richiede meno accessi ai blocchi per l'iterazione.Lo schema per un indice su nome di battesimo il campo è descritto 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 del record 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 di disco.Il numero totale di blocchi richiesti per contenere l'indice è N = (r/bfr) = 5000000/18 = 277,778 blocchi.

Ora una ricerca utilizzando il file 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 vero e proprio, che richiede un ulteriore blocco dell'accesso in lettura, portando il totale a 19 + 1 = 20 bloccare gli accessi, ben lontani dai 1.000.000 di accessi in blocco necessari per trovare un file nome di battesimo corrispondenza 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 di circa il 28%) e che troppi indici possono causare problemi derivanti dai limiti di dimensione dei file system, è necessario prestare attenzione per selezionare quello corretto campi da indicizzare.

Poiché gli indici vengono utilizzati solo per velocizzare la ricerca di un campo corrispondente all'interno dei record, è ovvio che indicizzare i campi utilizzati solo per l'output sarebbe semplicemente uno spreco di spazio su disco e 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 cardinalità 2 dividerebbe i dati a metà, mentre una cardinalità 1.000 restituirebbe circa 1.000 record.Con una cardinalità così bassa l'efficacia si riduce a un ordinamento lineare e il Query Optimizer eviterà di utilizzare l'indice se la cardinalità è inferiore al 30% del numero del record, rendendo di fatto l'indice uno spreco di spazio.

Altri suggerimenti

La prima volta che l'ho letto mi è stato molto utile.Grazie.

Da allora ho acquisito alcune informazioni sugli svantaggi della creazione di indici:se scrivi in ​​una tabella (UPDATE O INSERT) con un indice, hai in realtà due operazioni di scrittura nel file system.Uno per i dati della tabella e un altro per i dati dell'indice (e il suo riordino (e, se raggruppati, il riordino dei dati della tabella)).Se la tabella e l'indice si trovano sullo stesso disco rigido, ciò richiede più tempo.Pertanto una tabella senza indice (un heap) consentirebbe operazioni di scrittura più rapide.(se avessi due indici ti ritroveresti con tre operazioni di scrittura e così via)

Tuttavia, la definizione di due posizioni diverse su due dischi rigidi diversi per i dati dell'indice e per i dati della tabella può ridurre/eliminare il problema dell'aumento del costo del tempo.Ciò richiede la definizione di gruppi di file aggiuntivi con i file corrispondenti sui dischi rigidi desiderati e la definizione della posizione della 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 farlo.

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

ad esempio: - Se hai molte scritture rivali ma solo una lettura notturna al di fuori dell'orario lavorativo per la reportistica.

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

Mi ha aiutato:- Cosa significano effettivamente gli indici clusterizzati e non clusterizzati?

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

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 di indice, per trovare una sezione particolare che inizia con la lettera "S", non hai altra scelta che scansionare l'intero libro.cioè:1000 pagine

Ma con una pagina indice all'inizio, sei lì.Inoltre, per leggere una sezione particolare che conta, devi solo guardare la pagina dell'indice, ancora e ancora, ogni volta.Dopo aver trovato l'indice corrispondente puoi saltare in modo efficiente alla sezione saltando altre sezioni.

Ma poi, oltre a 1000 pagine, avrai bisogno di altre circa 10 pagine per visualizzare la pagina dell'indice, quindi in totale 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

Ora, supponiamo di voler eseguire una query per trovare tutti i dettagli di tutti i dipendenti denominati "Abc"?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

Cosa accadrebbe senza un indice?

Il software del database dovrebbe letteralmente esaminare 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 trovata solo una riga con il nome "Abc", perché potrebbero esserci altre righe con il nome Abc.Pertanto, è necessario cercare ogni riga fino all'ultima riga, 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

Lo scopo principale di avere un indice è accelerare le query di ricerca riducendo essenzialmente il numero di record/righe in una tabella che devono essere esaminati.Un indice è una struttura 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 i B-tree sono la struttura dati più popolare per gli indici è dovuto al fatto che sono efficienti in termini di tempo, poiché le ricerche, le eliminazioni e gli inserimenti possono essere eseguiti in tempo logaritmico.Inoltre, un altro motivo importante per cui i B-tree sono più comunemente utilizzati è perché i dati archiviati all'interno del B-tree possono essere ordinati.L'RDBMS in genere determina quale struttura dati viene effettivamente utilizzata per un indice.Ma, in alcuni scenari con determinati RDBMS, puoi effettivamente specificare quale struttura dati desideri che il tuo database utilizzi quando crei l'indice stesso.

Come funziona un indice di 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.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 discussa in precedenza potrebbe trarre vantaggio da un indice hash creato nella colonna Employee_Name.Il modo in cui funzionerebbe un indice hash è che il valore della colonna sarà la chiave nella tabella hash e il valore effettivo mappato su quella chiave sarebbe semplicemente un puntatore ai dati della riga nella tabella.Poiché una tabella hash è fondamentalmente un array associativo, una voce tipica sarebbe simile a "Abc => 0x28939", dove 0x28939 è un riferimento alla riga della tabella in cui Abc è archiviato in memoria.Cercare un valore come "Abc" nell'indice di una tabella hash e ottenere un riferimento alla riga in memoria è ovviamente molto più veloce che scansionare la tabella per trovare tutte le righe con un valore "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 con le quali gli indici hash non possono nemmeno essere d'aiuto.Ad esempio, supponiamo di voler scoprire tutti i dipendenti che hanno meno di 40 anni.Come potresti farlo con un indice di tabella hash?Bene, non è possibile perché una tabella hash è utile solo per cercare coppie chiave-valore, il che significa query che verificano l'uguaglianza

Cosa c'è esattamente all'interno di un indice di database?Quindi, ora sai che un indice del database viene creato su una colonna di una tabella e che l'indice memorizza i valori in quella colonna specifica.Ma è importante capire che un indice di 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 archiviati nell'indice.Se memorizzassimo solo tutte le altre colonne nell'indice, sarebbe come creare un'altra copia dell'intera tabella, il 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 controllerà per vedere se è presente un indice sulle colonne interrogate.Supponendo che la colonna Employee_Name abbia un indice creato su di essa, il database dovrà decidere se ha effettivamente senso utilizzare l'indice per trovare i valori da cercare, 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 è la tua tabella, più grande è il tuo indice.Un altro problema di prestazioni con gli indici è il fatto che ogni volta che aggiungi, elimini o aggiorni righe nella tabella corrispondente, le stesse operazioni dovranno essere eseguite sul tuo indice.Ricordare che un indice deve contenere gli stessi dati aggiornati al minuto presenti nelle colonne della tabella coperte dall'indice.

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 generalmente costituiscono buoni indici?
  2. Come funzionano gli indici dei database

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.

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

Ora, supponiamo di voler eseguire una query per trovare tutti i dettagli di tutti gli utenti chiamati "John".Se eseguiamo la seguente query.

SELECT * FROM User 
WHERE Name = 'John'

Il software del database dovrebbe letteralmente esaminare ogni singola riga nella tabella Utente per vedere se il nome di quella riga è "John".Ciò richiederà molto tempo.
È qui che l'indice ci aiuta "l'indice viene utilizzato per accelerare le query di ricerca riducendo essenzialmente 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) da una tabella e che tali valori siano archiviati in una struttura dati.
Quindi ora il database utilizzerà l'indice per trovare i dipendenti chiamati John perché l'indice sarà presumibilmente ordinato alfabeticamente in base al nome dell'utente.E, poiché è ordinato, significa che la ricerca di un nome è molto più veloce perché tutti i nomi che iniziano con una "J" saranno uno accanto all'altro nell'indice!

Solo un veloce suggerimento..Poiché l'indicizzazione costa scritture aggiuntive e spazio di archiviazione, quindi se la tua applicazione richiede più operazioni di inserimento/aggiornamento, potresti voler utilizzare tabelle senza indici, ma se richiede più operazioni di recupero dati, dovresti optare per la tabella indicizzata.

Basti pensare all'indice del database come all'indice di un libro.Se hai un libro sui cani e vuoi trovare informazioni, diciamo, sui pastori tedeschi, potresti ovviamente sfogliare tutte le pagine del libro e trovare quello che stai cercando, ma questo ovviamente richiede molto tempo e non è molto utile. veloce.Un'altra opzione è che potresti semplicemente andare alla sezione Indice del libro e trovare ciò che stai cercando utilizzando il nome dell'entità che stai cercando (in questo caso, pastori tedeschi) e guardando anche il numero di pagina per trova velocemente quello che cerchi.In 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 del pastore tedesco, potremmo avere qualcosa del genere (“Pastore tedesco”, 0x77129) dove 0x77129 è l'indirizzo sul disco in cui sono archiviati i dati della riga per il pastore tedesco.

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

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top