B-fa

• IPA:

B-fa

1. (matematika, algoritmusok)

A B-fa (B-tree) egy önkiegyensúlyozó keresőfa, amelyet adatok rendezett tárolására és gyors keresésére, beszúrására, valamint törlésére használnak. A B-fa biztosítja, hogy a fa mindig kiegyensúlyozott maradjon, így a műveletek időbonyolultsága garantáltan logaritmikus ((O(n))).

1. Több kulcs egy csomópontban:
   • Egy B-fa csomópontja több kulcsot is tárolhat.
   • A kulcsok rendezettek egy csomóponton belül.
2. Gyökér, belső csomópontok, levelek:
   • A gyökérnek legalább egy kulcsa van.
   • Az összes levél azonos mélységben található.
3. Gyermekek száma:
   • Ha egy csomópont (k) kulcsot tartalmaz, akkor pontosan (k+1) gyermeke lehet.
4. Rugalmas méret:
   • A csomópontok egy előre meghatározott minimális ((t)) és maximális ((2t-1)) számú kulcsot tartalmazhatnak, ahol (t) a B-fa rendje (minimum 2).
5. Egyensúly:
   • A fa mindig kiegyensúlyozott, azaz az összes levélcsomópont azonos távolságra van a gyökértől.

A keresés egy adott kulcsra ((k)) a B-fában rekurzív vagy iteratív módon végezhető el. Minden csomópont kulcsait rendezetten tárolják, így az adott kulcs gyorsan megtalálható, vagy eldönthető, hogy melyik gyermekágat kell vizsgálni.

• Nem teljes csomópont esetén:
  • Ha a célcsomópontban van szabad hely, a kulcsot egyszerűen beszúrjuk.
• Teljes csomópont esetén:
  • A telített csomópontot ketté kell osztani, és a középső kulcsot fel kell tolni a szülőbe.
  • Ez a művelet rekurzívan feljebb vihet kulcsokat, és akár a gyökércsomópontot is megoszthatja, így a fa magassága nő.

• Levélből:
  • Ha a törlendő kulcs egy levélben van, egyszerűen eltávolítjuk.
• Belső csomópontból:
  • A kulcs helyettesíthető az előtte vagy utána lévő legnagyobb vagy legkisebb kulccsal.
  • Ha szükséges, csomópontok összevonására vagy kölcsönzésére van szükség a gyermekcsomópontok között.

function BTreeSearch(x, k):
    i = 1
    amíg i <= n és k > key:
        i = i + 1

    ha i <= n és k == key:
        térj vissza (x, i)  # Kulcs megtalálva

    ha leaf:
        térj vissza None  # Kulcs nem található

    térj vissza BTreeSearch(child, k)

function BTreeInsert(T, k):
    ha root tele:
        s = CreateNode()
        root = s
        SplitChild(s, 1, root)
        InsertNonFull(s, k)
    különben:
        InsertNonFull(root, k)

function InsertNonFull(x, k):
    ha leaf:
        add k-t megfelelő helyre key-ben
    különben:
        keressük meg child-et, ahová k kerülne
        ha child tele:
            SplitChild(x, i, child)
        InsertNonFull(child, k)

function SplitChild(x, i, y):
    z = CreateNode()
    z lesz az y második fele
    középső kulcs felkerül az x-be

class BTreeNode:
    def __init__(self, t, leaf=False):
        self.t = t  # A B-fa rendje
        self.keys =   # Kulcsok
        self.children =   # Gyermekek
        self.leaf = leaf  # Levél-e a csomópont

class BTree:
    def __init__(self, t):
        self.root = BTreeNode(t, leaf=True)
        self.t = t

    def search(self, node, k):
        i = 0
        while i < len(node.keys) and k > node.keys:
            i += 1

        if i < len(node.keys) and node.keys == k:
            return node, i

        if node.leaf:
            return None

        return self.search(node.children, k)

    def insert(self, k):
        root = self.root
        if len(root.keys) == 2 * self.t - 1:
            s = BTreeNode(self.t)
            self.root = s
            s.children.append(root)
            self.split_child(s, 0)
            self.insert_non_full(s, k)
        else:
            self.insert_non_full(root, k)

    def insert_non_full(self, node, k):
        if node.leaf:
            node.keys.append(k)
            node.keys.sort()
        else:
            i = len(node.keys) - 1
            while i >= 0 and k < node.keys:
                i -= 1
            i += 1
            if len(node.children.keys) == 2 * self.t - 1:
                self.split_child(node, i)
                if k > node.keys:
                    i += 1
            self.insert_non_full(node.children, k)

    def split_child(self, parent, i):
        t = self.t
        child = parent.children
        new_child = BTreeNode(t, child.leaf)
        parent.keys.insert(i, child.keys)
        parent.children.insert(i + 1, new_child)
        new_child.keys = child.keys
        child.keys = child.keys

        if not child.leaf:
            new_child.children = child.children
            child.children = child.children

# Példa használat
btree = BTree(2)  # B-fa rendje 2
btree.insert(10)
btree.insert(20)
btree.insert(5)
btree.insert(6)
btree.insert(12)

node, index = btree.search(btree.root, 12)
if node:
    print(f"Kulcs megtalálva: {node.keys}")
else:
    print("Kulcs nem található.")

Kimenet:

Kulcs megtalálva: 12

A B-fa tulajdonságai: - Időbonyolultság: - Keresés, beszúrás, törlés: (O(n)) - Előnyök: - Nagy adatszerkezetek hatékony kezelése. - Disk alapú tárolásra is alkalmas (pl. adatbázisokban). - Hátrányok: - Az implementáció összetettebb, mint más adatszerkezeteké.

Alkalmazása széleskörű, például adatbázisokban, fájlrendszerekben és keresőmotorokban.

• B-fa - Értelmező szótár (MEK)
• B-fa - Etimológiai szótár (UMIL)
• B-fa - Szótár.net (hu-hu)
• B-fa - DeepL (hu-de)
• B-fa - Яндекс (hu-ru)
• B-fa - Google (hu-en)
• B-fa - Helyesírási szótár (MTA)
• B-fa - Wikidata
• B-fa - Wikipédia (magyar)