Programovanie

Použite súbor RandomAccessFile na vytvorenie nízkoúrovňovej databázy

Ako som hľadal JavaWorldStránka s nápadmi na tento mesiac Krok za krokom, Narazil som iba na niekoľko článkov venujúcich sa prístupu k súborom na nízkej úrovni. Aj keď nám API na vysokej úrovni, ako napríklad JDBC, poskytujú flexibilitu a výkon potrebný vo veľkých podnikových aplikáciách, mnoho menších aplikácií vyžaduje jednoduchšie a elegantnejšie riešenie.

V tomto článku postavíme rozšírenie pre RandomAccessFile trieda, ktorá nám umožňuje ukladať a načítať záznamy. Tento „záznamový súbor“ bude ekvivalentný s pretrvávajúcou hašovacou tabuľkou, ktorá umožňuje ukladanie a získavanie kľúčových objektov z úložiska súborov.

Primer na spisy a záznamy

Predtým, ako sa bezhlavo vrhneme do príkladu, začnime základným pozadím. Začneme definovaním niektorých pojmov týkajúcich sa súborov a záznamov, potom si krátko povieme niečo o triede java.io.RandomAccessFile a závislosť na platforme.

Terminológia

Nasledujúce definície sú skôr naladené na náš príklad, ako na tradičnú databázovú terminológiu.

Záznam - Zbierka súvisiacich údajov uložená v súbore. Záznam má zvyčajne viac polia, pričom každá je pomenovanou a napísanou položkou informácie.

Kľúč - Identifikátor záznamu. Kľúče sú zvyčajne jedinečné.

Súbor - Postupný zber údajov uložených v akomsi stabilnom úložisku, napríklad na pevnom disku.

Nesledujúci prístup k súborom - Umožňuje čítanie údajov z ľubovoľných umiestnení v súbore.

Ukazovateľ súboru - Číslo, ktoré obsahuje pozíciu nasledujúceho bajtu údajov, ktoré sa majú načítať zo súboru.

Zaznamenajte ukazovateľ - Ukazovateľ záznamu je ukazovateľ súboru, ktorý ukazuje na miesto, kde konkrétny záznam začína.

Register - sekundárny spôsob prístupu k záznamom v spise; to znamená, že mapuje kľúče na zaznamenávanie ukazovateľov.

Halda - Postupný súbor neusporiadaných záznamov a záznamov premennej veľkosti. Hromada vyžaduje určité externé indexovanie, aby sa dal zmysluplne získať prístup k záznamom.

Vytrvalosť - Týka sa uloženia objektu alebo záznamu na určitý čas. Táto doba je zvyčajne dlhšia ako rozpätie jedného procesu, takže objekty sú zvyčajne vytrval v súboroch alebo databázach.

Prehľad triedy java.io.RandomAccessFile

Trieda RandomAccessFile je spôsob Java poskytovania nesekvenčného prístupu k súborom. Trieda nám umožňuje preskočiť na určité miesto v súbore pomocou znaku hľadať () metóda. Po umiestnení ukazovateľa súboru je možné údaje načítať a zapisovať do súboru pomocou súboru DataInput a DataOutput rozhrania. Tieto rozhrania nám umožňujú čítať a zapisovať údaje nezávislým na platforme. Ďalšie užitočné metódy v RandomAccessFile dovoľte nám skontrolovať a nastaviť dĺžku súboru.

Úvahy závislé od platformy

Moderné databázy sa pri ukladaní spoliehajú na diskové jednotky. Údaje na diskovej jednotke sú uložené v priečinku bloky, ktoré sú distribuované naprieč koľaje a povrchy. Disk je hľadať čas a rotačné oneskorenie diktovať, ako možno najefektívnejšie ukladať a načítať údaje. Typický systém na správu databáz sa pri zefektívňovaní výkonu veľmi spolieha na atribúty disku. Bohužiaľ (alebo našťastie, v závislosti od vášho záujmu o nízkoúrovňové vstupno-výstupné operácie!), Nie sú tieto parametre pri použití vysokoúrovňového API súborov, ako napr. java.io. Vzhľadom na túto skutočnosť náš príklad ignoruje optimalizácie, ktoré by mohla poskytnúť znalosť parametrov disku.

Návrh príkladu súboru RecordFile

Teraz sme pripravení navrhnúť náš príklad. Na začiatok rozložím niektoré požiadavky a ciele týkajúce sa návrhu, vyriešim problémy so súčasným prístupom a určím nízkoúrovňový formát súboru. Pred pokračovaním v implementácii sa tiež pozrieme na hlavné operácie záznamu a ich príslušné algoritmy.

Požiadavky a ciele

Naším hlavným cieľom v tomto príklade je použiť a RandomAccessFile poskytnúť spôsob ukladania a načítania záznamových údajov. Priradíme kľúč typu String s každým záznamom ako prostriedkom na jeho jednoznačnú identifikáciu. Kľúče budú obmedzené na maximálnu dĺžku, hoci nebudú obmedzené údaje o zázname. Na účely tohto príkladu budú naše záznamy pozostávať iba z jedného poľa - blobu binárnych údajov. Kód súboru sa nebude pokúšať akýmkoľvek spôsobom interpretovať zaznamenané údaje.

Ako druhý cieľ návrhu budeme požadovať, aby počet záznamov, ktoré náš súbor podporuje, nebol v čase vytvorenia opravený. Umožníme zväčšenie a zmenšenie súboru pri vkladaní a odstraňovaní záznamov. Pretože naše indexové a záznamové údaje budú uložené v rovnakom súbore, toto obmedzenie spôsobí, že pridáme ďalšiu logiku, aby sme dynamicky zväčšili priestor indexu reorganizáciou záznamov.

Prístup k údajom v súbore je rádovo pomalší ako prístup k údajom v pamäti. To znamená, že rozhodujúcim faktorom výkonu bude počet prístupov k súborom, ktoré databáza vykoná. Budeme vyžadovať, aby naše hlavné operácie s databázou nezáviseli od počtu záznamov v súbore. Inými slovami, budú konštantného času objednávky pokiaľ ide o prístupy k súborom.

Ako poslednú požiadavku budeme predpokladať, že náš index je dostatočne malý na to, aby sa mohol načítať do pamäte. Toto uľahčí našej implementácii splnenie požiadavky, ktorá diktuje čas prístupu. Zrkadlíme index v a Hashtable, ktorá poskytuje okamžité vyhľadanie hlavičky záznamu.

Oprava kódu

Kód tohto článku obsahuje chybu, ktorá v mnohých možných prípadoch spôsobuje vrhnutie výnimky NullPointerException. V abstraktnej triede BaseRecordsFile existuje rutina s názvom insureIndexSpace (int). Tento kód je určený na presunutie existujúcich záznamov na koniec súboru, ak je potrebné oblasť indexu rozbaliť. Po obnovení kapacity „prvého“ záznamu na skutočnú veľkosť sa záznam presunie na koniec. DataStartPtr je potom nastavený tak, aby ukazoval na druhý záznam v súbore. Bohužiaľ, ak v prvom zázname bolo voľné miesto, nový údaj dataStartPtr nebude ukazovať na platný záznam, pretože bol zvýšený o prvý záznam dĺžka skôr ako jeho kapacita. Upravený zdroj Java pre BaseRecordsFile nájdete v Zdrojoch.

od Rona Walkupa

Senior softvérový inžinier

bioMerieux, Inc.

Synchronizácia a súbežný prístup k súborom

Pre jednoduchosť začneme tým, že podporujeme iba model s jedným vláknom, v ktorom je zakázané súčasné vykonávanie požiadaviek na súbor. Môžeme to dosiahnuť synchronizáciou metód verejného prístupu BaseRecordsFile a RecordsFile triedy. Upozorňujeme, že toto obmedzenie môžete zmierniť a pridať podporu pre súbežné čítanie a zápis na nekonfliktné záznamy: Budete musieť udržiavať zoznam uzamknutých záznamov a vkladať čítania a zápisy pre súbežné požiadavky.

Podrobnosti o formáte súboru

Teraz výslovne definujeme formát súboru záznamov. Súbor pozostáva z troch oblastí, z ktorých každý má svoj vlastný formát.

Oblasť hlavičiek súborov. Táto prvá oblasť obsahuje dve základné hlavičky potrebné na prístup k záznamom v našom súbore. Prvá hlavička s názvom ukazovateľ spustenia údajov, je a dlho ktorý ukazuje na začiatok záznamu. Táto hodnota nám hovorí o veľkosti oblasti indexu. Druhá hlavička s názvom počet hlavičiek záznamov, je int ktorý udáva počet záznamov v databáze. Oblasť hlavičiek začína na prvom bajte súboru a rozširuje sa na FILE_HEADERS_REGION_LENGTH bajtov. Použijeme readLong () a readInt () čítať hlavičky a writeLong () a writeInt () napísať hlavičky.

Región indexu. Každá položka v indexe pozostáva z kľúča a hlavičky záznamu. Index začína na prvom bajte za oblasťou hlavičiek súborov a siaha až do bajtu pred ukazovateľom spustenia údajov. Z týchto informácií môžeme vypočítať ukazovateľ súboru na začiatok ktoréhokoľvek z parametrov n položky v indexe. Záznamy majú pevnú dĺžku - kľúčové údaje sa začínajú na prvom bajte v položke indexu a rozširujú sa MAX_KEY_LENGTH bajtov. Zodpovedajúca hlavička záznamu pre daný kľúč nasleduje bezprostredne za kľúčom v indexe. Hlavička záznamu nám hovorí, kde sa nachádzajú údaje, koľko bajtov môže záznam obsahovať a koľko bajtov vlastne obsahuje. Položky indexu v indexe súboru nie sú v žiadnom konkrétnom poradí a nemapujú sa na poradie, v ktorom sú záznamy uložené v súbore.

Zaznamenajte oblasť údajov. Oblasť záznamových údajov sa začína na mieste označenom ukazovateľom spustenia údajov a siaha po koniec súboru. Záznamy sú v súbore umiestnené za sebou, pričom medzi záznamami nie je povolené žiadne voľné miesto. Táto časť súboru pozostáva z nespracovaných údajov bez informácií o hlavičke alebo kľúči. Súbor databázy končí na poslednom bloku posledného záznamu v súbore, takže na konci súboru nie je žiadny ďalší priestor. Súbor sa pri pridávaní a mazaní záznamov zväčšuje a zmenšuje.

Veľkosť pridelená záznamu nie vždy zodpovedá skutočnému množstvu údajov, ktoré záznam obsahuje. Záznam možno považovať za kontajner - môže byť len čiastočne plný. Platné údaje záznamu sú umiestnené na začiatku záznamu.

Podporované operácie a ich algoritmy

The RecordsFile bude podporovať tieto hlavné operácie:

  • Vložiť - pridá do súboru nový záznam

  • Čítať - Načíta záznam zo súboru

  • Aktualizovať - ​​Aktualizuje záznam

  • Vymazať - Vymaže záznam

  • Zaistiť kapacitu - narastie oblasť indexu, aby sa do nej zmestili nové záznamy

Predtým, ako prejdeme zdrojový kód, prejdime si vybrané algoritmy pre každú z týchto operácií:

Vložte. Táto operácia vloží nový záznam do súboru. Vložiť:

  1. Skontrolujte, či vložený kľúč ešte nie je v súbore
  2. Zaistite, aby bola oblasť indexu dostatočne veľká na ďalšie zadanie
  3. Nájdite v súbore dostatočne veľké voľné miesto na uloženie záznamu
  4. Zapíšte údaje záznamu do súboru
  5. Pridajte hlavičku záznamu do indexu

Čítať. Táto operácia načíta požadovaný záznam zo súboru na základe kľúča. Na získanie záznamu:

  1. Pomocou indexu namapujte daný kľúč na hlavičku záznamu
  2. Skok nadol na začiatok údajov (pomocou ukazovateľa na údaje záznamu uložené v hlavičke)
  3. Načítať údaje záznamu zo súboru

Aktualizácia. Táto operácia aktualizuje existujúci záznam o nové údaje a nahradí nové údaje starými. Kroky pre našu aktualizáciu sa líšia v závislosti od veľkosti nových záznamových údajov. Ak nové údaje zapadajú do existujúceho záznamu, sme:

  1. Zapíšte údaje záznamu do súboru a prepíšete tak predchádzajúce údaje
  2. Aktualizujte atribút, ktorý uchováva dĺžku údajov v hlavičke záznamu

V opačnom prípade, ak sú údaje pre záznam príliš veľké, vykonáme tieto kroky:

  1. Vykonajte operáciu odstránenia existujúceho záznamu
  2. Vykonajte vloženie nových údajov

Odstrániť. Táto operácia odstráni záznam zo súboru. Ak chcete záznam odstrániť, vykonáme tieto kroky:

  1. Uvoľnite miesto pridelené odstránenému záznamu buď zmenšením súboru, ak je záznam posledný v súbore, alebo pridaním jeho priestoru do susedného záznamu.

  2. Odstráňte hlavičku záznamu z indexu nahradením záznamu, ktorý sa má vymazať, posledným záznamom v indexe; to zaisťuje, že index je vždy plný a medzi položkami nie sú prázdne medzery

Zaistite kapacitu. Táto operácia zabezpečí, že oblasť indexu je dostatočne veľká na umiestnenie ďalších záznamov. V slučke posúvame záznamy spredu na koniec súboru, kým nebude dostatok miesta. Ak chcete presunúť jeden záznam, postupujte takto:

  1. Vyhľadajte hlavičku záznamu prvého záznamu v súbore; všimnite si, že toto je záznam s údajmi v hornej časti oblasti záznamových údajov - nie záznam s prvou hlavičkou v indexe

  2. Prečítajte si údaje cieľového záznamu

  3. Zväčšite súbor o veľkosť dát cieľového záznamu pomocou setLength (long) metóda v RandomAccessFile

  4. Údaje záznamu zapíšte do dolnej časti súboru

  5. Aktualizujte ukazovateľ údajov v zázname, ktorý bol presunutý

  6. Aktualizujte globálnu hlavičku, ktorá ukazuje na údaje prvého záznamu

Podrobnosti implementácie - krokovanie zdrojového kódu

Teraz sme pripravení zašpiniť si ruky a prepracovať sa napríklad v kóde. Celý zdroj si môžete stiahnuť zo zdrojov.

Poznámka: Na zostavenie zdroja musíte použiť platformu Java 2 (predtým označovanú ako JDK 1.2).

Trieda BaseRecordsFile

BaseRecordsFile je abstraktná trieda a je hlavnou implementáciou nášho príkladu. Definuje hlavné prístupové metódy a množstvo užitočných metód na manipuláciu so záznamami a položkami indexu.

$config[zx-auto] not found$config[zx-overlay] not found