GiST

Inom datorer är GiST eller Generalized Search Tree en datastruktur och API som kan användas för att bygga en mängd olika diskbaserade sökträd . GiST är en generalisering av B+-trädet , vilket ger en samtidig och återhämtningsbar infrastruktur för höjdbalanserad sökträd utan att göra några antaganden om vilken typ av data som lagras eller vilka frågor som betjänas. GiST kan användas för att enkelt implementera en rad välkända index, inklusive B+-träd , R-träd , hB-träd, RD-träd och många andra; det möjliggör också enkel utveckling av specialiserade index för nya datatyper. Det kan inte användas direkt för att implementera icke-höjdbalanserade träd som quad trees eller prefix trees (försök), även om det liksom prefix trees stöder komprimering, inklusive förlustkompression . GiST kan användas för vilken datatyp som helst som naturligt kan ordnas i en hierarki av supermängder . Det är inte bara utbyggbart när det gäller stöd för datatyp och trädlayout, det tillåter förlängningsskrivaren att stödja alla frågepredikat som de väljer.

GiST är ett exempel på programvaruutvidgning i samband med databassystem: det möjliggör enkel utveckling av ett databassystem för att stödja nya trädbaserade index. Den uppnår detta genom att faktorisera ut sin kärnsysteminfrastruktur från ett smalt API som är tillräckligt för att fånga de applikationsspecifika aspekterna av en mängd olika indexdesigner. GiST-infrastrukturkoden hanterar layouten av indexsidorna på disken, algoritmerna för att söka i index och ta bort från index, och komplexa transaktionsdetaljer som sidnivålåsning för hög samtidighet och skriv-förut-loggning för kraschåterställning . Detta gör det möjligt för författare till nya trädbaserade index att fokusera på att implementera de nya funktionerna i den nya indextypen – till exempel hur delmängder av data ska beskrivas för sökning – utan att bli experter på interna databassystem.

Även om GiST ursprungligen utformats för att svara på booleska urvalsfrågor, kan GiST också stödja sökning efter närmaste granne och olika former av statistisk approximation över stora datamängder.

Genomföranden

Den mest använda GiST-implementeringen är i relationsdatabasen PostgreSQL ; det implementerades också i Informix Universal Server, och som ett fristående bibliotek, libgist.

PostgreSQL

PostgreSQL GiST-implementeringen inkluderar stöd för nycklar med variabel längd, sammansatta nycklar, samtidighetskontroll och återställning; dessa funktioner ärvs av alla GiST-tillägg. Det finns flera bidragsmoduler utvecklade med GiST och distribuerade med PostgreSQL. Till exempel:

• rtree_gist, btree_gist - GiST-implementering av R-träd och B-träd
• intarray - indexstöd för endimensionell array av int4:s
• tsearch2 - en sökbar (fulltext) datatyp med indexerad åtkomst
• ltree - datatyper, indexerade åtkomstmetoder och frågor för data organiserade som trädliknande strukturer
• hstore - en lagring för (nyckel, värde) data
• kub - datatyp som representerar flerdimensionella kuber

PostgreSQL GiST-implementeringen tillhandahåller indexeringsstöd för PostGIS ( geografiskt informationssystem ) och BioPostgres bioinformatiksystem .

• Joseph M. Hellerstein , Jeffrey F. Naughton och Avi Pfeffer. Generaliserade sökträd för databassystem . Proc. 21st Int'l Conf. on Very Large Data Bases, Zürich, september 1995, 562–573.
• Marcel Kornacker, C. Mohan och Joseph M. Hellerstein. Samtidighet och återhämtning i generaliserade sökträd . Proc. ACM SIGMOD Conf. on Management of Data, Tucson, AZ, maj 1997, 62–72.
• Paul M. Aoki. Generalisera "Sök" i generaliserade sökträd . Proc. 14th Int'l Conf. on Data Engineering, Orlando, FL, februari 1998, 380–389.
• Marcel Kornacker. Högpresterande generaliserade sökträd , Proc. 24th Int'l Conf. på Very Large Data Bases, Edinburgh, Skottland, september 1999.
• Paul M. Aoki. Hur man undviker att bygga datablad som vet värdet av allt och kostnaden för ingenting , Proc. 11:e Int'l Conf. on Scientific and Statistical Database Management, Cleveland, OH, juli 1999, 122–133.

externa länkar

• GiST forskningsprojektets webbplats
• PostgreSQL GiST utveckling
• Dokumentation för GiST-stödet i PostgreSQL
• Utveckla PostgreSQL-tillägg med GiST (på ryska)
• GiST i PostgreSQL-wiki
• PostGIS
• BioPostgres