B-puu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 24. helmikuuta 2015 tarkistetusta versiosta . tarkastukset vaativat 46 muokkausta .

B-puu (äännetään venäjäksi B-puuksi ) on tietorakenne , hakupuu. Ulkoisen loogisen esityksen näkökulmasta tasapainoinen , voimakkaasti haarautunut puu . Käytetään usein tietojen tallentamiseen ulkoiseen muistiin.

R. Bayer ja E. McCreight ehdottivat ensimmäisen kerran B-puiden käyttöä vuonna 1970 .

Tasapainotettu tarkoittaa, että minkä tahansa kahden polun pituudet juuresta lehtiin eroavat enintään yhden.

Puun haarautuminen on jokaisen puusolmun ominaisuus viitata suureen määrään jälkeläisiä solmuja.

Fyysisen organisoinnin näkökulmasta B-puu on esitetty muistisivujen multilist-rakenteena, eli jokainen puun solmu vastaa muistilohkoa (sivua). Sisä- ja lehtisivuilla on yleensä erilainen rakenne.

Sovellus

B-puurakennetta käytetään indeksien järjestämiseen monissa nykyaikaisissa DBMS -järjestelmissä .

B-puuta voidaan käyttää kiintolevyllä olevien tietojen (yleensä metatietojen) jäsentämiseen (indeksointiin). Kiintolevyn mielivaltaisen lohkon käyttöaika on erittäin pitkä (millisekuntien luokkaa), koska sen määrää levyn pyörimisnopeus ja pään liike. Siksi on tärkeää vähentää kunkin toiminnon yhteydessä skannattujen solmujen määrää. Listahaun käyttäminen joka kerta satunnaisen lohkon löytämiseksi voi johtaa liialliseen määrään levyhakuja johtuen tarpeesta käydä läpi kaikki sen elementit, jotka edeltävät tiettyä lohkoa, kun taas haku B-puussa, johtuen tasapaino ja korkea haarautuminen, voivat merkittävästi vähentää tällaisten toimintojen määrää.

Algoritmien suhteellisen yksinkertainen toteutus ja valmiiden kirjastojen (mukaan lukien C :n) olemassaolo B-puurakenteen kanssa työskentelyä varten tekevät tällaisesta muistijärjestelystä suositun monissa ohjelmissa, jotka toimivat suurilla tietomäärillä.

Rakenne ja rakentamisen periaatteet

B-puu on puu, joka täyttää seuraavat ominaisuudet:

Kunkin solmun avaimet tilataan yleensä helpon pääsyn vuoksi. Juuri sisältää 1 - 2t-1 avaimia. Mikä tahansa muu solmu sisältää avaimia t-1 - 2t-1. Lehdet eivät ole poikkeus tästä säännöstä. Tässä t on puuparametri, joka on vähintään 2 (ja ottaa yleensä arvot välillä 50 - 2000 [1] ).
Lehdillä ei ole jälkeläisiä. Kaikki muut avaimet , …, , sisältävät solmut sisältävät lapsia. Jossa $K_1$ $K_n$ $n+1$
1. Ensimmäinen lapsi ja kaikki sen lapset sisältävät avaimet väliltä $(-\infty, K_1)$
2. Sillä , i. lapsi ja kaikki sen lapset sisältävät avaimia väliltä $2\le i\le n$ $(K_{i-1}, K_i)$
3. $(n+1)$ -th lapsi ja kaikki sen lapset sisältävät avaimet väliltä $(K_n,\infty)$
Kaikkien lehtien syvyys on sama.

Ominaisuus 2 voidaan ilmaista eri tavalla: B-puun jokaista solmua lehtiä lukuun ottamatta voidaan pitää järjestettynä listana, jossa avaimet ja osoittimet vuorottelevat lapsiin.

Hae

Jos avain sisältyy juureen, se löytyy. Muussa tapauksessa määritämme välin ja siirrymme vastaavaan jälkeläiseen. Toistamme.

Avaimen lisääminen

Kutsumme tietyn solmun jälkeläisten puuta alipuuksi, joka koostuu tästä solmusta ja sen jälkeläisistä.

Ensin määritellään funktio, joka lisää avaimen K solmun x lapsipuuhun. Toiminnon suorittamisen jälkeen kaikissa hyväksytyissä solmuissa, paitsi ehkä itse solmussa x , avaimet ovat pienempiä kuin , mutta ei pienempiä kuin . $2t-1$ $t-1$

Jos x ei ole lehti,
1. Määritetään väli, jossa K tulee olla. Olkoon y vastaava lapsi.
2. Lisää K rekursiivisesti y:n jälkeläiseen puuhun.
3. Jos solmu y on täynnä, eli se sisältää avaimia, jaamme sen kahteen osaan. Solmu vastaanottaa ensimmäisen y-avaimesta ja ensimmäisen lapsistaan, ja solmu vastaanottaa viimeisen y-avaimesta ja viimeisen lapsistaan. Solmun y avainten mediaani menee solmuun x, ja osoitin y:hen solmussa x korvataan osoittimilla solmuihin ja . $2t-1$ $y_1$ $t-1$ $t$ $y_2$ $t-1$ $t$ $y_1$ $y_2$
Jos x on lehti, lisää vain avain K siihen.

Nyt määritellään avaimen K lisääminen koko puuhun. Kirjain R tarkoittaa juurisolmua.

Lisää K R:n jälkeläiseen puuhun.
Jos R sisältää nyt avaimia, jaa se kahteen osaan. Solmu vastaanottaa ensimmäisen R-avaimesta ja ensimmäisen lapsistaan, ja solmu vastaanottaa viimeisen R-avaimesta ja viimeisen lapsistaan. Solmun R avainten mediaani osuu juuri luotuun solmuun, josta tulee juurisolmu. Solmuista tulee sen lapsia . $2t-1$ $R_{1}$ $t-1$ $t$ $R_{2}$ $t-1$ $t$ $R_{1}$ $R_{2}$

Avaimen poistaminen

Jos juuri on myös lehti, eli puussa on vain yksi solmu, poistamme yksinkertaisesti avaimen tästä solmusta. Muussa tapauksessa löydämme ensin avaimen sisältävän solmun, muistaen polun siihen. Olkoon tämä solmu . $x$

Jos - lehti, poista avain sieltä. Jos solmussa on jäljellä ainakin avaimia , pysähdymme siihen. Muussa tapauksessa tarkastelemme avainten määrää kahdessa viereisessä sisarussolmussa. Jos naapurissa on oikea naapurisolmu ja sillä on vähintään avaimet, lisäämme sen ja viereisen oikean solmun väliseen erotinavaimeen ja tämän avaimen tilalle laitamme viereisen oikean solmun ensimmäisen avaimen, jonka jälkeen lopetamme . Jos näin ei ole, mutta naapurissa on vasen solmu ja siinä on vähintään avaimet, lisäämme sen ja viereisen vasemman solmun väliseen erotinavaimeen ja tämän avaimen tilalle laitamme naapurisolmun viimeisen avaimen. vasen solmu, jonka jälkeen pysähdymme. Lopuksi, jos vasen avain epäonnistuu, yhdistämme solmun viereiseen vasempaan tai oikeaan solmuun ja siirrämme nämä kaksi solmua aiemmin erottaneen avaimen yhdistettyyn solmuun. Tässä tapauksessa vain avaimet voivat jäädä pääsolmuun . Sitten, jos se ei ole juuri, suoritamme samanlaisen toimenpiteen sen kanssa. Jos tämän seurauksena olemme päässeet juureen ja siinä on 1 - avaimia jäljellä, mitään ei tarvitse tehdä, koska juurilla voi olla vähemmän avaimia. Jos juuressa ei ole jäljellä yhtään avainta, jätetään juurisolmu pois ja tehdään sen ainoa lapsi puun uudeksi juureksi. $x$ $x$ $t-1$ $t$ $x$ $t$ $x$ $x$ $t-2$ $t-1$ $t-1$

Jos ei ole lehti ja K on sen -:s avain, poista oikeanpuoleisin avain -:nnen jälkeläisen jälkeläisten alipuusta , tai päinvastoin, vasemmanpuoleisin avain -:nnen jälkeläisen jälkeläisten alipuusta . Tämän jälkeen korvaamme avaimen K kauko-avaimella. Avaimen poistaminen tapahtuu edellisessä kappaleessa kuvatulla tavalla. $x$ $i$ $i$ $x$ $i+1$ $x$

Tärkeimmät edut

Toissijaisen säilytystilan hyödyllinen käyttöaste on kaikissa tapauksissa yli 50 %. Muistin käytön lisääntyessä palvelun laatu ei heikkene.
Satunnaispääsy tietueeseen toteutetaan pienellä määrällä alioperaatioita (viittaukset fyysisiin lohkoihin).
Keskimäärin tietueiden sisällyttäminen ja poistaminen on toteutettu varsin tehokkaasti; säilyttäen samalla avainten luonnollisen järjestyksen peräkkäistä käsittelyä varten sekä puun sopivan tasapainon nopean satunnaisnäytteenoton varmistamiseksi.
Muuttumaton avaimella tilaus mahdollistaa tehokkaan eräkäsittelyn.

B-puiden suurin haittapuoli on, että niillä ei ole tehokasta tapaa hakea dataa (eli puun läpikulkumenetelmää), joka on järjestetty muun ominaisuuden kuin valitun avaimen mukaan.

Katso myös

Ensimmäinen syvyyshaku
Leveys ensimmäinen haku
Tasapainotetut (itsetasapainottavat) puut:

AVL puu
matriisipuu
Täysin tasapainoinen puu
laajeneva puu
B+-puut
2-3-puu
R-puu
B*-puu
Puna-musta puu

Luettelo tietorakenteista (puista)

Muistiinpanot

↑ Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Luku 18. B-Trees // Algoritmit: rakentaminen ja analyysi = Algoritmien johdatus. - 2. painos - M .: Williams , 2006. - S. 515-536. — ISBN 0-07-013151-1 .

Kirjallisuus

Levitin A. V. Luku 7. Avaruus-aikakompromissi: B-puut // Algoritmit. Johdatus kehitykseen ja analyysiin - 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. Luku 18. B-Trees // Algoritmit: rakentaminen ja analyysi = Algoritmien johdatus. - 2. painos - M .: Williams , 2006. - S. 515-536. — ISBN 0-07-013151-1 .

Linkit

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