B-fa

A B-fa adatszerkezet egy fa adatszerkezet, ami az adatokat rendezetten tárolja el. Az adatok mennyiségének növekedésével a beillesztés és törlés műveletigénye logaritmikusan nő. Leggyakrabban adatbázisokban és fájlrendszerekben használják.

A B-fa csomópontjai az előre meghatározott tartományban változó mennyiségű gyerek csomópontot tartalmazhatnak. Beillesztésnél és törlésnél a csomópontok száma változik, illetve hogy a gyerek csomópontok száma a meghatározott korlátok közt maradjon, egyesítés és szétválasztás is lehet.

Története

A B-Tree algoritmust Rudolf Bayer és Edward M. McCreight fejlesztette ki. A nevének eredete nem ismert. Elterjedt az a nézet, miszerint balanced-tree-t (kiegyensúlyozott fa) jelent, mások a Boeing szót sejtik a B mögött, a két kutató ekkor ugyanis a Boeing-nél dolgozott.