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 24. februar 2015; checks kræver 46 redigeringer .

B-træ (udtales på russisk som B-træ ) er en datastruktur , et søgetræ. Fra den ydre logiske repræsentations synspunkt - et afbalanceret , stærkt forgrenet træ . Bruges ofte til at gemme data i ekstern hukommelse.

Brugen af B-træer blev først foreslået af R. Bayer og E. McCreight i 1970 .

Balanceret betyder, at længden af to vilkårlige stier fra roden til bladene ikke afviger mere end én.

Forgrening af et træ er egenskaben for hver træknude til at referere til et stort antal efterkommerknuder.

Fra et fysisk organiseringssynspunkt er B-træet repræsenteret som en multilistestruktur af hukommelsessider, det vil sige, at hver knude i træet svarer til en hukommelsesblok (side). Inder- og bladsider har normalt en anden struktur.

Ansøgning

B-træstrukturen bruges til at organisere indekser i mange moderne DBMS'er .

Et B-træ kan bruges til at strukturere (indeksere) information på en harddisk (normalt metadata). Adgangstiden til en vilkårlig blok på en harddisk er meget lang (i størrelsesordenen millisekunder), da den bestemmes af diskens rotationshastighed og hovedbevægelsen. Derfor er det vigtigt at reducere antallet af noder, der scannes ved hver operation. Brug af en listesøgning hver gang for at finde en tilfældig blok kunne føre til et for stort antal diskadgange på grund af behovet for sekventielt at passere gennem alle dens elementer forud for den givne blok, mens søgningen i B-træet på grund af egenskaberne ved balance og høj forgrening, kan reducere antallet af sådanne operationer betydeligt.

Den relativt enkle implementering af algoritmer og eksistensen af færdige biblioteker (inklusive dem til C ) til at arbejde med B-træstrukturen gør en sådan hukommelsesorganisation populær i en lang række programmer, der arbejder med store mængder data.

Struktur og principper for konstruktion

Et B-træ er et træ, der opfylder følgende egenskaber:

Nøglerne i hver node er normalt bestilt for nem adgang. Roden indeholder fra 1 til 2t-1 nøgler. Enhver anden node indeholder fra t-1 til 2t-1 nøgler. Blade er ingen undtagelse fra denne regel. Her er t en træparameter, der er mindst 2 (og normalt tager værdier fra 50 til 2000 [1] ).
Blade har ingen afkom. Enhver anden node, der indeholder nøgler , …, , indeholder børn. Hvori $K_1$ $K_n$ $n+1$
1. Det første barn og alle dets børn indeholder nøgler fra intervallet $(-\infty, K_1)$
2. For , det i-te barn og alle dets børn indeholder nøgler fra intervallet $2\le i\le n$ $(K_{i-1}, K_i)$
3. $(n+1)$ -th barn og alle dets børn indeholder nøgler fra intervallet $(K_n,\infty)$
Dybden af alle blade er den samme.

Egenskab 2 kan angives forskelligt: Hver knude på B-træet, bortset fra blade, kan betragtes som en ordnet liste, hvor nøgler og pejlemærker til børn veksler.

Søg

Hvis nøglen er indeholdt i roden, findes den. Ellers bestemmer vi intervallet og går til den tilsvarende efterkommer. Vi gentager.

Tilføjelse af en nøgle

Vi vil kalde træet af efterkommere af en bestemt node for et undertræ, der består af denne node og dens efterkommere.

Lad os først definere en funktion, der tilføjer nøglen K til det underordnede træ for node x. Efter udførelse af funktionen vil der i alle beståede noder, undtagen måske selve noden x, være færre end , men ikke mindre end , nøgler. $2t-1$ $t-1$

Hvis x ikke er et blad,
1. Vi bestemmer intervallet hvor K skal være Lad y være det tilsvarende barn.
2. Tilføj rekursivt K til y's efterkommertræ.
3. Hvis noden y er fuld, dvs. den indeholder nøgler, deler vi den i to. Noden modtager den første af y-nøglerne og den første af sine børn, og noden modtager den sidste af y-nøglerne og den sidste af sine børn. Medianen af nøglerne til node y går til node x, og markøren til y ved node x erstattes af pointere til noder og . $2t-1$ $y_1$ $t-1$ $t$ $y_2$ $t-1$ $t$ $y_1$ $y_2$
Hvis x er et blad, skal du blot tilføje nøglen K der.

Lad os nu definere tilføjelse af nøglen K til hele træet. Bogstavet R står for rodnoden.

Tilføj K til R's efterkommertræ.
Hvis R nu indeholder nøgler, opdel den i to. Noden modtager den første af R-nøglerne og den første af dens børn, og noden modtager den sidste af R-nøglerne og den sidste af dens børn. Medianen af nøglerne til node R falder ind i den nyoprettede node, som bliver rodknuden. Noderne bliver dens børn . $2t-1$ $R_{1}$ $t-1$ $t$ $R_{2}$ $t-1$ $t$ $R_{1}$ $R_{2}$

Fjernelse af en nøgle

Hvis roden også er et blad, det vil sige, at der kun er en knude i træet, fjerner vi simpelthen nøglen fra denne knude. Ellers finder vi først noden, der indeholder nøglen, og husker stien til den. Lad denne node være . $x$

Hvis - blad, slet nøglen derfra. Hvis der i det mindste er nøgler tilbage i noden , stopper vi der. Ellers ser vi på antallet af nøgler i to nabosøskendenoder. Hvis der er en tilstødende højre node, og den har mindst nøgler, tilføjer vi til separatornøglen mellem den og den tilstødende højre node, og i stedet for denne nøgle sætter vi den første nøgle af den tilstødende højre node, hvorefter vi stopper . Hvis dette ikke er tilfældet, men der er en tilstødende venstre node, og den har mindst nøgler, tilføjer vi separatornøglen mellem den og den tilstødende venstre node, og i stedet for denne nøgle sætter vi den sidste nøgle af naboen venstre knude, hvorefter vi stopper. Til sidst, hvis den venstre tast fejler, slår vi knudepunktet sammen med den tilstødende venstre eller højre knude, og flytter den nøgle, der tidligere adskilte disse to knudepunkter, ind i den fusionerede knude. I dette tilfælde kan kun nøgler forblive i den overordnede node . Så, hvis det ikke er en rod, udfører vi en lignende procedure med den. Hvis vi som følge heraf har nået roden, og der er fra 1 til nøgler tilbage i den, skal der ikke gøres noget, for roden kan have færre nøgler. Hvis der ikke er en eneste nøgle tilbage i roden, udelukker vi rodnoden og gør dens eneste underordnede til træets nye rod. $x$ $x$ $t-1$ $t$ $x$ $t$ $x$ $x$ $t-2$ $t-1$ $t-1$

Hvis ikke er et blad, og K er dets -te nøgle, skal du slette nøglen længst til højre fra efterkommerundertræet i -te efterkommer eller omvendt nøglen længst til venstre fra efterkommerundertræet i -te efterkommer . Derefter erstatter vi nøglen K med fjernbetjeningen. Sletningen af nøglen sker som beskrevet i det foregående afsnit. $x$ $jeg$ $jeg$ $x$ $i+1$ $x$

Vigtigste fordele

I alle tilfælde er den nyttige udnyttelse af sekundær lagerplads over 50 %. Med stigende hukommelsesudnyttelse er der intet fald i servicekvalitet.
Random adgang til posten implementeres gennem et lille antal underoperationer (referencer til fysiske blokke).
I gennemsnit er operationerne med at inkludere og slette poster implementeret ganske effektivt; samtidig med at den naturlige rækkefølge af nøglerne til sekventiel behandling bevares, samt den passende balance i træet for at sikre hurtig tilfældig prøveudtagning.
Uforanderlig bestilling efter nøgle muliggør effektiv batchbehandling.

Den største ulempe ved B-træer er, at de ikke har et effektivt middel til at hente data (det vil sige en trægennemløbsmetode) bestilt af en anden egenskab end den valgte nøgle.

Se også

Dybde første søgning
Bredde først søgning
Balancerede (selvbalancerende) træer:

AVL træ
matrix træ
Perfekt afbalanceret træ
ekspanderende træ
B+-træer
2-3-træ
R-træ
B*-træ
Rød-sort træ

Liste over datastrukturer (træer)

Noter

↑ Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Kapitel 18. B-træer // Algoritmer: Konstruktion og analyse = Introduktion til algoritmer. - 2. udg. - M. : Williams , 2006. - S. 515-536. — ISBN 0-07-013151-1 .

Litteratur

Levitin A. V. Kapitel 7. Rum-tid kompromis: B-træer // Algoritmer. Introduktion til udvikling og analyse - M . : Williams , 2006. - S. 331-339. — 576 s. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Kapitel 18. B-træer // Algoritmer: Konstruktion og analyse = Introduktion til algoritmer. - 2. udg. - M. : Williams , 2006. - S. 515-536. — ISBN 0-07-013151-1 .

Links

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