B-tree
Üdvözlöm, Ön a B-tree szó jelentését keresi. A DICTIOUS-ban nem csak a B-tree szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a B-tree szót egyes és többes számban mondani. Minden, amit a B-tree szóról tudni kell, itt található. A B-tree szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. AB-tree és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.
Főnév
A B-tree (magyarul: B-fa) egy önkiegyensúlyozó, általánosított keresőfa-adatszerkezet, amelyet kifejezetten arra terveztek, hogy nagy mennyiségű adatot hatékonyan tároljon és kezeljen – főként olyan rendszerekben, ahol a lemezműveletek vagy külső memória a szűk keresztmetszet (pl. adatbázisok, fájlrendszerek).
A B-fa kulcstulajdonsága, hogy:
- több gyermekcsomópontot enged meg (nem csak kettőt, mint a bináris keresőfa),
- kiegyensúlyozott: minden kulcs ugyanakkora távolságra van a gyökértől,
- minimális számú lemezhozzáféréssel biztosít keresést, beszúrást és törlést.
🧱 1. Alapdefiníció (rendű B-fa)
Egy B-fa rendje azt jelenti, hogy:
- Minden belső (nem levél) csomópontnak legfeljebb gyermeke lehet,
- Minden nem gyökér csomópontban legalább gyerek van,
- Minden csomópont legfeljebb kulcsot tartalmaz,
- A kulcsok rendezettek, és elválasztják a gyerekek által határolt tartományokat.
🌲 2. Példa: B-fa vizuálisan (rend = 3)
/ \
- A gyökér 1 kulcsot tartalmaz (17), két gyermekre mutat.
- Bal oldali gyerek tartalmaz kulcsokat 3 és 8.
- Keresés 20-ra → 17-nél jobbra → megtalálható a levélben.
🔍 3. Alapműveletek
| Művelet | Időkomplexitás |
|---|---|
| Keresés | |
| Beszúrás | |
| Törlés |
Keresés:
- Indul a gyökérből, a megfelelő tartomány szerint halad lefelé,
- Olyan, mint többutas bináris keresés: adott kulcshoz a megfelelő gyermeken megy tovább.
Beszúrás:
- Az új kulcs a megfelelő levélbe kerül,
- Ha a levél megtelik, kettéválik, és a középső kulcs “felúszik” a szülőbe,
- Ez rekurzívan felfelé haladhat → új gyökér is keletkezhet.
Törlés:
- Ha a kulcs levélben van, egyszerűen törölhető,
- Ha a csomópont kulcsai túl kevesen maradnak, egyesít vagy átrendez más gyerekekkel.
📦 4. Alkalmazások
| Terület | Példák |
|---|---|
| Adatbázisok | MySQL, PostgreSQL indexelés |
| Fájlrendszerek | NTFS, HFS+, Ext4 indexelés |
| Kulcs-érték tárolók | LevelDB, RocksDB |
| Lemezalapú tárolás | Optimalizálva blokkalapú olvasásra |
⚙️ 5. Miért jó a B-fa?
- Kisebb magasság: mély bináris fáknál gyorsabb, mivel kevésbé nő a magasság nagy adattömeg esetén.
- Támogatja a külső memóriát: egy csomópont egy blokkba kerülhet (pl. 4 KB-os lemezblokk).
- Lemezbarát: optimalizálja az I/O-műveleteket.
🧬 6. Variációk
| Típus | Leírás |
|---|---|
| B+ tree | Minden adat a levelekben van, a belső csomópontok csak indexelnek |
| B* tree | A B-fánál hatékonyabb, egyesítés helyett átrendezéssel dolgozik |
| SB-tree | Skálázható, többdimenziós indexelésre |
📊 7. Összehasonlítás más fákkal
| Fa típusa | Jellemző |
|---|---|
| Bináris keresőfa (BST) | Csak 2 gyerek/csomópont, mély fa lehet |
| AVL-fa, Red-Black fa | Kiegyensúlyozott, de memóriaigényes |
| B-fa | Tágabb csomópont, disk I/O-ra optimalizált |
| B+ fa | Gyors szekvenciális hozzáférés, levelek láncoltak |
🧠 8. Összegzés
A B-tree az egyik legfontosabb adatszerkezet a tárolóbarát keresőműveletekhez. Különösen nagy adatállományok esetén előnyös, mivel kevesebb lépéssel eléri a kívánt kulcsot, minimalizálva az I/O-t. Lemezes környezetben, adatbázisoknál és fájlrendszereknél szinte ipari szabvány.