Esempio in brevissimo:

Ho questo file (facciamo finta che invece che 4 siano 4 milioni di records).

file:
1 pippo
5 topolino
2 pluto
0 minnie

Ho questo indice .

indice:
0 3
1 0
2 2
5 1

Problema: Devo caricare il record con chiave 5 ([5, topolino]) dal file ma il file non è ordinato:

Apro l'indice ( in questo esempio l'indice deve essere ordinato, in realtà si usano strutture come BTREE perchè mantenere in ordine un indice costa troppo a meno che le modifiche al file siano molto rare).

Faccio una ricerca binaria sull'indice per trovare la posizione numero 5 con complessita o(log n)

Apro il file e leggo il record numero 1 in tempo costante.