B⁺-træ

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 7. februar 2022; verifikation kræver 1 redigering .

B⁺-træ er en datastruktur baseret på et B-træ , et balanceret søgetræ med et variabelt, men ofte stort antal børn pr. node. Et B⁺-træ består af en rod, indre noder og blade, roden kan enten være et blad eller en knude med to eller flere børn. $n$

Oprindeligt var strukturen beregnet til at lagre data til effektiv søgning i et blokorienteret lagringsmiljø - især til filsystemer; anvendelse skyldes det faktum, at i modsætning til binære søgetræer har B⁺-træer en meget høj forgreningsfaktor (antallet af pointere fra en overordnet node til børn er normalt i størrelsesordenen 100 eller mere), hvilket reducerer antallet af I/O-operationer, der kræver søgning efter et element i træet.

En variant af B⁺-træet, hvor alle værdier blev gemt i bladknuder, blev systematisk gennemgået i 1979 [1] , idet det bemærkes, at sådanne strukturer er blevet brugt af IBM i VSAM mainframe filadgangsteknologi siden mindst 1973.

Strukturen er meget brugt i filsystemer - NTFS , ReiserFS , NSS , XFS , JFS , ReFS og BFS bruger denne type træ til indeksering af metadata; BeFS bruger også B⁺-træer til at gemme mapper. Relationelle databasestyringssystemer såsom DB2 , Informix , Microsoft SQL Server , Oracle Database (fra version 8), Adaptive Server Enterprise og SQLite understøtter denne type træ til tabelindekser. Blandt NoSQL DBMS'er, der arbejder med nøgleværdi-modellen, er datastrukturen implementeret til dataadgang i CouchDB , MongoDB (ved brug af WiredTiger- lagringsundersystemet ) og Tokyo Cabinet .

Beskrivelse

Et B⁺-træ er et afbalanceret -ær orden (eller grad) søgetræ, der opfylder følgende egenskaber: $n$ $t,$

Hver node indeholder mindst én nøgle; nøglerne i hver node er ordnet, roden indeholder fra til nøgler, enhver anden node indeholder fra til nøgler; blade er ingen undtagelse fra denne regel. Her er en træparameter, der er mindst 2 (og typisk tager værdier fra 50 til 2000 afhængigt af størrelsen på nøglen i forhold til sidestørrelsen, som igen er bestemt af størrelsen på indholdsindtastningen). $en$ $2t-1$ ${\textstyle t-1}$ ${\textstyle 2t-1}$ ${\tekststil t}$
Blade har ingen efterkommere; for alle andre noder, der indeholder nøgler, indeholder den givne node børn. Hvori: $K_{1},\dots ,K_{n},$ $(n+1)$
- det første barn og alle dets børn indeholder nøgler fra intervallet $(-\infty ,K_{1});$
- for det -th barn og alle dets børn indeholder nøgler fra intervallet $2 \leqslant i \leqslant n$ $jeg$ $(K_{i-1},K_{i});$
- $(n+1)$ -th barn og alle dets børn indeholder nøgler fra intervallet $(K_{n},\infty ).$
Dybden af alle blade er den samme.
Blade har et link til en nabo, der giver dig mulighed for hurtigt at krydse træet i stigende rækkefølge af nøgler og links til data.

Bygning

Opbygning af et B⁺-træ kan kræve ombygning af den mellemliggende struktur, dette skyldes, at antallet af nøgler i hver node (undtagen roden) skal være fra til hvor er graden (eller rækkefølgen) af træet. Når du forsøger at indsætte den ( )-te nøgle i noden, bliver det nødvendigt at adskille denne node; den ( )-te nøgle, som er placeret på træets tilstødende lag, fungerer som separatornøgle for de dannede grene . Et særligt tilfælde er opdelingen af roden, da antallet af træets lag stiger i dette tilfælde. Et træk ved at flække et blad af et B⁺-træ er, at det er opdelt i ulige dele. Opdeling af en intern node eller rod resulterer i noder med lige mange nøgler. Opsplitning af et blad kan forårsage en "kædereaktion" af opsplitning af noder, der ender ved roden. $t$ $2t,$ $t$ $2t+1$ ${\textstyle t+1}$ $k.$

Strukturegenskaber

I et B⁺-træ er programmets uafhængighed af strukturen af informationsposten let realiseret.
Søgningen ender nødvendigvis i et ark.
Sletning af en nøgle har den fordel, at sletning altid sker fra arket.
Andre operationer udføres på samme måde som B-træer.
B⁺-træer kræver mere hukommelse at repræsentere end klassiske B-træer.
B⁺-træer har mulighed for at få adgang til nøgler sekventielt.

Grundlæggende handlinger på en struktur

Søg

Roden af B⁺-træet er udgangspunktet for hele rækken af værdier, hvor hver intern knude er et underinterval.

Lad os f.eks. sige, at vi skal finde værdien af en nøgle i et B⁺-træ. For at gøre dette leder vi efter en bladknude, der indeholder værdien. Ved hver indre knude skal vi finde ud af, hvilken efterfølgende underknude, der skal følges, B⁺-træets indre knude har højst børn, hvor hver af dem repræsenterer en separat delinterval. Den relevante node vælges ved at søge i nodens nøgleværdier: $k$ $k.$ $t$

Funktion : søg ( k ) returner træsøgning ( k , rod ); Funktion : tree_search ( k , node ) hvis node er et blad, så returner node ; switch k do case k < k [ 0 ] return tree_search ( k , p [ 0 ]); case k [ i ] ≤ k < k [ i + 1 ] returner træ_søgning ( k , p [ i + 1 ]); case k [ d ] ≤ k returner træ_søgning ( k , p [ d + 1 ]);

(Denne pseudokode antager, at dubletter ignoreres.)

Tilføjer

For at tilføje en ny nøgle eller en ny post skal du først finde den node, hvor du vil tilføje dem. I dette tilfælde er algoritmen:

Hvis noden ikke er helt udfyldt (antallet af elementer efter indsættelse er ikke mere end ), så tilføj en nøgle (record). $2t-1,$
Ellers skal du opdele noden:
- opret en ny node, flyt derefter halvdelen af elementerne fra den nuværende til den nye;
- tilføje den mindste nøgle fra den nye node og adressen til den (noden) til den overordnede;
- hvis den overordnede node er fuld, opdeles den på samme måde:
  - tilføje den midterste nøgle til den overordnede node;
- gentag indtil den overordnede node skal opdeles.
Hvis roden deler sig, skal du oprette en ny rod med én nøgle og to pointere (nøglen, der er tilføjet til roden, fjernes fra dens node)

B-træer, i modsætning til B⁺-træer, udvider sig fra siden af roden, ikke bladene.

Fjernelse

For at slette en nøgle eller post skal du først finde den bladknude, hvor den ligger. Algoritme til fjernelse fra en bladknude:

Hvis noden er mindst halvfuld, afsluttes algoritmen;
Hvis noden har færre elementer, så:
- forsøg på at omfordele elementer, det vil sige tilføje et element fra "broren" til noden - et element med en fælles forfader.
- hvis omfordelingen mislykkes, flette noden med "broderen".
Hvis der opstår en fletning, skal du fjerne nøglen eller indtastningen, der peger på den eksterne node eller dens "søskende" fra den overordnede node.

Unionen kan strække sig til roden, i hvilket tilfælde træets højde falder.

Beregningsmæssig kompleksitet af operationer

Den beregningsmæssige kompleksitet af hver operation i værste fald: hvor er rækkefølgen af træet eller forgreningsfaktoren; er antallet af elementer i træet af grene i træets noder. $O(\log {\frac {t}{2n)))$ $t$ $n$

Noter

↑ Douglas Comer. The Ubiquitous B-Tree // ACM Computing Surveys. - 1979. - Juni ( bind 11 , nr. 2 ). - S. 121-137 . — ISSN 0360-0300 . Arkiveret fra originalen den 17. november 2015.

Litteratur

Zubov V. S., Shevchenko I. V. Kapitel 6. Søgning i ikke-binære træer - B-træer // Strukturer og metoder til databehandling. Workshop i Delphi-miljøet. - Filin, 2004. - S. 144-164. — ISBN 5-9216-0053-9 .
Donald Knuth . 4. Generering af alle træer. Historie om kombinatorisk generation // The Art of Programming = The Art of Computer Programming. - M. : "Williams" , 2007. - V. 4. - S. 160. - ISBN 0-321-33570-8 .

Links

B⁺ Trævisualisering - B+ Trævisualisering

Træ (datastruktur)
Binært søgetræ Træ (grafteori) træstruktur
Binære træer	binært træ T-træ
Selvbalancerende binære træer	AA træ AVL træ Rød-sort træ Splay træ træ med bøder kartesisk træ Fibonacci træ B-træ T-træ
B-træer	2-3-træ B⁺-træ B*-træ B x -træ UB træ 2-3-4 træ (a,b)-træ dansende træ
præfiks træer	suffiks træ Komprimeret præfikstræ Ternært søgetræ
Binær opdeling af rummet	k-dimensionelt træ VP træ
Ikke-binære træer	Quadtree oktre Sparsom Voxel Octree eksponentielt træ PQ træ
At bryde rummet op	R-træ Hilbert R-træ R+-træ R*-træ X-træ M-træ Fenwick træ Segmenttræ
Andre træer	dynge hash træ fingertræ metrisk træ Belægning træ BK-træ Dobbeltkædet træ iDistance Linkskåret træ LSM træ
Algoritmer	Bredde først søgning Dybde første søgning DSW algoritme spanning tree protokol