[GS] Indexfile externe tabel met Btree

[zarry]

Dus: Als ge zo nen hoop datablokken hebt en ge gaat nen indexfile zo maken via nen Btree, zitten er in die nodes dan zo indexrecords (of blokken?), en zo data pointer is zo naar een blok waar da eigenlek inzit en childpointer naar een blok waar volgend indexrecord inzit ofwa? En wat is da met de zin: ideale max # kinderen m -> de grootst mogelijke oneven integer zodat m kinderpointers en m-1 indexrecords in één inkel blok van het indexbestand zitten. Is da da ge het aantal kinderen moet nemen zoveel als er indexrecords in een blok passe? Gelieve da vrij volledeg uit te leggen alle twee want alles is zo easy bij gs maar dit hebk al 10 keer geleze en da wilt er pcies maar niet in gaan. Het heeft wsl ermee te maken dak da eerste ni goe weet maar dus: HELP merci want damn.. gs ni snappe gaat er ruimschoots over ze jieee!

[cG`]

altijd die mooie structuur en duidelijke formuleringen he zarry ^^

zitten er in die nodes dan zo indexrecords (of blokken?), en zo data pointer is zo naar een blok waar da eigenlek inzit en childpointer naar een blok waar volgend indexrecord inzit ofwa?

In die nodes zitten inderdaad indexrecords, maar ze beginnen daar ineens over "blokken" omdat er in een node 2 indexrecords kunnen zitten denk ik. Dus ze organiseren het index bestand in blokken met maximum 2 indexrecords?
Die datapointer is ne pointer naar het blok waar de record met die search key zich bevindt (ineens naar het blok in het databestand zelf).
De kinderen van een node zijn dan pointers naar een ander "blok" (deze keer in het indexbestand), en das gewoon volgens de structuur van een 2-3 Boom he: kleinere search key = linkerkind enzo..

Zo heb ik het toch begrepen, maar het kan uiteraard fout zijn

Het beste resultaat wordt bekomen als:
m de grootst mogelijk oneven integer is zodat m kinderpointers en m-1 indexrecords <sleutel, datapointer> in één enkel blok van het indexbestand passen.

Da snap'k ook nie echt...

[Nicow]

Wat is het ideale maximum aantal kinderen (m) van de knopen in de zoekboom?
Het beste resultaat wordt bekomen als:
m de grootst mogelijk oneven integer is zodat m kinderpointers en m-1 indexrecords <sleutel, datapointer> in één enkel blok van het indexbestand passen.

Wel, de operatie met de meeste kost bij externe tabels is net I/O operaties. Het inlezen en wegschrijven van blokken vereist veel meer tijd dan het verwerken van de gegevens uit de blokken in het interne geheugen. Dus deze operaties moet je zo veel mogelijk beperken als je efficiënt wil werken.
Elk blok van het indexbestand is een node in de B-boom en bevat 3 pointers naar kinderen (-1 is de null pointer). De pointers zijn dus gehele getallen die naar blokken verwijzen, geen geheugenadressen zoals we gewoon zijn dus.
Aangezien je I/O operaties wil beperken, moet je proberen zoveel mogelijk indexrecords <sleutel, datapointer> in 1 blok van het indexbestand stoppen. Zo kan er in het interne geheugen met de gegevens gerommeld worden en zodat er zo weinig mogelijk andere blokken opgevraagd moeten worden. Stel dat één blok maximaal m-1 indexrecords kan bevatten, dan zijn er m kinderen aan die node. (zie figuur 14.11 op pagina 790 in het handboek) Als je dit vergelijkt met een 2-3-Tree: je hebt bijv. 2 indexrecords in een node steken, dan moet die node 3 children hebben... anders is het geen 2-3-tree meer.

Als m oneven is, zijn de algoritmen eenvoudiger.

nja, ik vermoed dat te maken heeft met de splitfunctie. Bij een 2-3 tree (m is 3) moet een node gesplitst worden als er een node 3 items bevat. Dan moet het 'middelste item' naar de parent gebracht worden en die 2 andere items worden in een aparte node gestopt. Tis dus handig dat m = 3, want dan kan je altijd het middelste item van een overvolle node bepalen. In een overvolle node zitten er 3 items, dus er moet wel een 'middelste' zijn. Wat zou het zijn als een overvolle node 4 items heeft, m = 4? welk item in die node is dan het middelste?
Als m oneven is, dan zijn de algoritmes dus eenvoudiger...[/quote]