Et B*-træ er en type B-træ , hvor hver knude i træet er mindst ⅔ fuld (i modsætning til et B-træ, hvor dette tal er 1/2).
B*-træer blev foreslået af Rudolf Bayer og Edward McCraith , som studerede problemet med kompakthed af B-træer . B*-træet er relativt mere kompakt, fordi hver node bruges mere fuldt ud. I øvrigt adskiller denne type træ sig ikke fra et simpelt B-træ.
For at opfylde kravet "knuden er mindst 2/3 fuld", er man nødt til at opgive den simple procedure for opdeling af en overfyldt knude. I stedet er der en "transfusion" ind i den tilstødende knude. Hvis naboknuden også er fuld, så er nøglerne omtrent ligeligt opdelt i 3 nye knudepunkter.
Et B + -træ , der opfylder disse krav, kaldes et B *+ -træ [1] .
Træ (datastruktur) | |
---|---|
Binære træer | |
Selvbalancerende binære træer |
|
B-træer | |
præfiks træer |
|
Binær opdeling af rummet | |
Ikke-binære træer |
|
At bryde rummet op |
|
Andre træer |
|
Algoritmer |
|