Fraktalträdindex

Fraktalträdindex
Typ	träd
Uppfunnet	2007
Uppfunnet av	Michael A. Bender , Martin Farach-Colton , Bradley C. Kuszmaul
Tidskomplexitet i stor O-notation
Algoritm Genomsnitt Värsta fall Plats O( N / B ) O( N / B ) Sök O(log B N ) O(log B N ) Föra in O(log B N / B ε ) O(log B N / B ε ) Radera O(log B N / B ε ) O(log B N / B ε )

Inom datavetenskap är ett fraktalt trädindex en träddatastruktur som håller data sorterad och tillåter sökningar och sekventiell åtkomst samtidigt som ett B-träd men med insättningar och raderingar som är asymptotiskt snabbare än ett B-träd. Liksom ett B-träd är ett fraktalt trädindex en generalisering av ett binärt sökträd genom att en nod kan ha fler än två barn. Dessutom, till skillnad från ett B-träd, har ett fraktalt trädindex buffertar vid varje nod, som gör att infogningar, raderingar och andra ändringar kan lagras på mellanliggande platser. Målet med buffertarna är att schemalägga diskskrivningar så att varje skrivning utför en stor mängd användbart arbete, och därigenom undviker prestanda i värsta fall av B-träd, där varje diskskrivning kan ändra en liten mängd data på disken. Precis som ett B-träd är fraktalträdindex optimerade för system som läser och skriver stora datablock. Fraktalträdsindexet har kommersialiserats i databaser av Tokutek . Ursprungligen implementerades det som en cache-omedveten lookahead-array, men den nuvarande implementeringen är en förlängning av B ^ε -trädet. B ^ε är relaterad till det buffrade förvarsträdet. Det buffrade förvarsträdet har grad 2, medan B ^ε -trädet har grad B ^ε . Fraktalträdsindexet har också använts i ett prototypfilsystem . En öppen källkodimplementering av fraktalträdsindexet är tillgänglig, som visar implementeringsdetaljerna som beskrivs nedan.

Översikt

I fraktala trädindex kan interna ( icke-bladiga ) noder ha ett variabelt antal barnnoder inom något fördefinierat intervall. När data infogas eller tas bort från en nod ändras dess antal undernoder. För att bibehålla det fördefinierade området kan interna noder sammanfogas eller delas. Varje intern nod i ett B-träd kommer att innehålla ett antal nycklar som är en mindre än dess förgreningsfaktor . Nycklarna fungerar som separationsvärden som delar upp dess underträd . Nycklar i underträd lagras i sökträdordning , det vill säga alla nycklar i ett underträd är mellan de två parentesvärdena. I detta avseende är de precis som B-träd.

Fraktalträdindex och B-träd utnyttjar båda det faktum att när en nod hämtas från lagringen, hämtas ett minnesblock, vars storlek betecknas med $B$ . Således är noder avstämda att ha storlek ungefär $B$ . Eftersom åtkomst till lagring kan dominera löptiden för en datastruktur, domineras tidskomplexiteten hos externa minnesalgoritmer av antalet läs/skrivningar en datastruktur inducerar. (Se t.ex. för följande analyser.)

I ett B-träd betyder detta att antalet nycklar i en nod är inriktat på att vara tillräckligt för att fylla noden, med viss variation för noddelningar och sammanslagningar. För teoretisk analys, om ${\displaystyle O(B)}-$ tangenter passar i en nod, så har trädet djupet $O(\log _{B}N )$ , och detta är I/O-komplexiteten för både sökningar och infogningar.

Fraktalträdsnoder använder en mindre förgreningsfaktor, säg, av ${\sqrt {B}}$ . Trädets djup är då $O(\log _{\sqrt {B}}N)=O(\log _{B}N)$ , och matchar därmed B-trädet asymptotiskt. Det återstående utrymmet i varje nod används för att buffra infogningar, radering och uppdateringar, som vi sammantaget kallar meddelanden. När en buffert är full spolas den till barnen i bulk. Det finns flera val för hur buffertarna spolas, vilket alla leder till liknande I/O-komplexitet. Varje meddelande i en nodbuffert kommer att spolas till ett visst barn, vilket bestäms av dess nyckel. Antag, för att vara konkret, att meddelanden töms som är på väg till samma barn, och att vi bland ${\sqrt {B}}+1$ väljer det som har flest meddelanden. Sedan finns det minst ${\frac {B}{{\sqrt {B}}}+1}}\approx {\sqrt {B}}$ meddelanden som kan spolas till barnet . Varje spolning kräver $O(1)$ spolningar, och därför är kostnaden per meddelande för en spolning $O\left({\frac {1}{\sqrt { B}}}\right)$ .

Tänk på kostnaden för en insättning. Varje meddelande rensas $O(\log _{B}N)$ gånger, och kostnaden för en spolning är $O\left({\frac { 1}{\sqrt {B}}}\right)$ . Därför är kostnaden för en infogning $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ . Observera slutligen att förgreningsfaktorn kan variera, men för vilken förgreningsfaktor ${\displaystyle B^{\varepsilon }} som helst$ , är kostnaden för en spolning ${\displaystyle O\left({ \frac {1}{B^{1-\varepsilon }}}\right)} ,$ vilket ger en jämn avvägning mellan sökkostnad, som beror på sökträdets djup, och därför förgreningsfaktorn, kontra insättningstiden , vilket beror på trädets djup men mer känsligt på storleken på buffertspolningarna.

Jämförelser med andra externa minnesindex

Det här avsnittet jämför fraktalträdindex med andra externa minnesindexeringsdatastrukturer. Den teoretiska litteraturen om detta ämne är mycket stor, så denna diskussion är begränsad till en jämförelse med populära datastrukturer som används i databaser och filsystem.

B-träd

Söktiden för ett B-träd är asymptotiskt densamma som för ett fraktalt trädindex. Men ett fraktalt trädindex har djupare träd än ett B-träd, och om varje nod skulle kräva en I/O, säg om cachen är kall, då skulle ett fraktalt trädindex inducera mer IO. Men för många arbetsbelastningar är de flesta eller alla interna noder i både B-träd och fraktala trädindex redan cachade i RAM. I det här fallet domineras kostnaden för en sökning av kostnaden för att hämta lövet, som är densamma i båda fallen. Således, för många arbetsbelastningar, kan fraktalträdindex matcha B-träd när det gäller söktid.

Där de skiljer sig är på infogningar, borttagningar och uppdateringar. En infogning i ett fraktalt trädindex tar $O\left({\frac {\log _{B}N}{\sqrt {B}}}\right)$ medan B- träd kräver $O(\log _{B}N)$ . Således är fraktalträdindex snabbare än B-träd med faktorn $O({\sqrt {B}})$ . Eftersom $B$ kan vara ganska stor, ger detta en potentiell förbättring av två storleksordningar i värsta fall insättningstider, vilket observeras i praktiken. Både B-träd och fraktala trädindex kan utföra insättningar snabbare i bästa fall. Till exempel, om nycklar infogas i sekventiell ordning, uppnår båda datastrukturerna en $O\left({\frac {1}{B}}\right)$ I/O per infogning. Eftersom de bästa och sämsta fallen av B-träd skiljer sig så mycket åt, medan fraktalträdindex alltid är nära sitt bästa fall, beror den faktiska hastigheten som fraktalträdindex uppnår jämfört med B-träd på detaljerna i arbetsbelastningen.

Loggstrukturerade sammanslagningsträd

Log-structured merge-tree (LSM) hänvisar till en klass av datastrukturer som består av två eller flera indexstrukturer med exponentiellt växande kapacitet. När ett träd på någon nivå når sin kapacitet slås det samman till nästa större nivå. IO-komplexiteten för en LSM beror på parametrar som tillväxtfaktorn mellan nivåer och datastrukturen som väljs på varje nivå, så för att analysera komplexiteten hos LSM måste vi välja en specifik version. För jämförelsesyften väljer vi versionen av LSM:er som matchar fraktalträdindex för insättningsprestanda.

Antag att en LSM implementeras via $O(\log _{B}N)$ B-träd, som var och en har en kapacitet som är ${\sqrt {B}}$ större än sin föregångare. Sammanfogningstiden beror på tre fakta: Den sorterade ordningen av nycklar i ett $N$ -objekt B-träd kan produceras i $O\left({\frac {N}{B }}\right)$ IOs; Två sorterade listor med $N$ och $M$ objekt kan slås samman till en sorterad lista i $O\left({\frac {N+M}{B }}\right)$ IOs; och ett B-träd av en sorterad lista med $N$ objekt kan byggas in i $O\left({\frac {N}{B}}\right)$ IOs. När ett träd svämmar över slås det samman till ett träd vars storlek är $O({\sqrt {B}})$ större, därför kräver en nivå som innehåller $k$ objekt $O\left({\frac {k}{\sqrt {B}}}\right)$ IO:er för att slå samman. Ett objekt kan slås samman en gång per nivå, vilket ger en total tid på $O\left({\frac {\log _{B}N}{\sqrt {B}}}\ höger)$ , som matchar fraktalträdets index.

Frågetiden är helt enkelt B-trädets frågetid på varje nivå. Frågetiden till ${\displaystyle i}:$ ^e nivån är $O(\log _{B}B^{\frac {i}{2} })=O(i)$ , eftersom ${\displaystyle i}:$ ^e nivån har kapacitet $B^{\frac {i}{2}}$ . Den totala tiden är därför $O(\log _{B}^{2}N)$ ​​. Detta är större än både B-trädet och fraktalträdets index med en logaritmisk faktor. Faktum är att även om B-träd och fraktala trädindex båda är på den optimala avvägningskurvan mellan infogningar och frågor, är LSM inte det. De är ojämförliga med B-träd och domineras av fraktala trädindex.

Några anteckningar om LSM:er: det finns sätt att göra frågorna snabbare. Till exempel, om endast medlemskapsfrågor krävs och inga efterföljare/föregångare/intervallfrågor krävs, Bloom-filter användas för att snabba upp frågorna. Tillväxtfaktorn mellan nivåerna kan också ställas in på något annat värde, vilket ger en rad avvägningar mellan infogning/fråga. Men för varje val av insättningshastighet har motsvarande fraktalträdsindex snabbare frågor.

B ^ε träd

Fraktalträdets index är en förfining av B ^ε -trädet. Liksom ett B ^ε -träd består det av noder med nycklar och buffertar och realiserar den optimala avvägningen mellan insättning/fråga. Fraktalträdsindexet skiljer sig genom att inkludera prestandaoptimering och i att utöka funktionaliteten. Exempel på förbättrad funktionalitet inkluderar ACID- semantik. B-trädimplementationer av ACID-semantik involverar vanligtvis låsning av rader som är involverade i en aktiv transaktion. Ett sådant schema fungerar bra i ett B-träd eftersom både infogningar och frågor innebär att man hämtar samma blad i minnet. Låsning av en infogat rad medför alltså ingen IO-straff. Men i fraktalträdindex är infogningar meddelanden, och en rad kan finnas i mer än en nod samtidigt. Fraktalträdindex kräver därför en separat låsstruktur som är IO-effektiv eller finns i minnet för att implementera låsningen som är involverad i implementering av ACID-semantik.

Fractal tree index har också flera prestandaoptimeringar. Först indexeras buffertar själva för att påskynda sökningar. För det andra är bladen mycket större än i B-träd, vilket möjliggör större komprimering. Faktum är att bladen är valda för att vara tillräckligt stora för att deras åtkomsttid domineras av bandbreddstiden och därför amorterar bort söknings- och rotationslatensen. Stora blad är en fördel med stora intervallfrågor men saktar ner punktfrågor, som kräver åtkomst till en liten del av bladet. Lösningen som implementeras i fraktala trädindex är att ha stora löv som kan hämtas som en helhet för snabba frågor men delas upp i mindre bitar kallar källarnoder som kan hämtas individuellt. Att komma åt en källarnod är snabbare än att komma åt ett blad, på grund av den minskade bandbreddstiden. Således tillåter understrukturen av löv i fraktala trädindex, jämfört med B ^ε -träd, både avstånds- och punktfrågor att vara snabba.

Meddelanden och fraktalträdindex

Insättningar, raderingar och uppdateringar infogas som meddelande i buffertar som tar sig fram mot löven. Meddelandeinfrastrukturen kan utnyttjas för att implementera en mängd andra operationer, av vilka några diskuteras nedan.

Upserts

En upsert är en sats som infogar en rad om den inte finns och uppdaterar den om den gör det. I ett B-träd implementeras en upsert genom att först söka efter raden och sedan implementera en infogning eller en uppdatering, beroende på resultatet av sökningen. Detta kräver att raden hämtas till minnet om den inte redan är cachad. Ett fraktalt trädindex kan implementera en upsert genom att infoga ett speciellt upsert-meddelande. Ett sådant meddelande kan i teorin implementera godtyckliga kodbitar under uppdateringen. I praktiken stöds fyra uppdateringsoperationer:

1. $x:={\text{konstant}}$
2. $x:=x+{\text{konstant}}$ (ett generaliserat steg)
3. $x:=x-{\text{konstant}}$ (en generaliserad minskning)
4. $x:={\begin{cases}0&{\text{if }}x=0\\x-1&{\text{if }}x\ neq 0\end{cases}}$ (en minskning med ett golv på 0)

Dessa motsvarar uppdateringsoperationerna som används i LinkBench, ett riktmärke som Facebook föreslagit. Genom att undvika den initiala sökningen kan uppslagningsmeddelanden förbättra hastigheten för uppslagning i storleksordningar.

Schemaändringar

Hittills har alla meddelandetyper ändrat enstaka rader. Broadcast-meddelanden, som kopieras till alla utgående buffertar, kan dock ändra alla rader i en databas. Till exempel kan broadcast-meddelanden användas för att ändra formatet på alla rader i en databas. Även om det totala arbetet som krävs för att ändra alla rader är oförändrat jämfört med brute-force-metoden för att korsa tabellen, förbättras latensen, eftersom, när meddelandet väl har injicerats i rotbufferten, kommer alla efterföljande frågor att kunna tillämpa schemaändringen till alla rader de möter. Schemaändringen är omedelbar och arbetet skjuts upp till en sådan tidpunkt då buffertar svämmar över och löv skulle ha blivit uppdaterade ändå.

Genomföranden

Fraktalträdsindexet har implementerats och kommersialiserats av Tokutek . Den finns tillgänglig som TokuDB som lagringsmotor för MySQL och MariaDB , och som TokuMX , en mer komplett integration med MongoDB . Fraktalträdindex har också använts i prototypfilsystem, TokuFS och BetrFS.