B+ träd

B+ träd
B+ träd
Typ	Träd (datastruktur)
Tidskomplexitet i stor O-notation
Algoritm
Algoritm	Genomsnitt
Plats	O( n )
Sök	O(log n )
Föra in	O(log n )
Radera	O(log n )

Ett B+-träd är ett m-ärt träd med ett variabelt men ofta stort antal barn per nod. Ett B+-träd består av en rot, inre noder och löv. Roten kan vara antingen ett löv eller en nod med två eller flera barn.

Ett B+-träd kan ses som ett B-träd där varje nod endast innehåller nycklar (inte nyckel-värdepar), och till vilket en ytterligare nivå läggs till längst ner med länkade löv.

Det primära värdet av ett B+-träd är att lagra data för effektiv hämtning i ett blockorienterat lagringssammanhang - i synnerhet filsystem . Detta beror främst på att till skillnad från binära sökträd har B+-träd mycket hög fanout (antal pekare till underordnade noder i en nod, vanligtvis i storleksordningen 100 eller fler), vilket minskar antalet I/O-operationer som krävs för att hitta ett element i trädet.

Historia

Det finns inget enskilt papper som introducerar B+-trädkonceptet. Istället tas idén om att behålla all data i lövnoder upprepade gånger upp som en intressant variant. Douglas Comer noterar i en tidig undersökning av B-träd (som också omfattar B+-träd) att B+-trädet användes i IBMs VSAM- programvara för dataåtkomst, och hänvisar till en IBM publicerad artikel från 1973.

Strukturera

Som med andra träd kan B+-träd representeras som en samling av tre typer av noder: rot , inre och löv . Dessa nodtyper har följande egenskaper:

Enskilda noder kommer att ha antingen nycklar eller barn , men aldrig båda samtidigt: detta är huvudskillnaden från ett B-träd .
Ordningen eller förgreningsfaktorn $b$ för ett B+-träd mäter kapaciteten hos interna noder, dvs deras maximalt tillåtna antal direkta barnnoder . Detta värde är konstant över hela trädet.
Interna noder har inga nycklar, men kommer alltid att ha barn som inte är noll. Det faktiska antalet barn $m$ för en given intern nod är begränsat så att $\lceil b/2\rceil \leq m\leq b$ . Varje barn hänvisas sedan till som $p_{i}$ för ${\displaystyle i\in [1,m-1]} ,$ där $p_{ i}$ representerar den underordnade noden vid naturligt talindex $i\in \mathbf {N}$ .
Bladnoder har inga underordnade, och innehåller istället elementen i B+-trädet som nycklar. Antalet nycklar $n$ som finns i en given bladnod måste uppfylla den dubbla olikheten $\lceil b/2\rceil \leq n\leq b$ .
Roten anses vanligtvis vara en speciell typ av intern nod som kan ha så få som 2 barn. Detta översätts till $2\leq m\leq b$ . Till exempel, om ordningen $b$ för ett B+-träd är 7, kan varje intern nod ha mellan $\lceil 7/2\rceil =4$ och 7 barn, medan roten kan ha mellan 2 och 7.
I situationen där ett B+-träd är tomt eller innehåller exakt 1 nod, blir roten istället det enda bladet. I detta fall måste antalet nycklar $n$ uppfylla $0\leq n\leq b-1$ .

Ett konkret exempel på dessa gränser visas i tabellen nedan:

Nodtyp	Barn Typ	Minsta antal barn	Max antal barn	Exempel $b=7$	Exempel $b=100$
Rotnod (när det är den enda noden i trädet)	Uppgifter	0	$b-1$	0–6	0–99
Rotnod	Interna noder eller bladnoder	2	$b$	2–7	2–100
Intern nod	Interna noder eller bladnoder	$\lceil b/2\rceil$	$b$	4–7	50–100
Bladnod	Uppgifter	$\lceil b/2\rceil$	$b$	4–7	50–100

Intervaller i interna noder

Ett enkelt B+-trädexempel som länkar nycklarna 1–7 till datavärden d ₁ -d ₇ . Den länkade listan (röd) tillåter snabb övergång i ordning. Detta speciella träds förgreningsfaktor är

b

=4. Både nycklar i blad och interna noder är färgade grå här.

Per definition är varje värde som finns i B+-trädet en nyckel som finns i exakt en lövnod. Varje nyckel måste vara direkt jämförbar med varannan nyckel, vilket utgör en totalorder . Detta gör det möjligt för varje bladnod att hålla alla sina nycklar sorterade hela tiden, vilket sedan gör det möjligt för varje inre nod att konstruera en ordnad samling av intervall som representerar den sammanhängande omfattningen av värden som finns i ett givet blad. Interna noder högre upp i trädet kan sedan konstruera sina egna intervall, som rekursivt aggregerar intervallen som finns i deras egna underordnade interna noder. Så småningom representerar roten av ett B+-träd hela intervallet av värden i trädet, där varje intern nod representerar ett delintervall.

För att denna rekursiva intervallinformation ska behållas måste interna noder dessutom innehålla $m-1$ kopior av nycklar $l_{i}$ för $i\in [1,m-1]$ representerar det minsta elementet inom det intervall som täcks av barnet med index $i$ (som i sig kan vara en intern nod eller ett blad).

Egenskaper

För ett B+-träd av b-ordningen med $h$ $-$ indexnivåer: ^{[ citat behövs ]}

Det maximala antalet lagrade poster är $n_{\max }=b^{h}-b^{h-1}$
Minsta antal lagrade poster är $n_{\min }=2\left\lceil {\tfrac {b}{2} }\right\rceil ^{h-1}-2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-2}$
Minsta antal nycklar är $n_{\mathrm {kmin} }=2\left\lceil {\tfrac {b}{2}}\ höger\rceil ^{h-1}-1$
Det maximala antalet nycklar är $n_{\mathrm {kmax} }=b^{h}-1$
Utrymmet som krävs för att lagra trädet är $O(n)$
För att infoga en post krävs $O(\log _{b}n)$ operationer
För att hitta en post krävs $O(\log _{b}n)$ operationer
Att ta bort en (tidigare lokaliserad) post kräver $O(\log _{b}n)$ operationer
Att utföra en intervallfråga med k element som förekommer inom intervallet kräver $O(\log _{b}n+k)$ operationer
B+-trädstrukturen expanderar/kontrakterar när antalet poster ökar/minskar. Det finns inga begränsningar för storleken på B+-träd. Alltså öka användbarheten av ett databassystem .
Eventuella förändringar i strukturen påverkar inte prestanda på grund av balanserade trädegenskaper.
Datan lagras i lövnoderna och mer förgrening av interna noder hjälper till att minska trädets höjd och därmed minska söktiden. Som ett resultat fungerar det bra i sekundära lagringsenheter.
Sökningen blir extremt enkel eftersom alla poster endast lagras i bladnoden och sorteras sekventiellt i den länkade listan.
Vi kan hämta räckviddshämtning eller partiell hämtning med B+-träd. Detta görs enklare och snabbare genom att korsa trädstrukturen. Denna funktion gör att B+-trädstrukturen tillämpas i många sökmetoder.

Algoritmer

Sök

Vi söker ett värde $k$ i B+-trädet. Det betyder att vi med utgångspunkt från roten letar efter bladet som kan innehålla värdet $k$ . Vid varje nod räknar vi ut vilken intern nod vi ska följa. En intern B+-trädnod har högst $m\leq b$ barn, där var och en av dem representerar olika delintervall. Vi väljer motsvarande barn via en linjär sökning av $m-$ posterna, och när vi äntligen kommer till ett blad gör vi en linjär sökning av dess $n$ element efter den önskade nyckeln. Eftersom vi bara korsar en gren av alla barn vid varje steg i trädet, uppnår vi $O(\log N)$ körtid, där $N$ är det totala antalet nycklar lagrade i bladen på B+-trädet.

     funktionssökning  (  k  ,  rot  )  är  let  leaf = leaf_search(k, rot)  för  leaf_key  i  leaf.keys():  om  k = leaf_key:  return  true  return  false

     
      funktion  leaf_search(  k  ,  nod  )  är  om  noden är ett blad:  returnera  nod  låt  p = node.children()  låt  l = node.left_sided_intervals()  hävda  $|p|=|l|+1$  låt  m = p.len()  för  i  från  1  till  m - 1:  om  $k\leq l[i]$  :  return  leaf_search(k, p[i])  return  leaf_search(k, p[m])

Observera att denna pseudokod använder 1-baserad matrisindexering.

Införande

Utför en sökning för att avgöra vilken hink den nya posten ska hamna i.
Om hinken inte är full (högst $b-1$ poster efter infogningen), lägg till posten.
Annars innan du infogar den nya posten
- dela hinken.
  - originalnoden har ⎡(L+1)/2⎤-objekt
  - ny nod har ⎣(L+1)/2⎦ objekt
- Kopiera ⎡(L+1)/2⎤-te nyckeln till föräldern och infoga den nya noden till föräldern.
- Upprepa tills en förälder hittas som inte behöver delas.
- Infoga den nya posten i den nya noden.
Om roten delar sig, behandla den som om den har en tom förälder och dela den enligt konturen ovan.

B-träd växer vid roten och inte vid löven.

Bulklastning

Med tanke på en samling dataposter vill vi skapa ett B+-trädindex på något nyckelfält. En metod är att infoga varje post i ett tomt träd. Det är dock ganska dyrt, eftersom varje post kräver att vi börjar från roten och går ner till lämplig bladsida. Ett effektivt alternativ är att använda bulklastning.

Det första steget är att sortera dataposterna enligt en söknyckel i stigande ordning.
Vi tilldelar en tom sida för att fungera som roten och infogar en pekare till den första sidan med poster i den.
När roten är full delar vi upp roten och skapar en ny rotsida.
Fortsätt att infoga poster på indexsidan längst till höger precis ovanför bladnivån tills alla poster är indexerade.

Notera :

när indexsidan längst till höger ovanför bladnivån fylls upp delas den;
denna åtgärd kan i sin tur orsaka en uppdelning av indexsidan längst till höger ett steg närmare roten;
sprickor förekommer endast längst till höger från roten till bladnivån.

Radering

Syftet med raderingsalgoritmen är att ta bort den önskade ingångsnoden från trädstrukturen. Vi rekursivt raderingsalgoritmen på lämplig nod tills ingen nod hittas. För varje funktionsanrop går vi vidare och använder indexet för att navigera tills vi hittar noden, tar bort den och arbetar sedan tillbaka till roten.

Vid post L som vi vill ta bort:

– Om L är minst halvfullt, klart

- Om L bara har d-1-poster, försök att omfördela, låna från syskon (intilliggande nod med samma förälder som L).

Efter omfördelningen av två syskonnoder måste den överordnade noden uppdateras för att återspegla denna förändring. Indexnyckeln som pekar på det andra syskonen måste ta det minsta värdet av den noden för att vara indexnyckeln.

- Om omfördelningen misslyckas, slå samman L och syskon. Efter sammanslagning uppdateras den överordnade noden genom att radera indexnyckeln som pekar på den raderade posten. Med andra ord, om sammanslagning inträffade, måste du radera posten (som pekar på L eller syskon) från förälder till L.

Notera: merge kan fortplanta sig till root, vilket innebär att höjden minskar.

B+ träd radering

Genomförande

Bladen (de nedersta indexblocken) i B+-trädet är ofta länkade till varandra i en länkad lista; detta gör intervallfrågor eller en (ordnad) iteration genom blocken enklare och mer effektiv (även om den ovan nämnda övre gränsen kan uppnås även utan detta tillägg). Detta ökar inte utrymmesförbrukningen eller underhållet på trädet avsevärt. Detta illustrerar en av de betydande fördelarna med ett B+träd framför ett B-träd; i ett B-träd, eftersom inte alla nycklar finns i bladen, kan en sådan ordnad länkad lista inte konstrueras. Ett B+träd är därför särskilt användbart som ett databassystemindex, där data vanligtvis finns på disk, eftersom det tillåter B+trädet att faktiskt tillhandahålla en effektiv struktur för att hysa själva data (detta beskrivs i som indexstruktur "Alternativt 1").

Om ett lagringssystem har en blockstorlek på B byte och nycklarna som ska lagras har en storlek på k, är förmodligen det mest effektiva B+-trädet ett där $b={\tfrac {B} {k}}-1$ . Även om engången teoretiskt sett är onödig, är det i praktiken ofta lite extra utrymme som tas upp av indexblocken (till exempel de länkade listhänvisningarna i bladblocken). Att ha ett indexblock som är något större än lagringssystemets faktiska block representerar en betydande prestandaminskning; därför är det att föredra att vara försiktig.

Om noder i B+-trädet är organiserade som arrayer av element kan det ta lång tid att infoga eller ta bort ett element eftersom hälften av arrayen kommer att behöva förskjutas i genomsnitt. För att övervinna detta problem kan element inuti en nod organiseras i ett binärt träd eller ett B+-träd istället för en array.

B+-träd kan också användas för data som lagras i RAM. I det här fallet skulle ett rimligt val för blockstorlek vara storleken på processorns cache-linje.

Utrymmeseffektiviteten för B+-träd kan förbättras genom att använda vissa kompressionstekniker. En möjlighet är att använda deltakodning för att komprimera nycklar som är lagrade i varje block. För interna block kan utrymmesbesparing uppnås genom att antingen komprimera tangenter eller pekare. För strängnycklar kan utrymme sparas genom att använda följande teknik: Normalt innehåller den i -te posten i ett internt block den första nyckeln i blocket $i+1$ . Istället för att lagra hela nyckeln kan vi lagra det kortaste prefixet för den första nyckeln i block $i+1$ som är strikt större (i lexikografisk ordning) än den sista nyckeln i block i . Det finns också ett enkelt sätt att komprimera pekare: om vi antar att några på varandra följande block $i,i+1,...i+k$ lagras kontinuerligt, då räcker det med att lagra endast en pekare till det första blocket och antalet på varandra följande block.

Alla ovanstående kompressionstekniker har vissa nackdelar. Först måste ett helt block dekomprimeras för att extrahera ett enda element. En teknik för att övervinna detta problem är att dela upp varje block i underblock och komprimera dem separat. I det här fallet behöver sökning eller infogning av ett element bara dekomprimeras eller komprimeras ett delblock istället för ett helt block. En annan nackdel med komprimeringstekniker är att antalet lagrade element kan variera avsevärt från ett block till ett annat beroende på hur väl elementen är komprimerade inuti varje block.

Ansökningar

Filsystem

Filsystemen ReiserFS , NSS , XFS , JFS , ReFS och BFS använder alla denna typ av träd för metadataindexering; BFS använder också B+-träd för att lagra kataloger. NTFS använder B+-träd för katalog- och säkerhetsrelaterad metadataindexering. EXT4 använder utsträckningsträd (en modifierad B+-träddatastruktur) för filomfattningsindexering. APFS använder B+-träd för att lagra mappningar från filsystemobjekt-ID till deras platser på disken och för att lagra filsystemposter (inklusive kataloger), även om dessa träds lövnoder saknar syskonpekare.

Databassystem

Relationella databashanteringssystem som IBM Db2 , Informix , Microsoft SQL Server , Oracle 8 , Sybase ASE och SQLite stöder den här typen av träd för tabellindex, även om varje sådant system implementerar den grundläggande B+-trädstrukturen med variationer och tillägg. Många NoSQL- databashanteringssystem som CouchDB och Tokyo Cabinet stöder också denna typ av träd för dataåtkomst och lagring.

Att hitta objekt i en högdimensionell databas som är jämförbara med ett visst frågeobjekt är en av de mest använda och ändå dyrbara procedurerna i sådana system. ^{[ citat behövs ]} I sådana situationer är det produktivt att hitta den närmaste grannen med hjälp av ett B+-träd.

iDistance

B+-trädet används effektivt för att konstruera en indexerad sökmetod som kallas iDistance. iDistance söker efter k närmaste grannar (kNN) i högdimensionella metriska utrymmen. Data i dessa högdimensionella utrymmen är uppdelade baserat på utrymmes- eller partitionsstrategier, och varje partition har ett indexvärde som är nära med avseende på partitionen. Härifrån kan dessa punkter implementeras effektivt med hjälp av B+-trädet, sålunda mappas frågorna till sökning med enstaka dimensioner. Med andra ord kan iDistance-tekniken ses som ett sätt att påskynda den sekventiella skanningen. Istället för att skanna poster från början till slutet av datafilen, startar iDistance skanningen från platser där de närmaste grannarna kan erhållas tidigt med mycket stor sannolikhet.

NVRAM

Icke-flyktigt slumpmässigt minne (NVRAM) har använt B+-trädstrukturen som den huvudsakliga minnesåtkomsttekniken för Internet Of Things-systemet (IoT) på grund av dess icke-statiska strömförbrukning och höga soliditet hos cellminnet. B+ kan reglera trafiken av data till minnet effektivt. Dessutom, med avancerade strategier för frekvenser för något mycket använda blad eller referenspunkt, visar B+-trädet betydande resultat för att öka uthålligheten hos databassystem.

Se även

^ ^a ^b ^c ^d Navathe, Ramez Elmasri, Shamkant B. (2010). Grunderna i databassystem (6:e upplagan). Upper Saddle River, NJ: Pearson Education. s. 652–660. ISBN 9780136086208 .
^ Comer, Douglas (1979). "Ubiquitous B-Tree" . ACM Computing Surveys . 11 (2): 121–137. doi : 10.1145/356770.356776 . S2CID 101673 .
^ ^a ^b Pollari-Malmi, Kerttu. " "B+ träd" " (PDF) . Datavetenskap, Naturvetenskapliga fakulteten, Helsingfors universitet . sid. 3. Arkiverad från originalet (PDF) 2021-04-14.
^ Grust, Torsten (sommaren 2013). " "Trädstrukturerad indexering: ISAM- och B+-träd" " ( PDF) . Logo der Universität Tübingen Institutionen för datavetenskap: Databassystem . sid. 84. Arkiverad från originalet (PDF) 2021-11-28.
^ ^a ^b "Databassystem för avancerade applikationer". Skalbar uppdelning av massiva dataströmmar .
^ "[Databassystem för avancerade applikationer "Uppdateringsmigrering: Ett effektivt B+-träd för Flash-lagring"]". Lecture Notes in Computer Science, Vol 5982. Springer, Berlin, Heidelberg .
^ "ECS 165B: Databassystemimplementering föreläsning 6" (PDF) . UC Davis CS-avdelning . 9 april 2010. s. 21–23.
^ Ramakrishnan, Raghu; Johannes Gehrke (2003). Databashanteringssystem (3:e upplagan). Boston: McGraw-Hill. ISBN 0-07-246563-8 . OCLC 49977005 .
^ ^a ^b ^c ^d ^e ^f Ramakrishnan Raghu, Gehrke Johannes – Database Management Systems, McGraw-Hill Higher Education (2000), 2:a upplagan (en) sida 267
^ Giampaolo, Dominic (1999). Praktisk design av filsystem med Be File System (PDF) . Morgan Kaufmann. ISBN 1-55860-497-9 . Arkiverad från originalet (PDF) 2017-02-13 . Hämtad 2014-07-29 .
^ "B-träd". Apple filsystemreferens (PDF) . Apple Inc. 2020-06-22. sid. 122 . Hämtad 2021-03-10 .
^ SQLite version 3 översikt
^ CouchDB Guide (se anmärkning efter 3:e stycket)
^ Tokyo kabinettreferens Arkiverad September 12, 2009, på Wayback Machine
^ Databassystem för avancerade applikationer . Japan. 2010.
^ Jagadish, HV; Ooi, Beng Chin; Tan, Kian-Lee; Yu, Cui; Zhang, Rui (juni 2005). "iDistance: En adaptiv B+-trädbaserad indexeringsmetod för närmaste grannesökning" . ACM-transaktioner på databassystem . 30 (2): 364–397. doi : 10.1145/1071610.1071612 . ISSN 0362-5915 . S2CID 967678 .
^ Dharamjeet; Chen, Tseng-Yi; Chang, Yuan-Hao; Wu, Chun-Feng; Lee, Chi-Heng; Shih, Wei-Kuan (december 2021). "Beyond Write-Reduction Consideration: A Wear-Leveling-Enabled B⁺-Tree Indexing Scheme över en NVRAM-baserad arkitektur" . IEEE-transaktioner på datorstödd design av integrerade kretsar och system . 40 (12): 2455–2466. doi : 10.1109/TCAD.2021.3049677 . ISSN 0278-0070 . S2CID 234157183 .

externa länkar

Genomföranden

[Navathe-1] Navathe, Ramez Elmasri, Shamkant B. (2010). Grunderna i databassystem (6:e upplagan). Upper Saddle River, NJ: Pearson Education. s. 652–660. ISBN 9780136086208 .

[2] Comer, Douglas (1979). "Ubiquitous B-Tree" . ACM Computing Surveys . 11 (2): 121–137. doi : 10.1145/356770.356776 . S2CID 101673 .

[algorithms-pdf-3] Pollari-Malmi, Kerttu. " "B+ träd" " (PDF) . Datavetenskap, Naturvetenskapliga fakulteten, Helsingfors universitet . sid. 3. Arkiverad från originalet (PDF) 2021-04-14.

[total-order-4] Grust, Torsten (sommaren 2013). " "Trädstrukturerad indexering: ISAM- och B+-träd" " ( PDF) . Logo der Universität Tübingen Institutionen för datavetenskap: Databassystem . sid. 84. Arkiverad från originalet (PDF) 2021-11-28.

[:0-5] "Databassystem för avancerade applikationer". Skalbar uppdelning av massiva dataströmmar .

[6] "[Databassystem för avancerade applikationer "Uppdateringsmigrering: Ett effektivt B+-träd för Flash-lagring"]". Lecture Notes in Computer Science, Vol 5982. Springer, Berlin, Heidelberg .

[7] "ECS 165B: Databassystemimplementering föreläsning 6" (PDF) . UC Davis CS-avdelning . 9 april 2010. s. 21–23.

[8] Ramakrishnan, Raghu; Johannes Gehrke (2003). Databashanteringssystem (3:e upplagan). Boston: McGraw-Hill. ISBN 0-07-246563-8 . OCLC 49977005 .

[DMS-9] ^ ^a ^b ^c ^d ^e ^f Ramakrishnan Raghu, Gehrke Johannes – Database Management Systems, McGraw-Hill Higher Education (2000), 2:a upplagan (en) sida 267

[practical-book-10] Giampaolo, Dominic (1999). Praktisk design av filsystem med Be File System (PDF) . Morgan Kaufmann. ISBN 1-55860-497-9 . Arkiverad från originalet (PDF) 2017-02-13 . Hämtad 2014-07-29 .

[11] "B-träd". Apple filsystemreferens (PDF) . Apple Inc. 2020-06-22. sid. 122 . Hämtad 2021-03-10 .

[SQLite-12] SQLite version 3 översikt

[CouchDB-13] CouchDB Guide (se anmärkning efter 3:e stycket)

[TC-14] Tokyo kabinettreferens Arkiverad September 12, 2009, på Wayback Machine

[15] Databassystem för avancerade applikationer . Japan. 2010.

[16] Jagadish, HV; Ooi, Beng Chin; Tan, Kian-Lee; Yu, Cui; Zhang, Rui (juni 2005). "iDistance: En adaptiv B+-trädbaserad indexeringsmetod för närmaste grannesökning" . ACM-transaktioner på databassystem . 30 (2): 364–397. doi : 10.1145/1071610.1071612 . ISSN 0362-5915 . S2CID 967678 .

[17] Dharamjeet; Chen, Tseng-Yi; Chang, Yuan-Hao; Wu, Chun-Feng; Lee, Chi-Heng; Shih, Wei-Kuan (december 2021). "Beyond Write-Reduction Consideration: A Wear-Leveling-Enabled B⁺-Tree Indexing Scheme över en NVRAM-baserad arkitektur" . IEEE-transaktioner på datorstödd design av integrerade kretsar och system . 40 (12): 2455–2466. doi : 10.1109/TCAD.2021.3049677 . ISSN 0278-0070 . S2CID 234157183 .

Träddatastrukturer
Sökträd ( dynamiska uppsättningar / associativa arrayer )	2–3 2–3–4 AA (a,b) AVL B B+ B* B ^x ( Optimal ) Binär sökning Dans HTree Intervall Beställningsstatistik ( Vänsterlutad ) Röd–svart Syndabock Splay T Treap DU ÄR Viktbalanserad
Högar	Binär Binom Brodal Fibonacci Vänsterman Parning Skev van Emde Boas Svag
Försöker	Ctrie C-trie (komprimerad ADT) Hash Radix Ändelse Ternär sökning X-snabb Y-snabb
Rumsliga datapartitioneringsträd	Boll BK BSP kartesiska Hilbert R k -d ( implicit k -d ) M Metrisk MVP Octree PH Prioritet R Quad R R+ R* Segmentet VP X
Andra träd	Omslag Exponentiell Fenwick Finger Fraktalträdindex Fusion Hash kalender iDistance K-ary Vänster-barn höger-syskon Länka/klippa Loggstrukturerad sammanslagning Merkle PQ Räckvidd SPQR Topp