/* * ExtendibleHash.java - Joris van Rantwijk * in2026 Inleiding databeheer * * Extendible hashing. */ import java.io.RandomAccessFile; import java.io.IOException; /* * We gebruiken aparte files voor de index (of directory) en de records. * * De index wordt opgeslagen in een indexfile. Aan het begin van de file * staat een integer die de globale diepte (d) aangeeft. Daarna volgen de * entries van de index. Per entry worden twee integers opgeslagen: een * pointer naar de bijbehorende pagina in de recordfile, en de locale * diepte van de betreffende pagina (d'). Hiervoor zijn per entry * 2 * 4 = 8 bytes nodig. * We wijken hier dus af van de beschrijving in het dictaat, waar de locale * diepte in de recordpagina wordt opgeslagen. * * De recordfile is ingedeeld in pagina's. In elke pagina is ruimte voor * een vast aantal records (bucketsize). Vrije posities binnen een pagina * worden gemarkeerd door een record met een ongeldige sleutel (-1). * * Wanneer een record moet worden toegevoegd aan een volle pagina, * wordt page splitting toegepast (zonodig meerdere keren). Soms moet * dan ook de globale diepte worden vergroot, en de index verdubbeld. * * Na het verwijderen van records is het soms mogelijk om pagina's weer * samen te voegen. We doen dit alleen als beide pagina's voor meer dan * de helft leeg zijn. Door de recombinatie komt er een pagina in de * recordfile vrij. In de vfile bewaren we een opsomming van al deze * vrije pagina's; bij het page splitten kan zo'n vrije pagina weer * in gebruik worden genomen. * Als voor alle records de locale diepte kleiner is dan de globale diepte, * is het in principe mogelijk om ook de globale diepte te verkleinen en de * index te halveren. Deze operatie is hier niet geimplementeerd, omdat * het waarschijnlijk niet vaak nodig zal zijn, en omdat het in Java erg * moeilijk is om een diskfile te verkleinen. */ //=========================================================================== // Class ExtendibleHash // Implementatie van extendible hashing //=========================================================================== public class ExtendibleHash extends BestandsOrganisatie { // De gebruikte files. private RandomAccessFile ifile; private RandomAccessFile rfile; private RandomAccessFile vfile; // De omvang van een pagina van de recordfile in bytes. private final static int PAGESIZE = 1024; // Het maximale aantal records per pagina. private int bucketsize; // Globale diepte van de index. // Deze wordt in het geheugen bewaard om het zoeken te versnellen. private int globalDepth; // Construeer een ExtendibleHash class. // Gebruik de gegeven filenaam, en het gegeven recordtype. //----------------------------------------------------------------------- public ExtendibleHash(String filenaam, Class recordType) throws IOException { this.recordType = recordType; this.recordLen = Record.newRecord(recordType).getRecordlen(); // Bereken de bucketsize (het aantal records dat in een pagina past). bucketsize = PAGESIZE / recordLen; // Open de benodigde files. Als de files nog niet bestaan, // worden er automatisch lege files aangemaakt. ifile = new RandomAccessFile(filenaam + "i", "rw"); rfile = new RandomAccessFile(filenaam + "r", "rw"); vfile = new RandomAccessFile(filenaam + "v", "rw"); // Controleer de lengte van de indexfile. if (ifile.length() == 0) { // De file bevat nog geen gegevens. Initialiseer de file // door een index met diepte 0, en een lege recordpagina // aan te maken. globalDepth = 0; // Schrijf globale diepte ifile.writeInt(globalDepth); // Schrijf eerste entry: adres = 0, d' = 0. ifile.writeInt(0); ifile.writeInt(0); diskaccess++; // Schrijf een lege pagina naar de recordfile. Record r = Record.newRecord(recordType); for (int i = 0; i < bucketsize; i++) r.write(rfile); diskaccess++; } else { // Lees alvast de globale diepte uit de indexfile. globalDepth = ifile.readInt(); } } // Sluit het bestand. //----------------------------------------------------------------------- public void close() throws IOException { // Sluit alle files. ifile.close(); rfile.close(); vfile.close(); } // Bereken de hashwaarde van de gegeven sleutel. //----------------------------------------------------------------------- private int hash(int key) { // Per hashwaarde mogen er hoogstens <bucketsize> synoniemen // optreden. Om dit te garanderen gebruiken we een lineaire // hashfunctie waarbij we de sleutelwaarde delen door <bucketsize>. return (key / bucketsize); } // Geef een getal dat bestaat uit de b meest significante bits van hv. //----------------------------------------------------------------------- private static int getBits(int hv, int b) { return (hv >>> (31 - b)); } // Splits de recordpagina met adres addr. // Eventueel kan dit leiden tot een verdubbeling van de index. //----------------------------------------------------------------------- private void splitPage(int hv, int addr, int localDepth) throws IOException { Record r[], tr; int h, addr2; int ta, tld; int i, k; // Alloceer een array van records om de huidige inhoud van de pagina // in het geheugen op te slaan. r = new Record[bucketsize]; for (i = 0; i < bucketsize; i++) r[i] = Record.newRecord(recordType); tr = Record.newRecord(recordType); // Zoek een positie in de recordfile voor de nieuwe pagina. // Doorloop eerst de vfile om een vrije positie te zoeken. addr2 = -1; vfile.seek(0); for (i = 0; i < vfile.length() / 4; i++) { addr2 = vfile.readInt(); if (addr2 != -1) break; } diskaccess++; if (addr2 != -1) { // Vrije positie gevonden. // Verwijder deze vrije positie uit de vfile. vfile.seek(i * 4); vfile.writeInt(-1); } else { // Geen vrije positie gevonden. // Voeg dan de pagina toe aan het eind van de file. addr2 = (int) ((rfile.length() + PAGESIZE - 1) / PAGESIZE); } // Lees de oude pagina in het geheugen. rfile.seek(addr * PAGESIZE); for (i = 0; i < bucketsize; i++) r[i].read(rfile); diskaccess++; // Verdeel de records over de twee pagina's. // In de oude pagina komen de records met volgende hv-bit = 0. k = 0; rfile.seek(addr * PAGESIZE); for (i = 0; i < bucketsize; i++) if ((getBits(hash(r[i].key), localDepth + 1) & 1) == 0) { r[i].write(rfile); k++; } // Vul de pagina aan met ongeldige records. while (k < bucketsize) { tr.write(rfile); k++; } diskaccess++; // In de nieuwe pagina komen de records met volgende hv-bit = 1. k = 0; rfile.seek(addr2 * PAGESIZE); for (i = 0; i < bucketsize; i++) if ((getBits(hash(r[i].key), localDepth + 1) & 1) == 1) { r[i].write(rfile); k++; } // Vul de pagina aan met ongeldige records. while (k < bucketsize) { tr.write(rfile); k++; } diskaccess++; if (localDepth >= globalDepth) { // De globale diepte is te klein. // Verhoog de globale diepte en verdubbel de index. // De index bevat 2 ^ globalDepth entries. k = 1 << globalDepth; // Loop van achter naar voren door de index en verdubbel // alle entries. for (i = k - 1; i >= 0; i--) { ifile.seek(4 + i * 8); ta = ifile.readInt(); tld = ifile.readInt(); ifile.seek(4 + 2 * i * 8); ifile.writeInt(ta); ifile.writeInt(tld); ifile.writeInt(ta); ifile.writeInt(tld); } // Verhoog de globale diepte en schrijf deze naar de ifile. globalDepth++; ifile.seek(0); ifile.writeInt(globalDepth); diskaccess++; } // Van alle indexentries die naar de oude pagina wijzen, // moet de helft naar de nieuwe pagina worden gezet. // Ook moet in alle entries de localDepth worden aangepast. // Bereken de eerste entry die naar de oude pagina wijst. h = getBits(hv, localDepth); h = h << (globalDepth - localDepth); // Er zijn 2^(globalDepth - localDepth) entries die naar de oude // pagina wijzen. Update van de eerste helft alleen de localDepth. k = 1 << (globalDepth - localDepth - 1); ifile.seek(4 + h * 8); diskaccess++; for (i = 0; i < k; i++) { ifile.writeInt(addr); ifile.writeInt(localDepth + 1); } // Laat de tweede helft van de entries naar de nieuwe pagina wijzen, // en update ook de localDepth. for (i = 0; i < k; i++) { ifile.writeInt(addr2); ifile.writeInt(localDepth + 1); } } // Probeer de pagina met index h samen te voegen met een andere pagina. //----------------------------------------------------------------------- private void tryJoinPage(int h) throws IOException { Record r[], r2[], tr; int addr, addr2, localDepth, localDepth2; int h2, fp, fp2; int i, k; /* * We noemen twee pagina's "vriendjes", wanneer ze dezelfde locale diepte * hebben, en de eerste (d' - 1) bits van de hv gelijk zijn. Dit wil zeggen * dat ze ooit door pagesplitting uit dezelfde pagina zijn ontstaan. * Niet elke pagina heeft een vriendje. * Pagina's worden alleen samengevoegd als ze vriendjes zijn, en beiden * voor meer dan de helft leeg zijn. */ // Alloceer array's van records om de inhoud van de pagina's in // op te slaan. r = new Record[bucketsize]; for (i = 0; i < bucketsize; i++) r[i] = Record.newRecord(recordType); r2 = new Record[bucketsize]; for (i = 0; i < bucketsize; i++) r2[i] = Record.newRecord(recordType); tr = Record.newRecord(recordType); // Lees het adres en de locale diepte van de pagina. ifile.seek(4 + h * 8); addr = ifile.readInt(); localDepth = ifile.readInt(); diskaccess++; // Als de locale diepte == 0, kan er niet samengevoegd worden. if (localDepth == 0) return; // Bereken de index van de eerste entry die naar deze pagina wijst. h = (h >>> (globalDepth - localDepth)) << (globalDepth - localDepth); // Bereken de index van de eerste entry die naar het vriendje wijst. h2 = h ^ (1 << (globalDepth - localDepth)); // Lees het adres en de globale diepte van het (mogelijke) vriendje. ifile.seek(4 + h2 * 8); addr2 = ifile.readInt(); localDepth2 = ifile.readInt(); diskaccess++; // Controleer of de pagina's echt bevriend zijn, dwz. of ze // dezelfde locale diepte hebben. if (localDepth != localDepth2) { // De pagina's zijn niet bevriend; we kunnen ze niet samenvoegen. return; } // Lees beide pagina's in het geheugen en tel het aantal vrije // posities. fp = 0; rfile.seek(addr * PAGESIZE); for (i = 0; i < bucketsize; i++) { r[i].read(rfile); if (r[i].key == -1) fp++; } diskaccess++; fp2 = 0; rfile.seek(addr2 * PAGESIZE); for (i = 0; i < bucketsize; i++) { r2[i].read(rfile); if (r2[i].key == -1) fp2++; } diskaccess++; // Controleer of beide pagina's voor meer dan de helft leeg zijn. if (2 * fp <= bucketsize || 2 * fp2 <= bucketsize) return; // Voeg de pagina's samen. // Schrijf de records uit beide pagina's naar de eerste pagina, // en vul de pagina aan met ongeldige records. k = 0; rfile.seek(addr * PAGESIZE); for (i = 0; i < bucketsize; i++) if (r[i].key != -1) { r[i].write(rfile); k++; } for (i = 0; i < bucketsize; i++) if (r2[i].key != -1) { r2[i].write(rfile); k++; } while (k < bucketsize) { tr.write(rfile); k++; } diskaccess++; // Schrijf ongeldige records naar de tweede pagina. rfile.seek(addr2 * PAGESIZE); for (k = 0; k < bucketsize; k++) tr.write(rfile); diskaccess++; // Neem de tweede pagina op in de lijst van vrije pagina's. // Zoek hiervoor een plekje in de vfile. vfile.seek(0); for (i = 0; i < vfile.length() / 4; i++) { k = vfile.readInt(); if (k == -1) { // Vrije plek in de vfile gevonden. // Schrijf hier straks het adres. vfile.seek(i * 4); break; } } // Schrijf het adres naar de vfile. vfile.writeInt(addr2); diskaccess++; // Update de index. Samen hadden de twee pagina's // 2^(globalDepth - localDepth + 1) entries in de index. // Deze moeten allemaal naar dezelfde pagina gaan wijzen en een // kleinere localDepth krijgen. k = 1 << (globalDepth - localDepth + 1); if (h2 < h) h = h2; ifile.seek(4 + 8 * h); diskaccess++; for (i = 0; i < k; i++) { ifile.writeInt(addr); ifile.writeInt(localDepth - 1); } } // Voeg het record r toe. //----------------------------------------------------------------------- public void insert(Record r) throws Exception, IOException { Record tr = Record.newRecord(recordType); int hv, h; int addr, localDepth; int i, k; // Bereken de hashwaarde van de sleutel. hv = hash(r.key); do { // In de index gebruiken we slechts globalDepth bits. h = getBits(hv, globalDepth); // Lees de bijbehorende index entry ifile.seek(4 + h * 8); addr = ifile.readInt(); localDepth = ifile.readInt(); diskaccess++; // Zoek in de bijbehorende recordpagina naar een vrije positie. // Controleer tegelijkertijd of het record nog niet bestaat. rfile.seek(addr * PAGESIZE); diskaccess++; k = -1; for (i = 0; i < bucketsize; i++) { // Lees een record uit de pagina. tr.read(rfile); if (tr.key == -1 && k == -1) { // Vrije positie gevonden; onthoud dit in k. k = i; } if (tr.key == r.key) { // Record met dezelfde sleutel gevonden; geef exceptie. throw new Exception("Record bestaat al"); } } if (k == -1) { // Er is geen vrije ruimte in de pagina; roep de functie // splitPage aan om de pagina te splitsen en de index // aan te passen. splitPage(hv, addr, localDepth); } // Als k == -1, probeer dan na het splitsen van de pagina // opnieuw een vrije positie voor het record te vinden. } while (k == -1); // We hebben een vrije positie in de recordpagina. // Schrijf op die plaats het nieuwe record. rfile.seek(addr * PAGESIZE + k * recordLen); r.write(rfile); diskaccess++; } // Vervang een bestaand record door r. //----------------------------------------------------------------------- public void update(Record r) throws Exception, IOException { Record tr = Record.newRecord(recordType); int hv, h; int addr, localDepth; int i, k, p; // Bereken de hashwaarde van de sleutel. hv = hash(r.key); // In de index gebruiken we slechts globalDepth bits. h = getBits(hv, globalDepth); // Lees de bijbehorende index entry ifile.seek(4 + h * 8); addr = ifile.readInt(); localDepth = ifile.readInt(); diskaccess++; // Zoek in de bijbehorende recordpagina naar het record r. rfile.seek(addr * PAGESIZE); diskaccess++; for (i = 0; i < bucketsize; i++) { // Lees een record uit de pagina. tr.read(rfile); if (tr.key == r.key) { // We hebben het oude record gevonden. // Schrijf het nieuwe record er overheen. rfile.seek(addr * PAGESIZE + i * recordLen); r.write(rfile); diskaccess++; // Klaar met de update operatie return; } } // Het record bestaat niet; geef een exceptie. throw new Exception("Record niet gevonden"); } // Zoek het record met de sleutel key. //----------------------------------------------------------------------- public Record retrieve(int key) throws IOException { Record r = Record.newRecord(recordType); int hv, h; int addr, localDepth; int i, k, p; // Bereken de hashwaarde van de sleutel. hv = hash(key); // In de index gebruiken we slechts globalDepth bits. h = getBits(hv, globalDepth); // Lees de bijbehorende index entry ifile.seek(4 + h * 8); addr = ifile.readInt(); localDepth = ifile.readInt(); diskaccess++; // Zoek in de bijbehorende recordpagina naar het record. rfile.seek(addr * PAGESIZE); diskaccess++; for (i = 0; i < bucketsize; i++) { // Lees een record uit de pagina. r.read(rfile); if (r.key == key) { // We hebben het juiste record gevonden. // Geef het record terug. return r; } } // Het record bestaat niet; geef null terug. return null; } // Verwijder het record met de sleutel <key>. //----------------------------------------------------------------------- public void delete(int key) throws Exception, IOException { Record tr = Record.newRecord(recordType); int hv, h; int addr, localDepth; int i, k, p; // Bereken de hashwaarde van de sleutel. hv = hash(key); // In de index gebruiken we slechts globalDepth bits. h = getBits(hv, globalDepth); // Lees de bijbehorende index entry ifile.seek(4 + h * 8); addr = ifile.readInt(); localDepth = ifile.readInt(); diskaccess++; // Zoek in de bijbehorende recordpagina naar het record r. rfile.seek(addr * PAGESIZE); diskaccess++; for (i = 0; i < bucketsize; i++) { // Lees een record uit de pagina. tr.read(rfile); if (tr.key == key) { // We hebben het juiste record gevonden. // Verwijder het door de sleutelwaarde ongeldig te maken. tr.key = -1; rfile.seek(addr * PAGESIZE + i * recordLen); tr.write(rfile); diskaccess++; // Probeer de pagina samen te voegen. tryJoinPage(h); // Klaar met de delete operatie. return; } } // Het record bestaat niet; geef een exceptie. throw new Exception("Record niet gevonden"); } } //=========================================================================== // End //===========================================================================