Hopp til innhold

B-tre

Fra Wikipedia, den frie encyklopedi

Et B-tre er innen informatikk en form for selvbalanserende tredatastruktur, som sorterer data og tillater søking, sekvensiell aksess, innsettelse og sletting i en logaritmisk tid. B-treet er en generalisering av et binært søketre, ved at en node kan ha mer enn to barn. I motsetning til et selvbalanserende binært søketre, er et B-tre optimalt for å lese og skrive større mengder med data, og er derfor et godt eksempel på en datastruktur i eksternt minne. B-trær blir mye brukt i databaser og filsystemer.