He visto tablas con más registros, lo que se necesita en una base de datos es que todo esté bien indexado, no necesitas poner por ejemplo 2 tablas para 2 diferentes departamentos, pero puedes tener una columna llamada "departamento" (o id_departamento) y hacerla parte del índice, eso agilitaría las cosas.
http://es.wikipedia.org/wiki/%C3%8Dndice_(base_de_datos)
http://es.wikipedia.org/wiki/%C3%8Dndice_(base_de_datos)