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 24 februari 2015; kontroller kräver 46 redigeringar .

B-träd (uttalas på ryska som B-träd ) är en datastruktur , ett sökträd. Ur den yttre logiska representationens synvinkel - ett balanserat , mycket grenat träd . Används ofta för att lagra data i externt minne.

Användningen av B-träd föreslogs först av R. Bayer och E. McCreight 1970 .

Balanserad betyder att längden på två valfria vägar från roten till bladen inte skiljer sig mer än en.

Förgrening av ett träd är egenskapen för varje trädnod att hänvisa till ett stort antal efterkommande noder.

Ur fysisk organisations synvinkel representeras B-trädet som en multiliststruktur av minnessidor, det vill säga varje nod i trädet motsvarar ett minnesblock (sida). Inner- och bladsidor har vanligtvis en annan struktur.

Applikation

B-trädstrukturen används för att organisera index i många moderna DBMS .

Ett B-träd kan användas för att strukturera (indexera) information på en hårddisk (vanligtvis metadata). Åtkomsttiden till ett godtyckligt block på en hårddisk är mycket lång (i storleksordningen millisekunder), eftersom den bestäms av skivrotationshastigheten och huvudets rörelse. Därför är det viktigt att minska antalet noder som skannas vid varje operation. Att använda en listsökning varje gång för att hitta ett slumpmässigt block kan leda till ett för stort antal diskåtkomster på grund av behovet att sekventiellt passera genom alla dess element som föregår det givna, medan sökningen i B-trädet, på grund av egenskaperna för balans och hög förgrening, kan avsevärt minska antalet sådana operationer.

Den relativt enkla implementeringen av algoritmer och förekomsten av färdiga bibliotek (inklusive de för C ) för att arbeta med B-trädstrukturen gör sådan minnesorganisation populär i en mängd olika program som arbetar med stora mängder data.

Struktur och principer för konstruktion

Ett B-träd är ett träd som uppfyller följande egenskaper:

Nycklarna i varje nod är vanligtvis beställda för enkel åtkomst. Roten innehåller från 1 till 2t-1 nycklar. Alla andra noder innehåller nycklar från t-1 till 2t-1. Blad är inget undantag från denna regel. Här är t en trädparameter som är minst 2 (och tar vanligtvis värden från 50 till 2000 [1] ).
Bladen har ingen avkomma. Alla andra noder som innehåller nycklar , …, , innehåller barn. Vart i $K_1$ $K_n$ $n+1$
1. Det första barnet och alla dess barn innehåller nycklar från intervallet $(-\infty, K_1)$
2. För innehåller det i-te barnet och alla dess underordnade nycklar från intervallet $2\le i\le n$ $(K_{i-1}, K_i)$
3. $(n+1)$ -te barnet och alla dess barn innehåller nycklar från intervallet $(K_n,\infty)$
Djupet på alla blad är detsamma.

Egenskap 2 kan anges annorlunda: varje nod i B-trädet, förutom löv, kan betraktas som en ordnad lista där nycklar och pekare till barn alternerar.

Sök

Om nyckeln finns i roten hittas den. Annars bestämmer vi intervallet och går till motsvarande ättling. Vi upprepar.

Lägga till en nyckel

Vi kommer att kalla trädet av ättlingar till en viss nod för ett underträd som består av denna nod och dess ättlingar.

Låt oss först definiera en funktion som lägger till nyckeln K till underträdet för nod x. Efter att ha kört funktionen, i alla passerade noder, utom kanske själva noden x, kommer det att finnas färre än , men inte mindre än , nycklar. $2t-1$ $t-1$

Om x inte är ett löv,
1. Vi bestämmer intervallet där K ska vara. Låt y vara motsvarande barn.
2. Lägg rekursivt till K till y:s efterkommande träd.
3. Om noden y är full, det vill säga den innehåller nycklar, delar vi upp den i två. Noden tar emot den första av y-nycklarna och den första av sina barn, och noden tar emot den sista av y-nycklarna och den sista av sina barn. Medianen för nycklarna för nod y går till nod x, och pekaren till y vid nod x ersätts av pekare till noder och . $2t-1$ $y_1$ $t-1$ $t$ $y_2$ $t-1$ $t$ $y_1$ $y_2$
Om x är ett löv, lägg bara till nyckeln K där.

Låt oss nu definiera hur man lägger till nyckeln K till hela trädet. Bokstaven R står för rotnoden.

Lägg till K till R:s efterkommande träd.
Om R nu innehåller nycklar, dela upp den i två. Noden tar emot den första av R-nycklarna och den första av sina barn, och noden tar emot den sista av R-nycklarna och den sista av sina barn. Medianen för nycklarna för nod R faller in i den nyskapade noden, som blir rotnoden. Noderna blir dess barn . $2t-1$ $R_{1}$ $t-1$ $t$ $R_{2}$ $t-1$ $t$ $R_{1}$ $R_{2}$

Ta bort en nyckel

Om roten också är ett löv, det vill säga det finns bara en nod i trädet, tar vi helt enkelt bort nyckeln från denna nod. Annars hittar vi först noden som innehåller nyckeln och kommer ihåg sökvägen till den. Låt denna nod vara . $x$

Om - blad, radera nyckeln därifrån. Om det finns åtminstone nycklar kvar i noden stannar vi där. Annars tittar vi på antalet nycklar i två närliggande syskonnoder. Om det finns en angränsande högernod, och den har åtminstone nycklar, lägger vi till separatornyckeln mellan den och den intilliggande högra noden, och i stället för denna nyckel sätter vi den första nyckeln till den närliggande högra noden, varefter vi stoppar . Om detta inte är fallet, men det finns en angränsande vänsternod, och den har åtminstone nycklar, lägger vi till separatornyckeln mellan den och den intilliggande vänstra noden, och i stället för denna nyckel sätter vi den sista nyckeln till den angränsande vänster nod, varefter vi stannar. Slutligen, om den vänstra tangenten misslyckas, slår vi samman noden med den närliggande vänstra eller högra noden, och flyttar nyckeln som tidigare separerade dessa två noder till den sammanslagna noden. I det här fallet kan endast nycklar finnas kvar i den överordnade noden . Sedan, om det inte är en rot, utför vi en liknande procedur med den. Om vi som ett resultat har nått roten, och det finns från 1 till nycklar kvar i den, behöver ingenting göras, eftersom roten kan ha färre nycklar. Om det inte finns en enda nyckel kvar i roten, exkluderar vi rotnoden och gör dess enda underordnade till trädets nya rot. $x$ $x$ $t-1$ $t$ $x$ $t$ $x$ $x$ $t-2$ $t-1$ $t-1$

Om det inte är ett löv, och K är dess -:e tangent, radera tangenten längst till höger från underträdet för ättlingar i -: e ättling , eller omvänt, tangenten längst till vänster från underträdet för ättlingar i -: e ättling . Efter det byter vi ut nyckeln K med fjärrnyckeln. Raderingen av nyckeln sker enligt beskrivningen i föregående stycke. $x$ $i$ $i$ $x$ $i+1$ $x$

Huvudfördelarna

I samtliga fall är den användbara användningen av sekundärt lagringsutrymme över 50 %. Med ökande minnesanvändning sker ingen minskning av kvaliteten på tjänsten.
Slumpmässig åtkomst till posten implementeras genom ett litet antal deloperationer (referenser till fysiska block).
I genomsnitt implementeras operationerna med att inkludera och ta bort poster ganska effektivt; samtidigt som nycklarnas naturliga ordning bibehålls för sekventiell bearbetning, såväl som lämplig balans i trädet för att säkerställa snabb slumpmässig provtagning.
Oföränderlig beställning efter nyckel möjliggör effektiv batchbearbetning.

Den största nackdelen med B-träd är att de inte har ett effektivt sätt att hämta data (det vill säga en trädgenomgångsmetod) beställd av en annan egenskap än den valda nyckeln.

Se även

Djup första sökning
Utöka första sökningen
Balanserade (självbalanserande) träd:

AVL-träd
matristräd
Perfekt balanserat träd
expanderande träd
B+-träd
2-3-träd
R-träd
B*-träd
Röd-svart träd

Lista över datastrukturer (träd)

Anteckningar

↑ Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Kapitel 18. B-träd // Algoritmer: Konstruktion och analys = Introduktion till algoritmer. - 2:a uppl. - M. : Williams , 2006. - S. 515-536. — ISBN 0-07-013151-1 .

Litteratur

Levitin A. V. Kapitel 7. Rum-tid kompromiss: B-träd // Algoritmer. Introduktion till utveckling och analys - M . : Williams , 2006. - S. 331-339. — 576 sid. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Kapitel 18. B-träd // Algoritmer: Konstruktion och analys = Introduktion till algoritmer. - 2:a uppl. - M. : Williams , 2006. - S. 515-536. — ISBN 0-07-013151-1 .

Länkar

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