B⁺-puu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 7. helmikuuta 2022 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

B⁺-puu on tietorakenne, joka perustuu B-puuhun , tasapainoiseen hakupuuhun, jossa on muuttuva, mutta usein suuri määrä lapsia solmua kohti. B⁺-puu koostuu juuresta, sisäsolmuista ja lehdistä, juuri voi olla joko lehti tai solmu, jossa on kaksi tai useampia lapsia. $n$

Alun perin rakenteen tarkoituksena oli tallentaa dataa tehokasta hakua varten lohkoorientoituneessa tallennusympäristössä - erityisesti tiedostojärjestelmille; Sovellus johtuu siitä, että toisin kuin binäärihakupuilla, B⁺-puilla on erittäin korkea haarautumiskerroin (osoittimien määrä yläsolmusta lapsiin on yleensä luokkaa 100 tai enemmän), mikä vähentää hakujen määrää. I/O-toiminnot, jotka vaativat elementin etsimisen puusta.

B⁺-puun muunnos, jossa kaikki arvot tallennettiin lehtisolmuihin, tarkistettiin systemaattisesti vuonna 1979 [1] , ja todettiin, että IBM on käyttänyt tällaisia rakenteita VSAM -päätietokoneen tiedostopääsyteknologiassa vuodesta lähtien . ainakin 1973.

Rakennetta käytetään laajalti tiedostojärjestelmissä - NTFS , ReiserFS , NSS , XFS , JFS , ReFS ja BFS käyttävät tämän tyyppistä puuta metatietojen indeksointiin; BeFS käyttää myös B⁺-puita hakemistojen tallentamiseen. Relaatiotietokannan hallintajärjestelmät , kuten DB2 , Informix , Microsoft SQL Server , Oracle Database (versiosta 8 alkaen), Adaptive Server Enterprise ja SQLite , tukevat tämän tyyppistä puuta taulukkohakemistoille. NoSQL -tietokantajärjestelmissä, jotka toimivat avainarvomallin kanssa, tietorakenne on toteutettu tietojen käyttöä varten CouchDB : ssä , MongoDB :ssä (käytettäessä WiredTiger - tallennusalijärjestelmää ) ja Tokyo Cabinetissa .

Kuvaus

B⁺-puu on tasapainoisen järjestyksen (tai asteen) hakupuu , joka täyttää seuraavat ominaisuudet: $n$ $t,$

Jokainen solmu sisältää vähintään yhden avaimen; kunkin solmun avaimet on järjestetty, juuri sisältää alkaen - avaimet, mikä tahansa muu solmu sisältää alkaen - avaimet; lehdet eivät ole poikkeus tästä säännöstä. Tässä on puuparametri, joka on vähintään 2 (ja tyypillisesti ottaa arvot välillä 50 - 2000 riippuen avaimen koosta suhteessa sivun kokoon, joka puolestaan määräytyy sisältömerkinnän koon mukaan). $yksi$ $2t-1$ ${\textstyle t-1}$ ${\textstyle 2t-1}$ ${\textstyle t}$
Lehdillä ei ole jälkeläisiä; kaikille muille avaimia sisältäville solmuille annettu solmu sisältää lapsia. Jossa: $K_{1},\dots ,K_{n},$ $(n+1)$
- ensimmäinen lapsi ja kaikki sen lapset sisältävät avaimia väliltä $(-\infty ,K_{1});$
- sillä -. lapsi ja kaikki sen lapset sisältävät avaimia väliltä $2 \leqslant i \leqslant n$ $i$ $(K_{i-1},K_{i});$
- $(n+1)$ -th lapsi ja kaikki sen lapset sisältävät avaimet väliltä $(K_{n},\infty ).$
Kaikkien lehtien syvyys on sama.
Lehdissä on linkki naapuriin, jonka avulla voit nopeasti kulkea puun läpi avainten nousevassa järjestyksessä, ja linkit tietoihin.

Rakennus

B⁺-puun rakentaminen voi vaatia välirakenteen uudelleenrakentamista, tämä johtuu siitä, että avainten lukumäärän jokaisessa solmussa (juurta lukuun ottamatta) tulee olla mistä on puun aste (tai järjestys). Kun yrität lisätä ( )- avaimen solmuun, on välttämätöntä erottaa tämä solmu; ( )-avain, joka on sijoitettu puun viereiselle tasolle, toimii muodostettujen oksien erotinavaimena. . Erikoistapaus on juuren jako, koska tässä tapauksessa puun tasojen lukumäärä kasvaa. B⁺-puun lehden halkaisemisen ominaisuus on, että se jaetaan epätasaisiin osiin. Sisäisen solmun tai juuren jakaminen johtaa solmuihin, joissa on sama määrä avaimia . Lehden halkaisu voi aiheuttaa "ketjureaktion" solmujen halkaisemisesta, joka päättyy juureen. $t$ $2t,$ $t$ $2t+1$ ${\textstyle t+1}$ $k.$

Rakenteen ominaisuudet

B⁺-puussa ohjelman riippumattomuus tietotietueen rakenteesta on helppo toteuttaa.
Haku päättyy välttämättä arkkiin.
Avaimen poistamisella on se etu, että poisto tapahtuu aina arkilta.
Muut toiminnot suoritetaan samalla tavalla kuin B-puilla.
B⁺-puut vaativat enemmän muistia edustaakseen kuin klassiset B-puut.
B⁺-puilla on mahdollisuus käyttää avaimia peräkkäin.

Rakenteen perustoiminnot

Hae

B⁺-puun juuri on lähtökohta koko arvoalueelle, jossa jokainen sisäinen solmu on osaväli.

Oletetaan esimerkiksi, että meidän on löydettävä avaimen arvo B⁺-puusta. Tätä varten etsimme lehtisolmua, joka sisältää arvon Jokaisessa sisäisessä solmussa meidän on selvitettävä, mitä seuraavaa lapsisolmua seurataan, B⁺-puun sisäisellä solmulla on enintään lapsia, joissa jokainen niistä edustaa erillinen osaväli. Sopiva solmu valitaan etsimällä solmun avainarvoista: $k$ $k.$ $t$

Funktio : search ( k ) return tree_search ( k , juuri ); Funktio : tree_search ( k , solmu ) jos solmu on lehti , palauttaa solmun ; _ vaihtaa k tee tapaus k < k [ 0 ] palauttaa puuhaku ( k , p [ 0 ]); tapaus k [ i ] ≤ k < k [ i + 1 ] palauttaa puuhaku ( k , p [ i + 1 ]); tapaus k [ d ] ≤ k palauttaa puuhaku ( k , p [ d + 1 ]);

(Tämä pseudokoodi olettaa, että kaksoiskappaleet jätetään huomioimatta.)

Lisätään

Jos haluat lisätä uuden avaimen tai uuden merkinnän, sinun on ensin löydettävä solmu, johon haluat lisätä ne. Tässä tapauksessa algoritmi on:

Jos solmu ei ole täysin täytetty (elementtien lukumäärä lisäyksen jälkeen on enintään ), lisää avain (tietue). $2t-1,$
Muussa tapauksessa sinun on jaettava solmu:
- luo uusi solmu ja siirrä sitten puolet elementeistä nykyisestä uuteen;
- lisää uuden solmun pienin avain ja sen osoite (solmu) emoryhmään;
- jos yläsolmu on täynnä, jaa se samalla tavalla:
  - lisää keskimmäinen avain pääsolmuun;
- toista, kunnes pääsolmu on jaettava.
Jos juuri hajoaa, luo uusi juuri yhdellä avaimella ja kahdella osoittimella (juureen lisätty avain poistetaan sen solmusta)

B-puut, toisin kuin B⁺-puut, laajenevat juurien puolelta, eivät lehtiä.

Poisto

Avaimen tai merkinnän poistamiseksi sinun on ensin löydettävä lehtisolmu, jossa se sijaitsee. Algoritmi lehden solmusta poistamiseksi:

Jos solmu on vähintään puoliksi täynnä, algoritmi päättyy;
Jos solmussa on vähemmän elementtejä, niin:
- yritä jakaa elementtejä uudelleen, eli lisätä elementti "veljestä" solmuun - elementti, jolla on yhteinen esi-isä.
- jos uudelleenjako epäonnistuu, yhdistä solmu "veljeen".
Jos yhdistäminen tapahtuu, poista avain tai merkintä, joka osoittaa etäsolmuun tai sen "sisarukseen" pääsolmusta.

Liitos voi ulottua juureen asti, jolloin puun korkeus pienenee.

Operaatioiden laskennallinen monimutkaisuus

Kunkin operaation laskennallinen monimutkaisuus pahimmassa tapauksessa: missä on puun järjestys tai haaroitustekijä; on elementtien lukumäärä puussa oksien solmuissa. $O(\log {\frac {t}{2n)))$ $t$ $n$

Muistiinpanot

↑ Douglas Comer. Ubiquitous B-Tree // ACM Computing Surveys. - 1979. - Kesäkuu ( osa 11 , nro 2 ) . - s. 121-137 . — ISSN 0360-0300 . Arkistoitu alkuperäisestä 17. marraskuuta 2015.

Kirjallisuus

Zubov V. S., Shevchenko I. V. Luku 6. Haku ei-binääripuista - B-puut // Tietojenkäsittelyn rakenteet ja menetelmät. Workshop Delphi-ympäristössä. - Filin, 2004. - S. 144-164. — ISBN 5-9216-0053-9 .
Donald Knuth . 4. Kaikkien puiden sukupolvi. Kombinatorisen sukupolven historia // Ohjelmoinnin taito = The Art of Computer Programming. - M. : "Williams" , 2007. - V. 4. - S. 160. - ISBN 0-321-33570-8 .

Linkit

B⁺ Tree Visualizer - B+ Tree Visualization

Puu (tietorakenne)
Binäärihakupuu Puu (graafiteoria) puun rakenne
Binääripuut	binäärinen puu T-puu
Itsetasapainottavat binaaripuut	AA puu AVL puu Puna-musta puu Splay-puu puu sakkoilla karteesinen puu Fibonacci puu B-puu T-puu
B-puut	2-3-puu B⁺-puu B*-puu B x -puu UB puu 2-3-4 puu (a,b)-puu tanssiva puu
etuliite puita	suffiksi puu Pakattu etuliitepuu Kolmiosainen hakupuu
Avaruuden binaarinen osiointi	k-ulotteinen puu VP-puu
Ei-binääripuut	Quadtree oktreen Harva Voxel Octree eksponentiaalinen puu PQ puu
Avaruuden hajottaminen	R-puu Hilbert R-puu R+-puu R*-puu X-puu M-puu Fenwick puu Segmenttipuu
Muut puut	pino hash puu sormipuu metrinen puu Päällystyspuu BK-puu Kaksiketjuinen puu iDistance Linkistä leikattu puu LSM puu
Algoritmit	Leveys ensimmäinen haku Ensimmäinen syvyyshaku DSW-algoritmi kattava puu protokolla