B-fa

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2015. február 24-én felülvizsgált verziótól ; az ellenőrzések 46 szerkesztést igényelnek .

A B-fa (oroszul B-faként ejtve ) egy adatstruktúra , egy keresőfa. A külső logikai reprezentáció szempontjából kiegyensúlyozott , erősen elágazó fa . Gyakran használják adatok külső memóriában való tárolására.

A B-fák használatát először R. Bayer és E. McCreight javasolta 1970 - ben .

A kiegyensúlyozott azt jelenti, hogy a gyökértől a levelekig tartó bármely két út hossza legfeljebb eggyel különbözik.

A fa elágazása az egyes facsomópontok azon tulajdonsága, hogy nagyszámú leszármazott csomópontra hivatkozzon.

A fizikai szervezés szempontjából a B-fa memóriaoldalak többlistás struktúrájaként jelenik meg, vagyis a fa minden csomópontja egy memóriablokknak (oldalnak) felel meg. A belső és a levéloldalak általában eltérő szerkezetűek.

Alkalmazás

A B-fa struktúrát számos modern DBMS -ben használják indexek rendezésére .

A B-fa felhasználható a merevlemezen lévő információk (általában metaadatok) strukturálására (indexelésére). A merevlemezen lévő tetszőleges blokkhoz való hozzáférési idő nagyon hosszú (ezredmásodperc nagyságrendű), mivel azt a lemez forgási sebessége és a fej mozgása határozza meg. Ezért fontos csökkenteni az egyes műveleteknél vizsgált csomópontok számát. A listakeresés minden alkalommal egy véletlenszerű blokk megtalálására túl sok lemezelérést eredményezhet, mivel az adott elemet megelőző összes elemén egymás után kell áthaladni, míg a B-fában történő keresés a blokk tulajdonságai miatt. egyensúly és magas elágazás, jelentősen csökkentheti az ilyen műveletek számát.

Az algoritmusok viszonylag egyszerű megvalósítása és a B-fa struktúrával való munkavégzéshez kész könyvtárak (beleértve a C - hez tartozókat is) népszerűvé teszik az ilyen memóriaszervezést a sokféle, nagy adatmennyiséggel dolgozó programban.

Felépítés és építési elvek

A B-fa olyan fa, amely megfelel a következő tulajdonságoknak:

Az egyes csomópontok kulcsait általában a könnyű hozzáférés érdekében rendelik. A gyökér 1 és 2t-1 közötti kulcsokat tartalmaz. Minden más csomópont t-1 és 2t-1 közötti kulcsokat tartalmaz. A levelek sem kivételek e szabály alól. Itt t egy faparaméter, amely legalább 2 (és általában 50 és 2000 közötti értékeket vesz fel [1] ).
A leveleknek nincs utóda. Minden más csomópont, amely , …, , kulcsokat tartalmaz, gyermekeket tartalmaz. Ahol $K_1$ $K_n$ $n+1$
1. Az első gyermek és az összes gyermeke tartalmazza az intervallum kulcsait $(-\infty, K_1)$
2. Az i-edik gyermek és minden gyermeke az intervallum kulcsait tartalmazza $2\le i\le n$ $(K_{i-1}, K_i)$
3. $(n+1)$ -th gyermek és minden gyermeke tartalmaz kulcsokat az intervallumból $(K_n,\infty)$
Minden levél mélysége azonos.

A 2. tulajdonság másként is megfogalmazható: a B-fa minden csomópontja a levelek kivételével rendezett listának tekinthető, amelyben a kulcsok és a gyermekekre mutató mutatók váltakoznak.

Keresés

Ha a kulcs a gyökérben található, akkor a rendszer megtalálja. Ellenkező esetben meghatározzuk az intervallumot, és a megfelelő leszármazotthoz lépünk. Ismételjük.

Kulcs hozzáadása

Egy bizonyos csomópont leszármazottainak fáját egy részfának nevezzük , amely ebből a csomópontból és leszármazottaiból áll.

Először is definiáljunk egy függvényt, amely hozzáadja a K kulcsot az x csomópont gyermekfájához. A függvény végrehajtása után az összes átadott csomópontban, kivéve talán magát az x csomópontot, kevesebb, mint , de nem kevesebb kulcs lesz. $2t-1$ $t-1$

Ha x nem levél,
1. Meghatározzuk azt az intervallumot, ahol K legyen. Legyen y a megfelelő gyermek.
2. Adja hozzá rekurzív módon K-t y leszármazott fájához.
3. Ha az y csomópont megtelt, azaz kulcsokat tartalmaz, akkor kettéosztjuk. A csomópont megkapja az y kulcsok közül az elsőt és a gyermekei közül az elsőt, a csomópont pedig az utolsó y kulcsot és a gyermekei közül az utolsót. Az y csomópont kulcsainak mediánja az x csomópontba kerül, és az x csomópontban az y-ra mutató mutatót felváltják a csomópontokra mutató mutatók és . $2t-1$ $y_1$ $t-1$ $t$ $y_2$ $t-1$ $t$ $y_1$ $y_2$
Ha x egy levél, csak adja hozzá a K kulcsot.

Most határozzuk meg a K kulcs hozzáadását a teljes fához. Az R betű a gyökércsomópontot jelöli.

Adja hozzá K-t R leszármazott fájához.
Ha R most kulcsokat tartalmaz, oszd ketté. A csomópont megkapja az R kulcsok közül az elsőt és a gyermekei közül az elsőt, a csomópont pedig az R kulcsok közül az utolsót és a gyermekei közül az utolsót. Az R csomópont kulcsainak mediánja az újonnan létrehozott csomópontba esik, amely a gyökércsomóponttá válik. A csomópontok gyermekeivé válnak . $2t-1$ $R_{1}$ $t-1$ $t$ $R_{2}$ $t-1$ $t$ $R_{1}$ $R_{2}$

Kulcs eltávolítása

Ha a gyökér egyben levél is, vagyis csak egy csomópont van a fában, egyszerűen eltávolítjuk a kulcsot ebből a csomópontból. Ellenkező esetben először megkeressük a kulcsot tartalmazó csomópontot, emlékezve a hozzá vezető útvonalra. Legyen ez a csomópont . $x$

Ha - levél, törölje onnan a kulcsot. Ha legalább kulcsok maradtak a csomópontban , akkor itt megállunk. Ellenkező esetben a kulcsok számát nézzük két szomszédos testvércsomópontban. Ha van egy szomszédos jobb csomópont, és van legalább kulcsa, akkor a közte és a szomszédos jobb csomópont közötti elválasztó kulcshoz hozzáadjuk , és e kulcs helyére a szomszédos jobb csomópont első kulcsát tesszük, ami után megállunk. . Ha ez nem így van, de van egy szomszédos bal csomópont, és legalább kulcsai vannak, akkor a közte és a szomszédos bal csomópont közötti elválasztó kulcshoz hozzáadjuk , és e kulcs helyére a szomszédos bal csomópont utolsó kulcsát tesszük. bal csomópont, ami után megállunk. Végül, ha a bal oldali kulcs meghibásodik, egyesítjük a csomópontot a szomszédos bal vagy jobb csomóponttal, és áthelyezzük a két csomópontot korábban elválasztó kulcsot az egyesített csomópontba. Ebben az esetben csak a kulcsok maradhatnak a szülőcsomópontban . Majd ha nem gyökér, akkor hasonló eljárást végzünk vele. Ha ennek eredményeként elértük a root-ot, és 1-től kulcsig maradt benne, akkor nem kell semmit tenni, mert előfordulhat, hogy a gyökérnek kevesebb kulcsa van. Ha a gyökérben egyetlen kulcs sem maradt, akkor a gyökércsomópontot kizárjuk, és annak egyetlen gyermekét tesszük a fa új gyökerévé. $x$ $x$ $t-1$ $t$ $x$ $t$ $x$ $x$ $t-2$ $t-1$ $t-1$

Ha nem levél, és K a -edik kulcsa, törölje a -. leszármazott utódok részfájából a jobb szélső kulcsot , vagy fordítva, a -edik leszármazott utódok részfájából a bal szélső kulcsot . Ezt követően a K kulcsot cseréljük ki a távvezérlőre. A kulcs törlése az előző bekezdésben leírtak szerint történik. $x$ $én$ $én$ $x$ $i+1$ $x$

Fő előnyei

A másodlagos tárhely hasznos kihasználása minden esetben 50% feletti. A memóriahasználat növekedésével nem csökken a szolgáltatás minősége.
A rekordhoz való véletlenszerű hozzáférést kis számú alműveleten keresztül valósítják meg (hivatkozások fizikai blokkra).
A rekordok felvételének és törlésének műveletei átlagosan meglehetősen hatékonyan valósulnak meg; a szekvenciális feldolgozáshoz szükséges kulcsok természetes sorrendjének megőrzése, valamint a fa megfelelő egyensúlyának megőrzése a gyors véletlenszerű mintavétel érdekében.
A változatlan kulcsos rendelés hatékony kötegelt feldolgozást tesz lehetővé.

A B-fák fő hátránya, hogy nem rendelkeznek hatékony eszközzel a kiválasztott kulcstól eltérő tulajdonság által rendezett adatok lekérésére (vagyis fa bejárási módszerrel).

Lásd még

Mélységi első keresés
Szélesség első keresés
Kiegyensúlyozott (önkiegyensúlyozó) fák:

AVL fa
mátrix fa
Tökéletesen kiegyensúlyozott fa
bővülő fa
B+-fák
2-3-fa
R-fa
B*-fa
Vörös-fekete fa

Adatstruktúrák listája (fák)

Jegyzetek

↑ Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. 18. fejezet B-fák // Algoritmusok: szerkesztés és elemzés = Bevezetés az algoritmusokba. - 2. kiadás - M .: Williams , 2006. - S. 515-536. — ISBN 0-07-013151-1 .

Irodalom

Levitin A. V. 7. fejezet Tér-idő kompromisszum: B-fák // Algoritmusok. Bevezetés a fejlesztésbe és elemzésbe - M . : Williams , 2006. - S. 331-339. — 576 p. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. 18. fejezet B-fák // Algoritmusok: szerkesztés és elemzés = Bevezetés az algoritmusokba. - 2. kiadás - M .: Williams , 2006. - S. 515-536. — ISBN 0-07-013151-1 .

Linkek

Fa (adatstruktúra)
Bináris keresőfa Fa (gráfelmélet) fa szerkezet
Bináris fák	bináris fa T-fa
Önkiegyensúlyozó bináris fák	AA fa AVL fa Vörös-fekete fa Splay fa fa bírságokkal karteziánus fa Fibonacci fa B-fa T-fa
B-fák	2-3-fa B⁺-fa B*-fa B x -fa UB fa 2-3-4 fa (a,b)-fa táncoló fa
előtag fák	utótag fa Tömörített előtag fa hármas keresőfa
A tér bináris particionálása	k-dimenziós fa VP fa
Nem bináris fák	Quadtree oktfa Ritka Voxel Octree exponenciális fa PQ fa
A tér felosztása	R-fa Hilbert R-fa R+-fa R*-fa X-fa M-fa Fenwick fa Szegmens fa
Más fák	halom hash fa ujjfa metrikus fa Bevonat fa BK-fa Kétláncú fa iDistance Link-vágott fa LSM fa
Algoritmusok	Szélesség első keresés Mélységi első keresés DSW algoritmus átívelő fa protokoll