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 node-jai az előre meghatározott tartományban változó mennyiségű gyerek-node-ot tartalmazhatnak. Beillesztésnél és törlésnél a node-ok száma változik, illetve hogy a gyerek-node-ok 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) jelent, mások a Boeing szót sejtik a B mögött, a két kutató ekkor ugyanis a Boeing-nél dolgozott.