Vraag Hoe werkt database-indexering?


Aangezien indexeren zo belangrijk is omdat uw gegevensset in omvang toeneemt, kan iemand dan uitleggen hoe indexering werkt op een database-agnostisch niveau?

Raadpleeg voor meer informatie over query's om een ​​veld te indexeren Hoe indexeer ik een databasekolom.


1873
2017-08-04 10:07


oorsprong


antwoorden:


Waarom is het nodig?

Wanneer gegevens worden opgeslagen op schijfgebaseerde opslagapparaten, worden deze opgeslagen als datablokken. Deze blokken zijn volledig toegankelijk en vormen daarmee de toegang tot de atomaire schijf. Schijfblokken zijn op ongeveer dezelfde manier gestructureerd als gekoppelde lijsten; beide bevatten een sectie voor gegevens, een verwijzing naar de locatie van het volgende knooppunt (of blok), en beide hoeven niet aangrenzend te worden opgeslagen.

Omdat een aantal records alleen op één veld kan worden gesorteerd, kunnen we stellen dat voor het zoeken op een veld dat niet is gesorteerd, een lineaire zoekopdracht vereist is. N/2 blokkeert toegang (gemiddeld), waar N is het aantal blokken dat de tabel overspant. Als dat veld een niet-sleutelveld is (dat wil zeggen dat het geen unieke ingangen bevat), moet naar de volledige tabelruimte worden gezocht N toegang blokkeren.

Overwegende dat met een gesorteerd veld, een binaire zoekopdracht kan worden gebruikt, die log2 N toegang blokkeren. Ook omdat de gegevens zijn gesorteerd op basis van een veld zonder sleutel, hoeft de rest van de tabel niet te worden gezocht naar dubbele waarden, zodra een hogere waarde is gevonden. Dus de prestatieverhoging is aanzienlijk.

Wat is indexeren?

Indexeren is een manier om een ​​aantal records op meerdere velden te sorteren. Door een index op een veld in een tabel te maken, wordt een andere gegevensstructuur gemaakt met de veldwaarde en een aanwijzer naar de record waarmee deze is verbonden. Deze indexstructuur wordt vervolgens gesorteerd, zodat er binaire zoekopdrachten op kunnen worden uitgevoerd.

Het nadeel van indexeren is dat deze indexen extra ruimte op de schijf vereisen, omdat de indexen samen in een tabel worden opgeslagen met behulp van de MyISAM-engine. Dit bestand kan snel de maximale grootte van het onderliggende bestandssysteem bereiken als veel velden binnen dezelfde tabel worden geïndexeerd .

Hoe werkt het?

Laten we eerst een voorbeeld van een databasetabelschema schetsen;

Veldnaam Gegevenstype Grootte op schijf
id (primaire sleutel) Niet-ondertekende INT 4 bytes
firstName Char (50) 50 bytes
lastName Char (50) 50 bytes
emailAdres Char (100) 100 bytes

Notitie: char werd gebruikt in plaats van varchar om een ​​nauwkeurige grootte op de schijfwaarde mogelijk te maken. Deze voorbeelddatabase bevat vijf miljoen rijen en is niet-geïndexeerd. De prestaties van verschillende zoekopdrachten worden nu geanalyseerd. Dit zijn een query met behulp van de ID kaart (een veld met een gesorteerde sleutel) en een met de Voornaam (een niet-sleutel ongesorteerd veld).

voorbeeld 1 - gesorteerd versus ongesorteerde velden

Gezien onze voorbeelddatabase van r = 5,000,000 records van een vaste grootte geven een recordlengte van R = 204 bytes en ze worden opgeslagen in een tabel met behulp van de MyISAM-engine die de standaardblokgrootte gebruikt B = 1,024bytes. De blokkerende factor van de tabel zou zijn bfr = (B/R) = 1024/204 = 5 records per schijfblok. Het totale aantal blokken dat nodig is om de tabel te houden is N = (r/bfr) = 5000000/5 = 1,000,000 blokken.

Een lineaire zoekopdracht op het veld id zou een gemiddelde van vereisen N/2 = 500,000 toegang blokkeren om een ​​waarde te vinden, aangezien het veld id een sleutelveld is. Maar aangezien het id-veld ook is gesorteerd, kan een binaire zoekopdracht worden uitgevoerd waarvoor een gemiddelde van nodig is log2 1000000 = 19.93 = 20 toegang blokkeren. We kunnen meteen zien dat dit een drastische verbetering is.

Nu de Voornaam veld is noch gesorteerd, noch een sleutelveld, dus een binaire zoekopdracht is niet mogelijk, noch zijn de waarden uniek, en daarom zal de tabel moeten zoeken naar het einde voor een exacte N = 1,000,000 toegang blokkeren. In deze situatie wil indexeren corrigeren.

Aangezien een indexrecord alleen het geïndexeerde veld en een pointer naar de oorspronkelijke record bevat, spreekt het vanzelf dat deze kleiner is dan de multi-field record waarnaar de record verwijst. De index zelf vereist dus minder schijfblokken dan de oorspronkelijke tabel, waardoor er daarom minder bloktoegangen nodig zijn om te doorlopen. Het schema voor een index op de Voornaam veld is hieronder beschreven;

Veldnaam Gegevenstype Grootte op schijf
firstName Char (50) 50 bytes
(record pointer) Speciale 4 bytes

Notitie: Pointers in MySQL zijn 2, 3, 4 of 5 bytes lang, afhankelijk van de grootte van de tabel.

Voorbeeld 2  - indexeren

Gezien onze voorbeelddatabase van r = 5,000,000 records met een indexrecordlengte van R = 54 bytes en met behulp van de standaardblokgrootte B = 1,024 bytes. De blokkerende factor van de index zou zijn bfr = (B/R) = 1024/54 = 18 records per schijfblok. Het totale aantal blokken dat nodig is om de index te houden is N = (r/bfr) = 5000000/18 = 277,778 blokken.

Nu een zoekopdracht met behulp van de Voornaam veld kan de index gebruiken om de prestaties te verbeteren. Dit zorgt voor een binaire zoekactie naar de index met een gemiddelde van log2 277778 = 18.08 = 19 toegang blokkeren. Om het adres van het daadwerkelijke record te vinden, waarvoor een verdere bloktoegang tot lezen vereist is, waardoor het totaal wordt opgehaald 19 + 1 = 20 blokkeren van toegangen, een verre schreeuw van de 1.000.000 blok toegangen die nodig zijn om een ​​te vinden Voornaam overeenkomen in de niet-geïndexeerde tabel.

Wanneer moet het worden gebruikt?

Aangezien het maken van een index extra schijfruimte vereist (277.778 extra blokken van het bovenstaande voorbeeld, een toename van ~ 28%) en dat te veel indexen problemen kunnen veroorzaken die voortvloeien uit de bestandsgroottelimieten, moet zorgvuldig worden nagedacht over het selecteren van de juiste velden om te indexeren.

Omdat indexen alleen worden gebruikt om het zoeken naar een overeenkomend veld binnen de records te versnellen, is het vanzelfsprekend dat indexeervelden die alleen voor uitvoer worden gebruikt, eenvoudigweg verspilling van schijfruimte en verwerkingstijd zouden zijn bij het uitvoeren van een invoeg- of wisbewerking en dus moet worden vermeden. Ook gegeven de aard van een binaire zoekactie, is de kardinaliteit of uniciteit van de gegevens belangrijk. Indexering op een veld met een kardinaliteit van 2 zou de gegevens in tweeën delen, terwijl een kardinaliteit van 1.000 ongeveer 1000 records zou retourneren. Met een dergelijke lage kardinaliteit wordt de effectiviteit teruggebracht tot een lineaire sortering en de query-optimizer vermijdt het gebruik van de index als de kardinaliteit minder dan 30% van het recordaantal is, waardoor de index feitelijk een verspilling van ruimte wordt.


2848
2017-08-04 10:41



De eerste keer dat ik dit las, was het erg nuttig voor mij. Dank je.

Sindsdien heb ik enig inzicht gekregen in het nadeel van het maken van indexen: als je in een tabel schrijft (UPDATE of INSERT) met één index, hebt u feitelijk twee schrijfbewerkingen in het bestandssysteem. Eén voor de tabelgegevens en een andere voor de indexgegevens (en het gebruik ervan (en - indien geclusterd - het gebruik van de tabelgegevens)). Als de tabel en index zich op dezelfde harde schijf bevinden, kost dit meer tijd. Een tabel zonder een index (een heap) zou dus snellere schrijfbewerkingen mogelijk maken. (als u twee indexen zou hebben, zou u eindigen met drie schrijfbewerkingen, enzovoort)

Als u echter twee verschillende locaties op twee verschillende harde schijven definieert voor indexgegevens en tabelgegevens, kunt u het probleem van de duurdere tijd verminderen / elimineren. Dit vereist de definitie van aanvullende bestandsgroepen met overeenkomstige bestanden op de gewenste harde schijven en de definitie van tabel / indexlocatie zoals gewenst.

Een ander probleem met indexen is hun fragmentatie in de tijd als gegevens worden ingevoegd. REORGANIZE helpt, je moet routines schrijven om het te laten doen.

In bepaalde scenario's is een heap nuttiger dan een tabel met indexen,

bijvoorbeeld: - Als u veel rivaliserende schrijfbewerkingen hebt, maar slechts één nacht buiten kantooruren leest voor rapportage.

Ook is een onderscheid tussen geclusterde en niet-geclusterde indexen nogal belangrijk.

Hielp mij:- Wat betekent Clustered en Non Clustered Index eigenlijk?


175
2018-04-30 14:31



Een index is slechts een gegevensstructuur die het zoeken naar een bepaalde kolom in een database sneller maakt. Deze structuur is meestal een b-tree of een hash-tabel, maar het kan elke andere logische structuur zijn.

Voor meer informatie, adviseer ik: Hoe werken database-indexen? En, hoe helpen indexen?


130
2018-02-20 14:40



Laten we nu zeggen dat we een query willen uitvoeren om alle details te vinden van alle werknemers met de naam 'Abc'?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

Wat zou er gebeuren zonder een index?

Databasesoftware zou letterlijk elke rij in de Employee-tabel moeten bekijken om te zien of de Employee_Name voor die rij 'Abc' is. En omdat we elke rij met de naam 'Abc' erin willen laten, kunnen we niet stoppen met kijken als we maar één rij vinden met de naam 'Abc', omdat er mogelijk andere rijen met de naam kunnen zijn Abc. Dus elke rij tot de laatste rij moet worden doorzocht - wat betekent dat duizenden rijen in dit scenario door de database moeten worden onderzocht om de rijen met de naam 'Abc' te vinden. Dit is wat a heet volledige tafelscan

Hoe een database-index prestaties kan helpen

Het hele punt van het hebben van een index is om zoekopdrachten te versnellen door het aantal records / rijen in een tabel dat moet worden onderzocht aanzienlijk te verminderen. Een index is een gegevensstructuur (meestal een B-structuur) die de waarden voor een specifieke kolom in een tabel opslaat.

Hoe werkt de B-trees-index?

De reden dat B-trees de meest populaire datastructuur voor indexen zijn, is vanwege het feit dat ze tijd efficiënt zijn - omdat opzoeken, deleties en invoegingen allemaal in logaritmische tijd kunnen worden gedaan. En een andere belangrijke reden dat B-bomen vaker worden gebruikt, is omdat de gegevens die in de B-tree zijn opgeslagen, kunnen worden gesorteerd. Het RDBMS bepaalt meestal welke gegevensstructuur daadwerkelijk voor een index wordt gebruikt. In sommige scenario's met bepaalde RDBMS's kunt u echter opgeven welke gegevensstructuur u wilt dat uw database gebruikt wanneer u de index zelf maakt.

Hoe werkt een hashtabelindex?

De reden dat hash-indexen worden gebruikt, is omdat hashtabellen uiterst efficiënt zijn als het gaat om het alleen maar opzoeken van waarden. Query's die vergelijken voor gelijkheid met een tekenreeks, kunnen dus zeer snel waarden ophalen als ze een hash-index gebruiken.

De query die we eerder hebben besproken, kan bijvoorbeeld profiteren van een hash-index die is gemaakt in de kolom Employee_Name. De manier waarop een hash-index werkt, is dat de kolomwaarde de sleutel in de hashtabel is en dat de werkelijke waarde die aan die sleutel is toegewezen, alleen maar een verwijzing naar de rijgegevens in de tabel zou zijn. Aangezien een hash-tabel in feite een associatieve array is, zou een typische entry er ongeveer zo uitzien als "Abc => 0x28939", waarbij 0x28939 een verwijzing is naar de tabelrij waarin Abc in het geheugen is opgeslagen. Het opzoeken van een waarde als "Abc" in een hash-tabelindex en het terughalen van een verwijzing naar de rij in het geheugen is uiteraard een stuk sneller dan het scannen van de tabel om alle rijen met een waarde van "Abc" in de kolom Employee_Name te vinden.

De nadelen van een hash-index

Hash-tabellen zijn geen gesorteerde gegevensstructuren en er zijn veel soorten query's waarmee hash-indexen niet eens kunnen helpen. Stel dat u bijvoorbeeld wilt weten wie alle werknemers zijn die jonger zijn dan 40 jaar. Hoe kon je dat doen met een hashtabelindex? Nou, het is niet mogelijk omdat een hash-tabel alleen goed is voor het opzoeken van belangrijke waardeparen - wat betekent dat zoekopdrachten die gelijkheid controleren

Wat zit er precies in een database-index? Dus nu weet u dat een database-index is gemaakt op een kolom in een tabel en dat de index de waarden in die specifieke kolom opslaat. Maar het is belangrijk om te begrijpen dat een database-index de waarden niet opslaat in de andere kolommen van dezelfde tabel. Als we bijvoorbeeld een index maken op de kolom Employee_Name, betekent dit dat de kolomwaarden Employee_Age en Employee_Address niet ook in de index zijn opgeslagen. Als we gewoon alle andere kolommen in de index zouden opslaan, zou het net zoiets zijn als het maken van nog een kopie van de hele tabel - die te veel ruimte in beslag zou nemen en erg inefficiënt zou zijn.

Hoe weet een database wanneer een index moet worden gebruikt? Wanneer een query als "SELECT * FROM Employee WHERE Employee_Name = 'Abc'" wordt uitgevoerd, controleert de database of er een index is in de kolom (men) die wordt opgevraagd. Ervan uitgaande dat de kolom Employee_Name een index bevat, zal de database moeten beslissen of het zinvol is om de index te gebruiken om de gezochte waarden te vinden - omdat er enkele scenario's zijn waarin het feitelijk minder efficiënt is om de database-index te gebruiken , en efficiënter om de hele tabel te scannen.

Wat kost een database-index?

Het neemt ruimte in beslag - en hoe groter je tabel, hoe groter je index. Een andere prestatiehit met indexen is het feit dat wanneer u rijen in de bijbehorende tabel toevoegt, verwijdert of bijwerkt, dezelfde bewerkingen naar uw index moeten worden uitgevoerd. Bedenk dat een index dezelfde tot op de minuut nauwkeurige gegevens moet bevatten als die in de tabelkolom (len) die de index dekt.

Als algemene regel geldt dat een index alleen in een tabel moet worden gemaakt als de gegevens in de geïndexeerde kolom regelmatig worden opgevraagd.

Zie ook

  1. Welke kolommen zijn over het algemeen goede indexen?
  2. Hoe werken database-indexen?

93
2017-08-13 18:36



Klassiek voorbeeld "Index in boeken"

Overweeg een "Boek" van 1000 pagina's, gedeeld door 100 secties, elke sectie met X-pagina's.

Eenvoudig, huh?

Nu, zonder een indexpagina, om een ​​bepaald gedeelte te vinden dat begint met de letter "S", hebt u geen andere optie dan het hele boek te scannen. dat wil zeggen: 1000 pagina's

Maar met een indexpagina aan het begin, ben je er. En meer, om een ​​bepaalde sectie te lezen die er toe doet, hoef je alleen maar keer op keer over de indexpagina te kijken. Na het vinden van de matching-index kun je efficiënt naar de sectie springen door andere secties over te slaan.

Maar dan heeft u naast 1000 pagina's nog eens ~ 10 pagina's nodig om de indexpagina weer te geven, dus totaal 1010 pagina's.

De index is dus een afzonderlijke sectie die waarden van geïndexeerde kolom + pointer naar de geïndexeerde rij opslaat in een gesorteerde volgorde voor efficiënte opzoekingen.

Dingen zijn eenvoudig in scholen, is het niet? : P


82
2018-04-23 14:43



Eenvoudige beschrijving !!!!!!!!!!

De index is niets anders dan een gegevensstructuur die de waarden voor een specifieke kolom in een tabel opslaat. Er wordt een index gemaakt op een kolom van een tabel.

Voorbeeld: we hebben een databasetabel met de naam Gebruiker met drie kolommen: naam, leeftijd en adres. Stel dat de tabel Gebruiker duizenden rijen heeft.

Laten we nu zeggen dat we een query willen uitvoeren om alle details te vinden van alle gebruikers met de naam 'John'. Als we de volgende query uitvoeren.

SELECT * FROM User 
WHERE Name = 'John'

De databasesoftware zou letterlijk elke rij in de gebruikerstabel moeten bekijken om te zien of de naam voor die rij 'John' is. Dit zal lang duren.
Dit is waar index ons helpt "index wordt gebruikt om zoekopdrachten te versnellen door het aantal records / rijen in een tabel dat moet worden onderzocht, in wezen te verminderen".
Hoe een index te maken

CREATE INDEX name_index
ON User (Name)

Een index bestaat uit kolomwaarden (bijv. John) uit één tabel en die waarden worden opgeslagen in een gegevensstructuur.
Dus nu zal de database de index gebruiken om werknemers met de naam John te vinden, omdat de index vermoedelijk alfabetisch gesorteerd wordt op de naam van de gebruiker. En omdat het is gesorteerd, betekent dit dat het zoeken naar een naam een ​​stuk sneller is omdat alle namen die beginnen met een 'J' naast elkaar in de index staan!


46
2017-08-02 01:30



Gewoon een snelle suggestie. Aangezien indexering u extra schrijf- en opslagruimte kost, dus als uw toepassing meer invoeg- / update-bewerkingen vereist, wilt u mogelijk tabellen zonder indexen gebruiken, maar als het meer gegevensherstelbewerkingen vereist, moet u voor geïndexeerd gaan tafel.


21
2018-01-14 06:44