Chciałbym stworzyć listę wszystkich szkół w danej miejscowości.
Planuje to w ten sposób, że w tabeli szkoły będą kategorie:

1. przedszkole
2. podstawowa
3. gimnazjum
4. średnia
5. wyższa
(może być dużo więcej kategorii)

W kolejnej tabeli miasta, będe miał listę miejscowości.
1. Wrocław
2. Warszawa.
3. Kraków

Dodając nową szkołę użyję 3 tabeli, w której będe miał:
id, id_typu (z tabeli kategorie określające typ szkoły), id_miasta (z tabeli miasta), ulica:
1 2 2 Kościuszki 12


Tak to widzę, tylko czy w takim przypadku nie będzie problemu z np. wyszukiwaniem wszystkich szkół z danej miejscowości lub z danej ulicy (danej miejscowości) ?

Chciał bym móc przetwarzać dane na różne sposoby i zastanawiam się czy mój schemat budowy tabel jest prawidłowym, czy powiniennem to zrobić jakoś inaczej ?

Twój schemat jest prawidłowy. Z wyszukiwaniem nie będzie żadnego problemu, od tego są JOIN-y, np.:

[SQL] pobierz, plaintext 
SELECT `s`.*
FROM `szkoly` AS `s`
JOIN `typy` AS `t`
ON `t`.`id` = `s`.`id_typu`
WHERE `t`.`nazwa` = 'gimnazjum';
[SQL] pobierz, plaintext