Немного странный формат хранения информации.
Если это ежедневник, то он должен хранить "начало" и "окончание" события.
Или что подразумевается под интервалами?
---
Делить на 2 таблицы - не стоит, запаритесь с синхронизацией.
Лучше/правильней выделить 1 поле-флаг, которое будет хранить статус "занято/не занято"
В основном зависит все не от размера базы, а от того для чего вам эти данные, какая у них структура и как вы их будете обрабатывать.
Для начала, нужно определиться реляционная база или нет нужна.
Потом уже выбирать СУБД в зависимости от ваших задач.
Полнотекстовый поиск наверное лучше (не точно).
---
Индекы помогут несомненно, но я думаю они уже заданы, без них было бы дольше 4 секунд. Какие вообще индексы заданы в таблицах?