Databaslagringsstrukturer

Databastabeller och index kan lagras på disk i ett av ett antal former, inklusive ordnade/oordnade platta filer , ISAM , heapfiler, hash-buckets eller B+-träd . Varje form har sina egna speciella fördelar och nackdelar. De vanligaste formerna är B-träd och ISAM. Sådana former eller strukturer är en aspekt av det övergripande schemat som används av en databasmotor för att lagra information.

Obeställd

Oordnad lagring lagrar vanligtvis posterna i den ordning de infogas. Sådan lagring erbjuder bra insättningseffektivitet ( O $\displaystyle O\left(1\right)}$ ), men ineffektiva hämtningstider ( ${\displaystyle O\left(n\right)} )$ . Vanligtvis är dessa hämtningstider dock bättre, eftersom de flesta databaser använder index på primärnycklarna, vilket resulterar i hämtningstider för $O\left(\log n\right)$ eller ${ \displaystyle O\left(1\right)}$ för nycklar som är samma som databasradförskjutningarna inom lagringssystemet.

Beordrade

Beställd lagring lagrar vanligtvis posterna i ordning och kan behöva ordna om eller öka filstorleken när en ny post infogas, vilket resulterar i lägre insättningseffektivitet. Beställd lagring ger dock mer effektiv hämtning eftersom posterna är försorterade, vilket resulterar i komplexiteten $O\left(\log n\right)$ .

Strukturerade filer

Hög filer

Heap-filer är listor över oordnade poster av varierande storlek. Även om de delar ett liknande namn, skiljer sig heapfiler mycket från i minneshögar . In-memory-högar beställs, i motsats till heap-filer.

• Enklaste och mest grundläggande metoden
  • infoga effektiv, med nya poster tillagda i slutet av filen, vilket ger kronologisk ordning
  • hämtning effektiv när handtaget till minnet är adressen till minnet
  • sökning ineffektiv, eftersom sökning måste vara linjär
  • radering åstadkommes genom att markera valda poster som "raderade"
  • kräver periodisk omorganisation om filen är mycket flyktig (ändras ofta)
• Fördelar
  • effektivt för bulkladdning av data
  • effektivt för relativt små relationer eftersom indexeringskostnader undviks
  • effektivt när hämtningar omfattar en stor andel lagrade poster
• Nackdelar
  • inte effektivt för selektiv hämtning med nyckelvärden, särskilt om de är stora
  • sortering kan vara tidskrävande
  • inte lämplig för flyktiga tabeller

Hashhinkar

Huvudartikel: Hash-tabell

• Hashfunktioner beräknar adressen till sidan där posten ska lagras baserat på ett eller flera fält i posten
  • hashing-funktioner valda för att säkerställa att adresser fördelas jämnt över adressutrymmet
  • "beläggning" är i allmänhet 40% till 60% av den totala filstorleken
  • unik adress kan inte garanteras så kollisionsdetektering och kollisionsupplösningsmekanismer krävs
• Öppna adressering
• Kedjat/unkedjat bräddavlopp
• För-och nackdelar
  • effektiv för exakta matchningar på nyckelfält
  • inte lämplig för intervallhämtning, vilket kräver sekventiell lagring
  • beräknar var posten lagras baserat på fält i posten
  • hashfunktioner säkerställer jämn spridning av data
  • kollisioner är möjliga, så kollisionsdetektering och restaurering krävs

B+ träd

Huvudartikel: B+-träd

Dessa är de vanligaste i praktiken.

• Tiden det tar att komma åt en post är densamma eftersom samma antal noder söks
• Index är ett fullständigt index så datafilen behöver inte beställas
• För-och nackdelar
  • mångsidig datastruktur – sekventiell såväl som direktåtkomst
  • åtkomsten är snabb
  • stöder exakt matchning, intervall, delnyckel och mönstermatchningar effektivt.
  • flyktiga filer hanteras effektivt eftersom index är dynamiskt - expanderar och drar ihop sig när tabellen växer och krymper
  • mindre väl lämpad för relativt stabila filer – i det här fallet är ISAM mer effektivt

Dataorientering

De flesta konventionella relationsdatabaser använder "radorienterad" lagring, vilket innebär att all data som är associerad med en given rad lagras tillsammans. Däremot kolumnorienterad DBMS all data från en given kolumn tillsammans för att snabbare kunna betjäna frågor i datalagerstil . Korrelationsdatabaser liknar radbaserade databaser, men använder ett lager av indirektion för att mappa flera instanser av samma värde till samma numeriska identifierare.

Se även

• Databasindex
• ISAM