B⁺-träd

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 7 februari 2022; verifiering kräver 1 redigering .

B⁺-träd är en datastruktur baserad på ett B-träd , ett balanserat sökträ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. $n$

Inledningsvis var strukturen tänkt att lagra data för effektiv sökning i en blockorienterad lagringsmiljö - i synnerhet för filsystem; tillämpningen beror på det faktum att, till skillnad från binära sökträd, har B⁺-träd en mycket hög förgreningsfaktor (antalet pekare från en föräldernod till barn är vanligtvis i storleksordningen 100 eller mer), vilket minskar antalet I/O-operationer som kräver sökning efter ett element i trädet.

En variant av B⁺-trädet, där alla värden lagrades i bladnoder, granskades systematiskt 1979 [1] och noterade att sådana strukturer har använts av IBM i VSAM stordatorfilåtkomstteknologi sedan åtminstone 1973.

Strukturen används ofta i filsystem - NTFS , ReiserFS , NSS , XFS , JFS , ReFS och BFS använder den här typen av träd för att indexera metadata; BeFS använder också B⁺-träd för att lagra kataloger. Relationella databashanteringssystem som DB2 , Informix , Microsoft SQL Server , Oracle Database (från version 8), Adaptive Server Enterprise och SQLite stöder den här typen av träd för tabellindex. Bland NoSQL DBMS:er som arbetar med nyckel-värde-modellen är datastrukturen implementerad för dataåtkomst i CouchDB , MongoDB (vid användning av WiredTiger- lagringsundersystemet ) och Tokyo Cabinet .

Beskrivning

Ett B⁺-träd är ett sökträd med balanserad -är ordning (eller grad) som uppfyller följande egenskaper: $n$ $t,$

Varje nod innehåller minst en nyckel; nycklarna i varje nod är ordnade, roten innehåller från till nycklar, vilken annan nod som helst innehåller från till nycklar; löv är inget undantag från denna regel. Här är en trädparameter som är minst 2 (och tar vanligtvis värden från 50 till 2000 beroende på storleken på nyckeln i förhållande till sidstorleken, som i sin tur bestäms av storleken på innehållsposten). $ett$ $2t-1$ ${\textstyle t-1}$ ${\textstyle 2t-1}$ ${\textstyle t}$
Blad har inga ättlingar; för alla andra noder som innehåller nycklar, innehåller den givna noden barn. Vart i: $K_{1},\dots ,K_{n},$ $(n+1)$
- det första barnet och alla dess barn innehåller nycklar från intervallet $(-\infty ,K_{1});$
- för det -te barnet och alla dess underordnade innehåller nycklar från intervallet $2 \leqslant i \leqslant n$ $i$ $(K_{i-1},K_{i});$
- $(n+1)$ -te barnet och alla dess barn innehåller nycklar från intervallet $(K_{n},\infty ).$
Djupet på alla blad är detsamma.
Löv har en länk till en granne som gör att du snabbt kan korsa trädet i stigande nycklarordning och länkar till data.

Byggnad

Att bygga ett B⁺-träd kan kräva ombyggnad av den mellanliggande strukturen, detta beror på att antalet nycklar i varje nod (förutom roten) måste vara från till var är graden (eller ordningen) av trädet. När du försöker infoga den ( )-te nyckeln i noden, blir det nödvändigt att separera denna nod; den ( )-te nyckeln, som är placerad på den intilliggande nivån av trädet, fungerar som separatornyckeln för de bildade grenarna . Ett specialfall är uppdelningen av roten, eftersom i det här fallet ökar antalet nivåer av trädet. En egenskap med att klyva ett blad av ett B⁺-träd är att det är uppdelat i ojämna delar. Att dela en intern nod eller rot resulterar i noder med lika många nycklar Att dela ett löv kan orsaka en "kedjereaktion" av delande noder, som slutar vid roten. $t$ $2t,$ $t$ $2t+1$ ${\textstyle t+1}$ $k.$

Strukturegenskaper

I ett B⁺-träd är programmets oberoende av informationspostens struktur lätt realiserat.
Sökningen slutar nödvändigtvis i ett ark.
Att ta bort en nyckel har fördelen att radering alltid sker från arket.
Andra operationer utförs på samma sätt som B-träd.
B⁺-träd kräver mer minne för att representera än klassiska B-träd.
B⁺-träd har möjlighet att komma åt nycklar sekventiellt.

Grundläggande operationer på en struktur

Sök

Roten till B⁺-trädet är utgångspunkten för hela värdeintervallet, där varje intern nod är ett delintervall.

Låt oss till exempel säga att vi behöver hitta värdet på en nyckel i ett B⁺-träd. För att göra detta letar vi efter en lövnod som innehåller värdet. Vid varje intern nod måste vi ta reda på vilken efterföljande barnnod som ska följas, den interna noden i B⁺-trädet har högst barn, där var och en av dem representerar en separat delintervall. Lämplig nod väljs genom att söka i nodens nyckelvärden: $k$ $k.$ $t$

Funktion : sök ( k ) returnera trädsökning ( k , rot ); Funktion : tree_search ( k , nod ) om noden är ett löv , returnera noden ; switch k do case k < k [ 0 ] return tree_search ( k , p [ 0 ]); fall k [ i ] ≤ k < k [ i + 1 ] returnera trädsökning ( k , p [ i + 1 ]); fall k [ d ] ≤ k returnera trädsökning ( k , p [ d + 1 ]);

(Denna pseudokod förutsätter att dubbletter ignoreras.)

Lägger till

För att lägga till en ny nyckel eller en ny post måste du först hitta noden där du vill lägga till dem. I det här fallet är algoritmen:

Om noden inte är helt fylld (antalet element efter infogning är inte mer än ), lägg sedan till en nyckel (rekord). $2t-1,$
Annars måste du dela noden:
- skapa en ny nod, flytta sedan hälften av elementen från den nuvarande till den nya;
- lägg till den minsta nyckeln från den nya noden och adressen till den (noden) till föräldern;
- om föräldernoden är full, dela den på liknande sätt:
  - lägg till den mellersta nyckeln till föräldranoden;
- upprepa tills föräldranoden behöver delas.
Om roten delar sig, skapa en ny rot med en nyckel och två pekare (nyckeln som läggs till roten tas bort från dess nod)

B-träd, till skillnad från B⁺-träd, expanderar från sidan av roten, inte löven.

Borttagning

För att radera en nyckel eller post måste du först hitta lövnoden där den finns. Algoritm för att ta bort från en lövnod:

Om noden är åtminstone halvfull avslutas algoritmen;
Om noden har färre element, då:
- försök att omfördela element, det vill säga lägga till ett element från "brodern" till noden - ett element med en gemensam förfader.
- om omfördelningen misslyckas, slå samman noden med "brodern".
Om en sammanslagning inträffar, ta bort nyckeln eller posten som pekar på fjärrnoden eller dess "syskon" från föräldernoden.

Unionen kan sträcka sig till roten, i vilket fall trädets höjd minskar.

Beräkningskomplexitet för operationer

Beräkningskomplexiteten för varje operation i värsta fall: var är trädets ordning eller förgreningsfaktorn; är antalet element i trädet av grenar i trädets noder. $O(\log {\frac {t}{2n)))$ $t$ $n$

Anteckningar

↑ Douglas Comer. The Ubiquitous B-Tree // ACM Computing Surveys. - 1979. - Juni ( vol. 11 , nr 2 ). - S. 121-137 . — ISSN 0360-0300 . Arkiverad från originalet den 17 november 2015.

Litteratur

Zubov V. S., Shevchenko I. V. Kapitel 6. Sökning i icke-binära träd - B-träd // Strukturer och metoder för databehandling. Workshop i Delphi-miljön. - Filin, 2004. - S. 144-164. — ISBN 5-9216-0053-9 .
Donald Knuth . 4. Generering av alla träd. Historien om kombinatorisk generation // Konsten att programmera = Konsten att programmera. - M. : "Williams" , 2007. - V. 4. - S. 160. - ISBN 0-321-33570-8 .

Länkar

B⁺ Trädvisualisering - B+ Trädvisualisering

Träd (datastruktur)
Binärt sökträd Träd (grafteori) trädstruktur
Binära träd	binärt träd T-träd
Självbalanserande binära träd	AA-träd AVL-träd Röd-svart träd Splay träd träd med böter kartesiskt träd Fibonacci träd B-träd T-träd
B-träd	2-3-träd B⁺-träd B*-träd B x -träd UB-träd 2-3-4 träd (a,b)-träd dansande träd
prefix träd	suffixträd Komprimerat prefixträd Ternärt sökträd
Binär uppdelning av utrymme	k-dimensionellt träd VP-träd
Icke-binära träd	Quadtree octree Gles Voxel Octree exponentiellt träd PQ-träd
Bryter upp utrymmet	R-träd Hilbert R-träd R+-träd R*-träd X-träd M-träd Fenwick träd Segment träd
Andra träd	högen haschträd fingerträd metriskt träd Beläggning träd BK-träd Dubbelkedjat träd iDistance Länkklippt träd LSM-träd
Algoritmer	Utöka första sökningen Djup första sökning DSW-algoritm spaning tree-protokoll