Kulcsfontosságú különbség: A számítógépekben a bináris fák olyan adatadat-struktúrák, amelyek az adatokat tárolják, és lehetővé teszik a felhasználó számára az adatok elérését, keresését, beillesztését és törlését az algoritmikus időben. A B és B + fa közötti különbség az, hogy egy B-fában a kulcsok és az adatok tárolhatók mind a belső, mind a levél csomópontokban, míg egy B + fában az adatok és a kulcsok csak a levélcsomópontokban tárolhatók. .
A bináris fák kiegyensúlyozott keresési fák, amelyek úgy vannak kialakítva, hogy jól működjenek a közvetlen hozzáférési másodlagos tárolóeszközökön, például mágneses lemezeken. Rudolf Bayer és Ed McCreight feltalálta a B-fa fogalmát.
A B-fa egy általánosított bináris keresési fa, amelyben bármely csomópont több mint két gyermek lehet. Minden B-fa belső csomópont számos kulcsot tartalmaz. Ezek a kulcsok elválasztják az értékeket, és tovább alakítják az alfákat. A B-fa belső csomópontjai változó számú gyermekcsomóponttal rendelkezhetnek, amelyek egy előre meghatározott tartományban vannak elrendezve. Abban az időben, amikor bármilyen adatot beiktatnak vagy eltávolítanak bármelyik csomópontból, megváltozik a gyermekcsomópontok száma. Az előre meghatározott tartomány fenntartása érdekében a belső csomópontok összekapcsolhatók vagy feloszthatók. Egy B-fában a gyermekcsomópontok sorozata megengedett, ami miatt az előre meghatározott tartományt meg kell őrizni.
A B-fákat nem kell újra kiegyensúlyozni, gyakran más, önfenntartó keresési fákkal ellentétben. Ezeknek a fáknak a csomópontjai nem mindig teljesek; ezért ezekben a fákban a terek feleslegesek, ami a tér elvesztéséhez vezet. Egy adott megvalósításhoz tipikusan csak a gyermekcsomópontok számának alsó és felső határai vannak rögzítve. Például egy 2-3 B-fában (gyakran egyszerűen 2-3-nak nevezik) minden belső csomópontnak csak 2 vagy 3 gyermekcsomópontja lehet.
Továbbá, a B-fa olyan rendszerekre van optimalizálva, amelyek nagy adatblokkokat olvasnak és írnak. Gyakran használják az adatbázisokban és a fájlrendszerekben. A B-fában minden csomópont ugyanolyan kiegyenlítési mélységben van a gyökércsomópontoktól. Ezek a mélységek lassan nőnek, amikor az elemek száma nő; ez azt eredményezi, hogy minden levél csomópont egy további csomópont van a gyökértől távolabb. Ezenkívül a B-fák előnyösebbek az adatokhoz való hozzáférésre fordított idő más megvalósításaihoz képest.
A B + fa egy n-tömbfa, egy csomóponttal, amely egy csomópontonként nagy számú gyermekből áll. A gyökér lehet egy levél vagy egy csomópont, amely több mint két gyermeket tartalmaz. A B + fa gyökérből, belső csomópontokból és levelekből áll.
A B + fa ugyanaz, mint egy B fa; az egyetlen különbség az, hogy a B + fában egy további szint van hozzáadva az alsó részhez kapcsolódó lapokkal. A B-fától eltérően a B + -fában minden egyes csomópont csak kulcsokat tartalmaz, és nem a kulcs-érték párokat.
Ezenkívül a B + fa kiegyensúlyozó tényezője vagy sorrendje megméri a fa belső csomópontjainak kapacitását, vagyis a csomópontok számát, amelyekre képesek. A csomópontok tényleges száma a belső csomópontok esetében korlátozott. A gyökér azonban kivétel, mivel több mint két gyermeke van. Ha például egy B + fa sorrendje 7, akkor minden belső csomópont (a gyökér kivételével) 4 és 7 gyermek között lehet; míg a gyökér 2 és 7 között lehet. A B + fa elsődleges értéke az adatok tárolása a hatékony visszanyeréshez egy blokk-orientált tárolási környezetben és különösen a fájlrendszerekben.
A B + fa elsődleges értéke az adatok tárolása és karbantartása, így az adatok nem veszítenek el. Ezt a megközelítést különösen blokk-orientált tárolási kontextusban és bizonyos fájlrendszerekben alkalmazzák. A levelek, amelyek a B + fa alsó indexblokkjai, gyakran összekapcsolódnak egymással egy összekapcsolt listában; így egyszerűbbé és hatékonyabbá teszi a blokk lekérdezéseket vagy rendezett iterációt a blokkokon keresztül. Továbbá a B + fákban nem kerül sor a térfaktorra. A B + fa hatékony házadatszerkezeti formátumot biztosít, ami egyszerűvé teszi a hozzáférést és tárolást. A B + fák különösen hasznosak adatbázis-rendszerindexként, ahol az adatok általában egy lemezen helyezkednek el.
A B és a B + fa összehasonlítása:
B fa | B + fa | |
Rövid web leírások | Az AB fa az információ tárolására és lekérdezésére szolgáló szervezeti felépítés egy fa formájában, amelyben az összes terminálcsomópont azonos távolságra van az alaptól, és az összes nem-terminális csomópont n és 2 n alfák vagy mutatók között van (ahol n egész szám). | A B + fa egy n-tömbfa, amely csomópontonként változó, de gyakran nagy számú gyermekkel rendelkezik. A B + fa gyökérből, belső csomópontokból és levelekből áll. A gyökér lehet egy levél vagy egy csomópont két vagy több gyermekkel. |
Más néven | Kiegyensúlyozott fa. | B plusz fa. |
Tér | Tovább) | Tovább) |
Keresés | O (log n) | O (log b n) |
Insert | O (log n) | O (log b n) |
Töröl | O (log n) | O (log b n) |
Tárolás | Egy B-fában a keresési kulcsok és a belső vagy levélcsomópontokban tárolt adatok. | Egy B + fában csak a levélcsomópontokban tárolt adatok. |
Adat | A három tároló levélcsomópontja inkább a nyilvántartások helyett a rekordok felé mutat. | A fa levélcsomópontjai a rekordok helyett a tényleges rekordot tárolják. |
Tér | Ezek a fák helyet pazarolnak | A fák nem pazarolnak helyet. |
A levélcsomópontok funkciója | A B-fában a levélcsomópont nem tárolhatja a hivatkozott listát. | B + fa esetén a levélcsomópont adatokat sorrendben kapcsolt listában rendezik. |
kutató | Itt a keresés nehéz lesz a B-fában, mivel az adatok nem találhatók a levélcsomópontban. | Itt minden adat keresése egy B + fában nagyon egyszerű, mivel minden adat megtalálható a levél csomópontokban. |
Keresés elérhetősége | Itt a B fában a keresés nem olyan egyszerű, mint egy B + fa. | Itt a B + fában a keresés egyszerűvé válik. |
Redundáns kulcs | Nem tárolják a redundáns keresőgombot. | Ezek redundáns keresőgombot tárolnak. |
Alkalmazások | Ezek egy régebbi változat, és nem olyan előnyösek, mint a B + fák. | Számos adatbázis-rendszer-implementátor előnyben részesíti a B + fa strukturális egyszerűségét. |
