Programmering

Brug en RandomAccessFile til at oprette en database på lavt niveau

Da jeg søgte JavaWorldwebsted for ideer til denne måneds Trin for trin, Stødte jeg kun på et par artikler, der dækkede filadgang på lavt niveau. Selvom API'er på højt niveau som JDBC giver os den nødvendige fleksibilitet og styrke i store virksomhedsapplikationer, kræver mange mindre applikationer en mere enkel og elegant løsning.

I denne artikel bygger vi en udvidelse til RandomAccessFile klasse, der giver os mulighed for at gemme og hente poster. Denne "arkivfil" svarer til en vedvarende hashtable, så nøgleobjekter kan gemmes og hentes fra fillagring.

En primer på filer og optegnelser

Før vi springer hovedet ind i eksemplet, lad os starte med en grundlæggende baggrund. Vi begynder med at definere nogle udtryk, der vedrører filer og optegnelser, så diskuterer vi kort klassen java.io.RandomAccessFile og platformafhængighed.

Terminologi

Følgende definitioner er indstillet på vores eksempel snarere end til traditionel databaseterminologi.

Optage - En samling af relaterede data gemt i en fil. En post har typisk flere felter, hver er et navngivet og indtastet informationselement.

Nøgle - En identifikator for en post. Nøgler er normalt unikke.

Fil - En sekventiel samling af data, der er gemt i en eller anden form for stabil lagring såsom en harddisk.

Ikke-efterfølgende filadgang - Tillader, at data læses fra vilkårlige placeringer i filen.

Filmarkør - Et tal, der holder positionen for den næste byte af data, der skal læses fra en fil.

Optag markør - En postmarkør er en filmarkør, der peger på det sted, hvor en bestemt post begynder.

Indeks - Et sekundært middel til at få adgang til poster i en fil; det vil sige, det kortlægger tasterne til at optage markører.

Bunke - En sekventiel fil med ikke-ordnet og variabel størrelse poster. En bunke kræver nogle eksterne indekseringer for at få meningsfuld adgang til posterne.

Udholdenhed - Henviser til opbevaring af et objekt eller en registrering i en bestemt periode. Denne tid er typisk længere end en proces, så objekter er normalt vedvarende i filer eller databaser.

Oversigt over klasse java.io.RandomAccessFile

Klasse RandomAccessFile er Java's måde at give ikke-efterfølgende adgang til filer på. Klassen giver os mulighed for at springe til et bestemt sted i filen ved hjælp af søge() metode. Når filmarkøren er placeret, kan data læses fra og skrives til filen ved hjælp af Datainput og Dataoutput grænseflader. Disse grænseflader giver os mulighed for at læse og skrive data på en platformuafhængig måde. Andre nyttige metoder i RandomAccessFile tillad os at kontrollere og indstille længden af ​​filen.

Platformafhængige overvejelser

Moderne databaser er afhængige af diskdrev til lagring. Data på et diskdrev er gemt i blokke, som er fordelt på tværs spor og overflader. Disken er søge tid og rotationsforsinkelse diktere, hvordan data mest effektivt kan lagres og hentes. Et typisk databasestyringssystem er meget afhængigt af diskens attributter for at strømline ydelsen. Desværre (eller heldigvis, afhængigt af din interesse for lavt niveau I / O!), Ligger disse parametre langt fra rækkevidde, når du bruger et højniveaufil-API såsom java.io. I betragtning af denne kendsgerning vil vores eksempel se bort fra de optimeringer, som viden om diskens parametre kunne give.

Design af RecordsFile-eksemplet

Nu er vi klar til at designe vores eksempel. For at starte, lægger jeg nogle designkrav og mål, løser problemer med samtidig adgang og specificerer filformatet på lavt niveau. Før vi fortsætter med implementeringen, vil vi også se på de vigtigste postoperationer og deres tilsvarende algoritmer.

Krav og mål

Vores hovedmål i dette eksempel er at bruge en RandomAccessFile at give en måde til lagring og hentning af postdata. Vi forbinder en nøgle af typen Snor med hver post som et middel til entydigt at identificere den. Tasterne begrænses til en maksimal længde, skønt registreringsdataene ikke er begrænsede. Med henblik på dette eksempel vil vores optegnelser kun bestå af et felt - en "klat" af binære data. Filkoden forsøger ikke på nogen måde at fortolke postdataene.

Som et andet designmål kræver vi, at antallet af poster, som vores fil understøtter, ikke rettes ved oprettelsestidspunktet. Vi tillader filen at vokse og krympe, når poster indsættes og fjernes. Da vores indeks- og registreringsdata gemmes i den samme fil, får denne begrænsning os til at tilføje ekstra logik for dynamisk at øge indekspladsen ved at omorganisere poster.

Adgang til data i en fil er størrelsesordener langsommere end adgang til data i hukommelsen. Dette betyder, at antallet af filadgang, som databasen udfører, vil være den afgørende præstationsfaktor. Vi kræver, at vores vigtigste databaseoperationer ikke afhænger af antallet af poster i filen. Med andre ord vil de være konstant bestillingstid med hensyn til filadgang.

Som et sidste krav antager vi, at vores indeks er lille nok til at indlæses i hukommelsen. Dette vil gøre det lettere for vores implementering at opfylde kravet, der dikterer adgangstid. Vi spejler indekset i en Hashtable, som giver øjeblikkelig post-header-opslag.

Kodekorrektion

Koden til denne artikel har en fejl, der får den til at kaste en NullPointerException i mange mulige tilfælde. Der er en rutine med navnet insureIndexSpace (int) i den abstrakte klasse BaseRecordsFile. Koden er beregnet til at flytte eksisterende poster til slutningen af ​​filen, hvis indeksområdet skal udvides. Efter at den "første" plades kapacitet er nulstillet til dens faktiske størrelse, flyttes den til slutningen. DataStartPtr indstilles derefter til at pege på den anden post i filen. Desværre, hvis der var ledig plads i den første post, vil den nye dataStartPtr ikke pege på en gyldig post, da den blev forøget med den første records længde snarere end dens kapacitet. Den modificerede Java-kilde til BaseRecordsFile kan findes i Resources.

fra Ron Walkup

Senior softwareingeniør

bioMerieux, Inc.

Synkronisering og samtidig filadgang

For nemheds skyld starter vi med kun at understøtte en enkelt trådmodel, hvor filanmodninger ikke er tilladt at ske samtidigt. Vi kan opnå dette ved at synkronisere de offentlige adgangsmetoder til BaseRecordsFile og RecordsFile klasser. Bemærk, at du kan slappe af af denne begrænsning for at tilføje understøttelse af samtidige læsninger og skrivninger på ikke-modstridende poster: Du bliver nødt til at opretholde en liste over låste poster og sammenflette læsninger og skriv til samtidige anmodninger.

Detaljer om filformatet

Vi vil nu eksplicit definere formatet på records-filen. Filen består af tre regioner, hver med sit eget format.

Regionen med filoverskrifter. Denne første region indeholder de to vigtige overskrifter, der er nødvendige for at få adgang til poster i vores fil. Den første header, kaldet data startmarkør, er en lang der peger på starten af ​​postdataene. Denne værdi fortæller os størrelsen på indeksområdet. Den anden header, kaldet num poster header, er en int der giver antallet af poster i databasen. Overskriftsregionen starter den første byte i filen og strækker sig til FILE_HEADERS_REGION_LENGTH bytes. Vi bruger readLong () og readInt () at læse overskrifterne, og skrivLang () og skrivInt () at skrive overskrifterne.

Indeksregionen. Hver post i indekset består af en nøgle og en postoverskrift. Indekset starter på den første byte efter filoverskriftsregionen og strækker sig indtil byten før data startmarkøren. Fra disse oplysninger kan vi beregne en filmarkør til starten af ​​en af n poster i indekset. Indgange har en fast længde - nøgledataene starter ved den første byte i indeksindgangen og udvides MAX_KEY_LENGTH bytes. Den tilsvarende postoverskrift for en given nøgle følger umiddelbart efter nøglen i indekset. Recordoverskriften fortæller os, hvor dataene er placeret, hvor mange bytes posten kan rumme, og hvor mange bytes den faktisk har. Indeksindgange i filindekset er ikke i nogen bestemt rækkefølge og kortlægges ikke til den rækkefølge, som posterne er gemt i filen.

Registrer dataregion. Registreringsdataregionen starter på det sted, der er angivet med datastartmarkøren og strækker sig til slutningen af ​​filen. Records placeres back-to-back i filen uden fri plads tilladt mellem poster. Denne del af filen består af rådata uden overskrift eller nøgleinformation. Databasefilen slutter på den sidste blok i den sidste post i filen, så der er ikke ekstra plads i slutningen af ​​filen. Filen vokser og krymper, når poster tilføjes og slettes.

Den størrelse, der er allokeret til en post, svarer ikke altid til den faktiske mængde data, som posten indeholder. Posten kan betragtes som en container - den er muligvis kun delvist fuld. Gyldige postdata er placeret i starten af ​​posten.

Understøttede operationer og deres algoritmer

Det RecordsFile vil understøtte følgende hovedoperationer:

  • Indsæt - Tilføjer en ny post til filen

  • Læs - Læser en post fra filen

  • Opdatering - Opdaterer en post

  • Slet - Sletter en post

  • Sikre kapacitet - Vokser indeksområdet til at rumme nye poster

Før vi går igennem kildekoden, lad os gå gennem de valgte algoritmer for hver af disse operationer:

Indsæt. Denne handling indsætter en ny post i filen. For at indsætte, vi:

  1. Sørg for, at nøglen, der indsættes, ikke allerede er indeholdt i filen
  2. Sørg for, at indeksområdet er stort nok til den ekstra post
  3. Find ledig plads i filen, der er stor nok til at holde rekorden
  4. Skriv postdataene til filen
  5. Føj posthovedet til indekset

Læs. Denne handling henter en anmodet post fra filen baseret på en nøgle. For at hente en post skal vi:

  1. Brug indekset til at kortlægge den givne nøgle til postens overskrift
  2. Se ned til starten af ​​dataene (brug markøren til de optagedata, der er gemt i overskriften)
  3. Læs postens data fra filen

Opdatering. Denne handling opdaterer en eksisterende post med nye data, der erstatter de nye data med de gamle. Trinene til vores opdatering varierer afhængigt af størrelsen på de nye postdata. Hvis de nye data passer ind i den eksisterende post, skal vi:

  1. Skriv postdataene til filen og overskriv de tidligere data
  2. Opdater attributten, der indeholder længden af ​​dataene i postens overskrift

Ellers, hvis dataene er for store til posten, skal vi:

  1. Udfør en sletning på den eksisterende post
  2. Udfør en indsættelse af de nye data

Slet. Denne handling fjerner en post fra filen. For at slette en post skal vi:

  1. Genvinde den plads, der er tildelt til posten, der fjernes, ved enten at formindske filen, hvis posten er den sidste i filen, eller ved at føje dens plads til en tilstødende post

  2. Fjern postens overskrift fra indekset ved at erstatte den post, der slettes, med den sidste post i indekset; dette sikrer, at indekset altid er fuldt uden tomme mellemrum mellem poster

Sikre kapacitet. Denne handling sikrer, at indeksområdet er stort nok til at rumme yderligere poster. I en sløjfe flytter vi poster fra forsiden til slutningen af ​​filen, indtil der er tilstrækkelig plads. For at flytte en post vi:

  1. Find posthovedet til den første post i filen; bemærk, at dette er posten med data øverst i postdataområdet - ikke posten med den første overskrift i indekset

  2. Læs data fra målregistreringen

  3. Dyrk filen efter størrelsen på målpostens data ved hjælp af setLength (lang) metode i RandomAccessFile

  4. Skriv postdataene i bunden af ​​filen

  5. Opdater datapekeren i den post, der blev flyttet

  6. Opdater den globale header, der peger på den første records data

Implementeringsdetaljer - trin gennem kildekoden

Vi er nu klar til at gøre vores hænder beskidte og arbejde igennem koden til eksemplet. Du kan downloade den komplette kilde fra Resources.

Bemærk: Du skal bruge Java 2-platformen (tidligere kendt som JDK 1.2) for at kompilere kilden.

Klasse BaseRecordsFile

BaseRecordsFile er en abstrakt klasse og er den vigtigste implementering af vores eksempel. Det definerer de vigtigste adgangsmetoder samt en række hjælpemetoder til manipulation af poster og indeksindgange.