A belső szint: tárolás és adatelérés

A relációs modellben az ESZKÖZ reláció attribútumai például az eszköz_id, megnevezés, kategória és beszerzés_dátuma. A belső szinten azt vizsgáljuk, hogyan kerülnek ezek a rekordok lapokra, hogyan jutnak a memóriába, és hogyan kereshető ki gyorsan egy adott eszköz. A tárolási részleteket az adatbázis-kezelő szervezi; a tervező az indexekkel és más beállításokkal befolyásolhatja a hozzáférést.

Ugyanaz a logikai adat más fizikai szervezéssel is tárolható. Ha egy táblához új indexet hozunk létre, nem változik meg a kurzus vagy eszköz jelentése, és a lekérdezésnek továbbra is ugyanazokat a megfelelő rekordokat kell visszaadnia. Az index a keresés költségét változtatja meg. Ez a fizikai adatfüggetlenség egyik gyakorlati megnyilvánulása.

Fő példánk egy iskolai eszközkölcsönző. Az eszköz_id egyedi azonosító, a kategória viszont ismétlődhet: több laptop és több kamera van. Egyrészt konkrét eszközöket keresünk id alapján, másrészt kategóriánként vagy id-tartományban kérünk listát. Az eltérő kérdések eltérő hozzáférési módoknak kedveznek.

Az alábbi blokkok, címek, kapacitások és költségszámok szemléltető modellhez tartoznak. Nem egy konkrét adatbázis-kezelő általános beállításai. A fő elv az, hogy nemcsak az számít, hány rekordot hasonlítunk össze: az is fontos, hány adatlapot kell beolvasni a háttértárolóból.

A hagyományos HDD lemezfelületein az adatok koncentrikus sávokhoz kapcsolódnak. Az azonos sugáron lévő sávok együttese a klasszikus lemezmodellben cilinder. Egy sáv kisebb szektorokra oszlik. Az író-olvasó fej helyzetét és a lemez forgását is figyelembe kell venni, amikor egy adott területet elérünk.

A hozzáférés szemléltető lépései: a fej megfelelő sávhoz mozgatása, a megfelelő felület kiválasztása, várakozás a kívánt hely odafordulására, végül adatátvitel. Ezek közül a keresési idő és a forgási várakozás mechanikai összetevő. A közeli vagy egymást követő adatok olvasása ezért előnyös lehet a szétszórt véletlen eléréshez képest.

Az SSD flashmemóriában tárol, ezért a sáv, cilinder és fejmozgás nem az SSD működésének leírása. Ettől még az SSD-s adatbázisban sem ingyenes minden véletlen olvasás: számít az I/O műveletek száma, az átvitel mérete, a vezérlő, a párhuzamosság és a puffer találati aránya. A logikai blokkszám nem feltétlenül árulja el a tényleges fizikai elhelyezést.

A mágnesszalag egymás utáni hozzáférésre alkalmas tároló. Nagy mennyiségű archív vagy mentési adatnál lehet szerepe, de egy aktív adatbázis tetszőleges rekordjának gyors kikeresésére más hozzáférési lehetőséget kívánunk. Az adatbázis mentése és az élő adatbázis tárolási szerkezete nem azonos feladat.

A rekordok nem szükségképpen egyenként kerülnek a memóriába: a kezelő rendszerint egész lapot olvas be. Ha egy oldalon több eszközrekord van, a beolvasás után ezeket további háttértár-elérés nélkül vizsgálhatjuk. Az operációs rendszer blokkja, a meghajtó szektora és az adatbázis lapja eltérő rétegek fogalmai; méretüknek nem kell megegyeznie.

Egy lapnak a rekordokon kívül fejléc és egyéb szervezési adatok is helyet foglalnak. Változó hosszúságú rekordoknál a kapacitás sem állandó. Ha egy példában fix rekordhosszal számolunk, külön megadjuk a használható helyet, és lefelé kerekítjük az elférő rekordok számát. Nem lehet a maradék fél rekordot elhelyezni.

Puffertalálat esetén a kért lap már rendelkezésre áll a memóriában, így nincs hozzá új fizikai beolvasás. Pufferhiba, vagyis cache miss esetén a lapot be kell olvasni. A puffer mérete véges, ezért a rendszer megfelelő szabályokkal lecseréli a régebbi lapok egy részét. A gyakran használt indexgyökér például sok keresésnél memóriában maradhat.

Íráskor a memóriabeli lap módosulhat, és piszkos, módosított lappá válik. Az adatbázis-kezelő a tartósság és helyreállítás szabályai szerint írja ki az adatokat és naplóinformációkat. Nem igaz általánosan, hogy minden SQL-módosítás azonnal, közvetlenül a teljes adatlapot írja lemezre. A naplózás részletes működése külön témakör.

Heap állománynál a beszúrás általában szabad helyet keres, vagy új lapot foglal. Ha nincs megfelelő index, egy adott id-t a lapok és rekordok átvizsgálásával találunk meg. A rendezetlen nem jelent véletlenszerű értéket, adatvesztést vagy hibás adatbázist: csak azt, hogy a fizikai szervezés nem adja meg a keresési kulcs szerinti sorrendet.

Rendezett állományban a kisebb keresési kulcsértékek megelőzik a nagyobbakat. Az eszköz_id szerinti rendezés az id-keresést és id-tartomány bejárását segítheti. A kategória szerinti keresés azonban nem követi ezt a sorrendet: a laptopok több külön helyre kerülhetnek. Egyetlen fizikai rendezés nem tud minden lehetséges szempontnak egyszerre megfelelni.

A rendezett állomány beszúrása több munkával járhat. Ha két meglévő rekord közé érkezik új id, helyet kell találni a megfelelő környezetben; szükség lehet mozgatásra, lapfelosztásra vagy túlcsorduló területre. Tartalék üres hely csökkentheti az azonnali átrendezések számát, de tárolókapacitást foglal.

A rekordok logikai sorrendje nem feltétlenül azonos a meghajtó tényleges geometriai sorrendjével. A kezelő, a fájlrendszer és a meghajtó külön rétegeket kezel. SQL-eredményben sem szabad az aktuális tárolási sorrendre hagyatkozni: ha meghatározott sorrend kell, ORDER BY-t írunk.

Index nélküli heap állományban a keresett id előfordulhat bármelyik lapon. A lineáris keresés addig halad, amíg megtalálja, vagy elfogynak az adatok. Ha a kulcs egyedi, megtaláláskor megállhatunk. Ha ismétlődő kategóriát keresünk és minden találat kell, a teljes állományt is végig kell vizsgálni.

Rendezett állománynál a lapok minimuma és maximuma alapján eldönthető, hogy a keresett kulcs balra, jobbra vagy az adott lap tartományában lehet. A bináris keresés a középső lapot vizsgálja, majd a megfelelő féllel folytatja. Miután megvan a szóba jövő lap, azon belül még meg kell találni a rekordot.

A 147-es id-t négy rendezett lapban keressük. Kezdetben az alsó lapindex 1, a felső 4, a lefelé kerekített közép 2. B2-ben 118–132 az értéktartomány, tehát jobbra lépünk. Az új közép B3, tartománya 140–155; itt ellenőrizzük a rekordokat és megtaláljuk 147-et.

A 150-es id ugyanígy B3 tartományába esik, de a benne lévő 140, 147 és 155 egyikével sem egyezik. A tartományba esés csak lehetséges helyet jelent, nem sikeres találatot. Ha egy lapról jobbra vagy balra lépve az alsó határ nagyobb a felsőnél, a keresés szintén sikertelen.

A bináris keresés rendezést és a kiválasztott középső lap elérhetőségét kívánja. Egy mágnesszalag vagy általános láncolt lista esetén a középső elemre ugrás nem feltétlenül olcsó. A logaritmikus összehasonlítási szám ezért nem minden adatszerkezetben jelent logaritmikus teljes elérési időt.

Ha minden kereséskor a hosszú adatlapokat vizsgáljuk, sok háttértár-olvasásra lehet szükség. Az index bejegyzései rövidebbek lehetnek, így több fér egy lapra. A keresési értékhez először az indexben találjuk meg a megfelelő hivatkozást, majd elérjük az adatlapot vagy rekordot.

A klasszikus rendezett állomány elsődleges indexe a rendezési kulcsra épül. Ha a kulcs egyedi, és minden adatlap első értékét tesszük az indexbe, ritka indexet kapunk: nem minden rekordnak van saját bejegyzése. A rendezés teszi lehetővé, hogy az indexben meg nem jelenő 147-es kulcsot is a megfelelő laptartományhoz rendeljük.

A fő példában az index (102, B1), (118, B2), (140, B3), (162, B4) párokat tartalmaz. A 147 keresésekor az indexben a legnagyobb olyan kezdőkulcsot keressük, amely nem nagyobb 147-nél. Ez 140, tehát B3-at olvassuk. Az index itt a lapra vezet, a pontos találatot a lapon belül ellenőrizzük.

A ritka index nem használható ugyanezzel a logikával rendezetlen kategóriaértékekhez: egy B1-es laptop nem zárja ki, hogy B4-en is legyen laptop. Sűrű index esetén minden rekordhoz vagy minden keresési értékhez megfelelő, összes találatra vezető bejegyzés tartozik. Az elsődleges és másodlagos index megnevezését mindig az adott tárolási modellben értelmezzük.

A mai adatbázis-kezelőkben az index nem feltétlenül önálló, a felhasználó által kezelt fájl. A mutató sem feltétlenül nyers lemezcím: lehet lap–rekord helyazonosító vagy egy másik index kulcsa. A konkrét rendszer döntéseit ne következtessük pusztán az „elsődleges kulcs” kifejezésből.

Az eszközök id szerint rendezettek, de a kölcsönző gyakran az összes kamerát keresi. A kategória szerinti index a kategóriaértékhez rendeli a megfelelő rekordhelyeket. A kamerák lehetnek B1-en, B2-n és B4-en is: a kategóriák sorrendjéből nem következik az adatlapok sorrendje.

Ha a másodlagos keresési mező egyedi, egy értékhez egy rekord tartozik. Ez nem azt jelenti, hogy minden másodlagos index egyedi. A kategória ismétlődő érték, ezért egyetlen rekordhely eltárolása elveszítené a további találatokat.

Az ismétlődések többféleképpen kezelhetők. Tárolhatunk azonos kulcsértékkel több bejegyzést, egy kulcshoz változó hosszú helylistát, vagy külön mutatólistára hivatkozást. A konkrét szerkezet rendszerfüggő, de a lényeg ugyanaz: az összes érintett rekordnak elérhetőnek kell lennie.

Az indexben talált rekordhely után az adatokat még be kell olvasni, ha a lekérdezés olyan attribútumot kér, amely nincs benne az indexben. Sok különböző adatlap érintése költséges lehet. Ha a szűrés a tábla nagy részét visszaadja, egy teljes bejárás olcsóbb lehet, mint sok külön indexen átvezetett adatelérés.

Az egyediség és a hozzáférés két külön tulajdonság. Egy nem egyedi INDEX gyorsíthat, de nem tiltja az ismétlődést. A UNIQUE korlátozás és megfelelő egyedi index az üzleti szabály védelmét is szolgálhatja. Ne tegyük a kategóriát egyedivé csak azért, hogy könnyebb legyen lerajzolni az indexet.

Ha a kölcsönző szinte mindig kategóriánként listáz, a kamerák, laptopok és tabletek csoportos tárolása hasznos lehet. Az azonos kategóriájú eszközök így kevesebb különálló lapot érintenek. A kategória nem egyedi; az eszköz_id ettől továbbra is egyedi azonosító marad.

Egy csoport több lapot is elfoglalhat. A kezdőmutató után addig követjük a rendezett csoport lapjait vagy rekordjait, amíg a kategória meg nem változik. A csoport első lapjának címével nem feltétlenül kaptuk meg az összes találatot.

A csoportos tárolás ára, hogy más keresések vagy beszúrások eltérő költségűek lehetnek. Ugyanaz a rekordhalmaz nem tud egyszerre több különböző teljes fizikai sorrendben állni. Más szempontokhoz további hozzáférési szerkezetek készülhetnek.

A „clustered index” szóhasználata adatbázis-kezelőnként eltérhet. InnoDB-ben a sorok a clustered index levélszintjén tárolódnak, és ennek kulcsa rendszerint az elsődleges kulcs. Ez nem automatikusan a klasszikus, nem egyedi kategória szerinti csoportosító index. A fogalmat mindig a konkrét tárolási rendszer leírásával együtt értelmezzük.

Ha egy index már sok lapból áll, annak keresését újabb, kisebb indexszint gyorsíthatja. A többszintű szerkezet tetején egy gyökérlap áll, alatta további belső lapok, végül levéllapok. Nagy elágazási szám mellett kevés szint is sok rekordhoz vezet.

A B+ fa levelei azonos mélységben találhatók. Ezért nem fordul elő, hogy egy szerencsétlenül kialakult hosszú lánc miatt egyes kulcsokhoz sokkal több szintet kell bejárni. Egy belső csomópont több gyermekre vezethet; nem szabad összekeverni a bináris keresőfával, amelynek csomópontjai legfeljebb két gyermekkel rendelkeznek.

A szemléltető gyökér 118, 140 és 162 elválasztó értékeket tárol. A hozzá tartozó négy tartomány: K < 118; 118 ≤ K < 140; 140 ≤ K < 162; 162 ≤ K. A 147 a harmadik levélbe kerül. Az elválasztóérték-egyezés ebben a jelölésben a jobb oldali tartományt választja; a szabályt az ábrával összhangban kell használni.

A levél bejegyzése további adatrekordhoz vezethet, vagy egyes tárolási rendszerekben maga a levél tartalmazza a teljes sort. Külön levélindex és adatlap esetén a gyökér–levél bejárás után további adatlap-olvasás szükséges lehet. Ha a gyökér a pufferben van, nem kell azt minden alkalommal újra háttértárból olvasni.

Tartománykereséskor megkeressük az alsó határ megfelelő levelét, majd a rendezett levélláncon haladunk, amíg a felső határt el nem érjük. A 125–162 közötti, zárt intervallum találatai: 125, 132, 140, 147, 155 és 162. A hashvödör beosztásából ez a sorrendi szomszédság nem következik.

Beszúráskor egy tele levél felosztható, az új elválasztóérték a szülőbe kerül. Ha a szülő is megtelik, a változás felfelé terjedhet. A gyökér felosztása növelheti a magasságot. A cél nem a teljes állomány újrarendezése minden beszúráskor, hanem a kiegyensúlyozott, lapokhoz illeszkedő szerkezet fenntartása.

A hashing az indexben történő sorrendi keresés helyett a kulcsból számít egy elérési útvonalat. A szemléltető egész kulcsú függvény h(K) = K mod 7, ahol a vödrök száma 7, az eredmény 0 és 6 közé esik. A függvény egy vödör azonosítóját adja, nem egy általánosan közvetlenül használható, végleges lemezcímet.

A 103, 110 és 117 kulcsok mind 5 maradékot adnak. Ez szabályos ütközés: a három eszköz különböző, csak a kiválasztott vödör azonos. A rekord megkereséséhez az eredeti kulcsot is ellenőrizni kell. A hashérték egyezése nem bizonyítja, hogy két rekord ugyanahhoz az eszközhöz tartozik.

Jó eloszlásnál a vödrök nem telítődnek néhány helyen, miközben a többi szinte üres. A függvény választását a kulcsok tényleges eloszlásával együtt értékeljük. A prímszám modulus bizonyos mintázatoknál hasznos lehet, de nem garantál ütközésmentességet vagy tökéletes egyenletességet.

A hashalapú hozzáférés pontos egyenlőségi kereséshez kedvező lehet. A 117-es id-hez gyorsan kiválasztjuk az 5-ös vödröt. A 100–150 közötti id-tartományhoz azonban nem kapunk egyetlen szomszédos vödörsorozatot: a numerikus sorrend nem őrződik meg. Ezért más adatszerkezet jobb lehet tartományokhoz.

Az adatbázisbeli hash-hozzáférés nem azonos a jelszavak biztonságos hash-elésével, és nem adatazonosításra használt kriptográfiai ujjlenyomat. Itt a rekordok tárolási helyének kiválasztása a cél; a biztonsági jelszókezelés egészen más követelményekkel működik.

Egy vödör több rekordot is tárolhat, de kapacitása véges. Ha megtelik, túlcsorduló lapot kapcsolhatunk hozzá, és a keresés a láncot is bejárja. Ha a lánc hosszú lesz, több háttértár-elérés szükséges: a hashing nem biztosít minden körülmények között egyetlen olvasást.

Az ütközésre nem megoldás, hogy az új rekorddal felülírjuk a régit. A 103, 110 és 117 külön adatrekord; mindegyiket meg kell őrizni. Kereséskor a teljes megfelelő vödör- és túlcsordulási lánc alapján mondhatjuk ki, hogy egy kulcs nincs jelen.

Dinamikus módszernél a hashérték egyes bitjei alapján további vödröket különítünk el. Egy címtár több bejegyzése is mutathat ugyanarra a vödörre. Ha egy vödröt felosztunk, újabb bit segít a rekordokat két részre osztani. Nem szükséges minden egyes túlcsorduláskor minden tárolt rekordot új helyre tenni.

Egy egyszerű bővíthető példában a vödrök kapacitása 2. Kezdetben az utolsó egy bit alapján választunk: a páros 2 és 4 az even vödörbe, a páratlan 3 és 7 az odd vödörbe kerül. Az 5 beszúrása túlcsordítaná az odd vödröt. Két bitet vizsgálva 5 vége 01, a 3 és 7 vége 11: szétválaszthatjuk őket.

Az új címtár 00, 01, 10 és 11 bejegyzést tartalmaz. A 00 és 10 még ugyanarra a páros vödörre mutat, mert azt nem bontottuk. A 01 az 5-öt, a 11 a 3-at és 7-et tartalmazó vödörre vezet. A példában két alacsony helyiértékű bitet használunk; más módszerek más bitválasztást és bővítési szabályt alkalmazhatnak.

Pontos id-kereséshez rendezett index vagy megfelelő hash-hozzáférés lehet hasznos. Az id-k közötti tartományokhoz rendezett faindex alkalmasabb. A kategória szerinti összes találathoz másodlagos index segíthet, különösen akkor, ha kevés rekord érintett. Ha a lekérdezés a tábla majdnem minden sorát kéri, a teljes bejárás is jó választás lehet.

Minden index helyet foglal. Beszúrás, törlés és indexelt mező módosítása esetén karban kell tartani. Ha a kategóriát kamera értékről laptopra változtatjuk, a régi kategóriabejegyzést módosítani kell, és az új értékhez is elérhetővé kell tenni a rekordot. Az állomány és az index összhangjának megőrzése a kezelő feladata.

Az összetett indexek külön tervezést kívánnak. A (kategória, eszköz_id) sorrendű faindex a kategórián belüli id-ket rendezi. Ez nem ugyanaz, mint az (eszköz_id, kategória) index. Az oszlopok sorrendjét a keresési feltételekhez és a rendezési igényekhez igazítjuk; egyetlen kétoszlopos index nem válik automatikusan két független indexszé.

Az index használatáról rendszerint a lekérdezésoptimalizáló dönt. A döntésnél szerepet kaphat a találatok becsült száma, a tábla mérete, a puffer, a tároló és az index szerkezete. Az, hogy egy index létezik, nem jelenti, hogy minden érintett lekérdezésnél használni fogják. A tényleges végrehajtási terv és mért futás hasznosabb, mint a feltételezés.

Az indexek szerkezetétől függetlenül az eredmény helyességét meg kell őrizni. Index nélkül és indexszel ugyanarra az adatállapotra ugyanazok a feltételt teljesítő rekordok járnak; a teljesítmény változik. Az eredmény sorrendje külön előírás hiányában nem garantált.