B⁺-fa

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. február 7-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A B⁺-fa egy B-fán alapuló adatstruktúra , amely egy kiegyensúlyozott keresési fa változó, de csomópontonként gyakran nagy számú gyermekkel. A B⁺-fa egy gyökérből, belső csomópontokból és levelekből áll, a gyökér lehet levél vagy két vagy több gyermekes csomópont. $n$

Kezdetben a struktúra célja az volt, hogy a hatékony keresés érdekében adatokat tároljon blokkorientált tárolási környezetben – különösen fájlrendszerek esetében; Az alkalmazás annak köszönhető, hogy a bináris keresőfákkal ellentétben a B⁺-fák nagyon magas elágazási tényezővel rendelkeznek (a szülőcsomóponttól a gyerekek felé mutató mutatók száma általában 100 vagy több nagyságrendű), ami csökkenti a keresések számát. I / O műveletek, amelyek megkövetelik egy elem keresését a fában.

A B⁺-fa egy változatát, amelyben az összes értéket a levél csomópontjaiban tárolták, 1979-ben szisztematikusan felülvizsgálták [1] , megjegyezve, hogy ezeket a struktúrákat az IBM a VSAM nagyszámítógépes fájlelérési technológiájában óta használja. legalább 1973.

A struktúrát széles körben használják a fájlrendszerekben - az NTFS , ReiserFS , NSS , XFS , JFS , ReFS és BFS ezt a fát használja a metaadatok indexelésére; A BeFS B⁺-fákat is használ a könyvtárak tárolására. A relációs adatbázis-kezelő rendszerek , például a DB2 , Informix , Microsoft SQL Server , Oracle Database (8-as verziótól), Adaptive Server Enterprise és SQLite támogatják ezt a fajta fát a táblaindexekhez. A kulcsérték-modellel dolgozó NoSQL DBMS-ek közül az adatstruktúra a CouchDB -ben, a MongoDB - ben ( a WiredTiger tárolási alrendszer használatakor ) és a Tokyo Cabinetben valósult meg adathozzáféréshez .

Leírás

A B⁺-fa egy kiegyensúlyozott sorrendű (vagy fokszámú) keresési fa , amely megfelel a következő tulajdonságoknak: $n$ $t,$

Minden csomópont legalább egy kulcsot tartalmaz; az egyes csomópontokban a kulcsok sorrendben vannak, a gyökér tól -ig kulcsokat, minden más csomópont -tól -ig kulcsokat tartalmaz; a levelek sem kivételek e szabály alól. Itt van egy faparaméter, amely legalább 2 (és általában 50 és 2000 közötti értékeket vesz fel a kulcs méretétől függően az oldal méretéhez képest, amelyet viszont a tartalombejegyzés mérete határoz meg). $egy$ $2t-1$ ${\textstyle t-1}$ ${\textstyle 2t-1}$ ${\textstyle t}$
A leveleknek nincsenek leszármazottai; az összes többi kulcsot tartalmazó csomópontnál az adott csomópont gyermekeket tartalmaz. Ahol: $K_{1},\dots ,K_{n},$ $(n+1)$
- az első gyermek és minden gyermeke kulcsokat tartalmaz a tartományból $(-\infty ,K_{1});$
- mert a -edik gyermek és minden gyermeke tartalmaz kulcsokat az intervallumból $2 \leqslant i \leqslant n$ $én$ $(K_{i-1},K_{i});$
- $(n+1)$ -th gyermek és minden gyermeke tartalmaz kulcsokat az intervallumból $(K_{n},\infty ).$
Minden levél mélysége azonos.
A levelek egy szomszédhoz mutató hivatkozással rendelkeznek, amely lehetővé teszi, hogy gyorsan bejárja a fát a kulcsok növekvő sorrendjében, és hivatkozásokat az adatokra.

Épület

A B⁺-fa felépítéséhez szükség lehet a köztes struktúra újraépítésére, ez abból adódik, hogy a kulcsok számának minden csomópontban (a gyökér kivételével ) a fa fokának (vagy sorrendjének) hova kell lennie . Amikor megpróbálja beszúrni a ( )-edik kulcsot a csomópontba, szükségessé válik ennek a csomópontnak a szétválasztása; a fa szomszédos szintjén elhelyezett ()-edik kulcs a kialakított ágak elválasztó kulcsaként működik. . Speciális eset a gyökér felosztása, mivel ebben az esetben megnő a fa rétegeinek száma. A B⁺-fa levelének felhasadásának sajátossága, hogy egyenlőtlen részekre oszlik. Egy belső csomópont vagy gyökér felosztása azonos számú kulccsal rendelkező csomópontokat eredményez . $t$ $2t,$ $t$ $2t+1$ ${\textstyle t+1}$ $k.$

Struktúra tulajdonságai

A B⁺-fában könnyen megvalósítható a program függetlensége az információrekord szerkezetétől.
A keresés szükségszerűen egy lappal végződik.
A kulcs törlésének megvan az az előnye, hogy a törlés mindig a lapról történik.
A többi művelet a B-fákhoz hasonlóan történik.
A B⁺-fák ábrázolásához több memória szükséges, mint a klasszikus B-fák.
A B⁺-fák képesek egymás után hozzáférni a kulcsokhoz.

Alapműveletek egy szerkezeten

Keresés

A B⁺-fa gyökere a kiindulópontja a teljes értéktartománynak, amelyben minden belső csomópont egy részintervallum.

Tegyük fel például, hogy meg kell találnunk egy kulcs értékét egy B⁺-fában. Ehhez keresünk egy értéket tartalmazó levélcsomópontot Minden belső csomópontnál meg kell találnunk, hogy melyik következő gyermekcsomópontot kell követni, a B⁺-fa belső csomópontjának legfeljebb gyermeke van, ahol mindegyik egy külön részintervallum. A megfelelő csomópontot a csomópont kulcsértékeiben való kereséssel választjuk ki: $k$ $k.$ $t$

Funkció : search ( k ) return tree_search ( k , gyökér ); Funkció : tree_search ( k , csomópont ) ha a csomópont egy levél , akkor visszatér a csomópont ; switch k do case k < k [ 0 ] return tree_search ( k , p [ 0 ]); eset k [ i ] ≤ k < k [ i + 1 ] return tree_search ( k , p [ i + 1 ]); eset k [ d ] ≤ k return tree_search ( k , p [ d + 1 ]);

(Ez a pszeudokód feltételezi, hogy a duplikációkat figyelmen kívül hagyja.)

Hozzáadása

Új kulcs vagy új bejegyzés hozzáadásához először meg kell találnia azt a csomópontot, amelyhez hozzá szeretné adni őket. Ebben az esetben az algoritmus a következő:

Ha a csomópont nincs teljesen kitöltve (az elemek száma a beillesztés után nem több, mint ), akkor adjunk hozzá egy kulcsot (rekordot). $2t-1,$
Ellenkező esetben fel kell osztania a csomópontot:
- hozzon létre egy új csomópontot, majd helyezze át az elemek felét az aktuálisból az újba;
- adja hozzá az új csomópont legkisebb kulcsát és a hozzá tartozó címet (a csomópontot) a szülőhöz;
- ha a szülőcsomópont megtelt, hasonló módon ossza fel:
  - adja hozzá a középső kulcsot a szülőcsomóponthoz;
- ismételje meg mindaddig, amíg a szülőcsomópontot fel kell osztani.
Ha a gyökér szétválik, hozzon létre egy új gyökeret egy kulccsal és két mutatóval (a gyökérhez hozzáadott kulcs eltávolításra kerül a csomópontjából)

A B-fák a B⁺-fákkal ellentétben a gyökér oldaláról tágulnak, nem a levelek felől.

Eltávolítás

Kulcs vagy bejegyzés törléséhez először meg kell találnia azt a levélcsomópontot, amelyben az található. Algoritmus a levél csomópontból való eltávolításához:

Ha a csomópont legalább félig megtelt, az algoritmus leáll;
Ha a csomópontnak kevesebb eleme van, akkor:
- próbálja meg újra elosztani az elemeket, vagyis a „testvér” elemét hozzáadja a csomóponthoz - egy elemet, amelynek közös őse.
- ha az újraelosztás nem sikerül, egyesítse a csomópontot a "testvérrel".
Ha összevonás történik, távolítsa el a távoli csomópontra vagy annak "testvérére" mutató kulcsot vagy bejegyzést a szülőcsomópontból.

Az egyesülés a gyökérig terjedhet, ilyenkor a fa magassága csökken.

A műveletek számítási összetettsége

Az egyes műveletek számítási bonyolultsága a legrosszabb esetben: hol van a fa vagy az elágazási tényező sorrendje; a fa csomópontjaiban lévő ágak elemeinek száma . $O(\log {\frac {t}{2n)))$ $t$ $n$

Jegyzetek

↑ Douglas Comer. A mindenütt jelenlévő B-fa // ACM Computing Surveys. - 1979. - június ( 11. évf. , 2. sz.). - 121-137 . o . — ISSN 0360-0300 . Az eredetiből archiválva : 2015. november 17.

Irodalom

Zubov V. S., Shevchenko I. V. 6. fejezet: Keresés nem bináris fákban - B-fák // Az adatfeldolgozás struktúrái és módszerei. Workshop Delphi környezetben. - Filin, 2004. - S. 144-164. — ISBN 5-9216-0053-9 .
Donald Knuth . 4. Az összes fa generálása. A kombinatorikus generáció története // The Art of Programming = The Art of Computer Programming. - M. : "Williams" , 2007. - V. 4. - S. 160. - ISBN 0-321-33570-8 .

Linkek

B⁺ Fa vizualizáció - B+ Fa vizualizáció

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