Creare sistema di indicizzazione tramite id per la ricerca in più categorie

Come da titolo, vorrei un consiglio su come strutturare la registrazione di alcuni dati nel DB!
Ho delle categorie che variano, basate su ID univoci e vorrei che quando registro un nuovo record, tramite dei checkbox seleziono le categorie in cui va inserito per poi estrarlo.
Esempio, io ho:
Cat 1
Cat 2
Cat 3
Cat 4

Poi registro un nuovo record (post, news o quel che è) e vorrei che fosse correlata alla 1, 3 e 4! Come posso fare epr registrarlo nel DB in modo da estrarlo poi con dei filtri (PHP e MYSL, uno script di ricerca per categoria)?