Slajd 10 z 17

Pierwszym krokiem w tworzeniu dobrej struktury danych jest rozwiązanie problemu superstron. Drzewo Trie jest słownikiem w postaci drzewa. Początkowe bity adresu określają ścieżkę w drzewie prowadzącą do liścia, w którym jest adres fizyczny strony. Zauważmy, że długość ścieżki nie musi być stałą, dzięki czemu mamy strony różnej wielkości.

Możliwe (i stosowane) jest uogólnienie - więcej niż 1 bit wybiera kolejnego syna w drzewie - to jest konieczność, jeśli chcemy mieć płytkie drzewo, czyli małą liczbę dostępów do pamięci. Oczywiście jest to pewien kompromis - stopień wierzchołka i zużycie pamięci zależy wykładniczo od liczby bitów na poziom.