Referanseside · Kapittel 18

Begreper & formler

Alle nøkkelbegrepene og formlene fra B-trær, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.

Øv med flashcards7 kort fra dette kapittelet

Begreper

Sentrale begreper fra kapittelet med korte definisjoner.

01Grad

t

Minimum antall barn en node kan ha. Roten kan ha færre.

02Balansert høyde

Alle blad har samme dybde, noe som gir $O (lo g_{t} n)$ høyde.

03Søk

Sammenligner nøkkel innen en node og traverserer korrekt barn.

04Splitting

Når en node er full, deles den i to og midtnøkkelen flyttes opp.

05Bruksområder

Databaseindekser, filsystemer, og søkeoptimering på disk.

Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.

h \leq lo g_{t} \frac{n + 1}{2}

O (t lo g_{t} n)