Если нет требований к качеству, то хватит одного index.php и пара файлов: в один можно положить подключение к БД и запросы к БД - такие файлы ещё называют моделями, в другой отдельно положить вывод страницы, т.е. html. AJAX точно не знаю куда лучше положить, можно прям в html написать если кода мало(обычно AJAX делается через инструменты фреймворка). В таком случае у тебя получится, что главный файл - контроллер, файл с БД - модель, а файл с html - вид(шаблон).
Твой контроллер сможет делать запросы к БД и выводить шаблон с заполненными данными.
1. Проверяешь не пришло ли что то из формы и какая страница запрошена. $_POST $_GET(надеюсь об XSS ты в курсе)
2. Если пришло, то пишешь в БД, если нет требований по неповторению сообщений.
3. Вытаскиваешь из БД названия тем и заполняешь хедер. Тут нужно будет вытащить только те темы, которые нужно. Если требований нет, то сойдёт where id:$id limit 5; $id=rand(1, 150 000).
4. Поиск. Если пришла строка на поиск нужно сформировать запрос с условием Like.
Можно выполнить поиск текста от начала поля:
SELECT Таблица.* FROM Таблица WHERE Таблица.Поле Like 'текст*'
или в любой части поля - Like '*текст*'
5. Статистика работы PHP. memory_get_usage() - для объема используемой памяти, microtime() - для времени выполнения скрипта. По MySQL microtime() - время выполнения запроса.
6. Постраничный вывод тем. Считаешь число тем, делишь число тем на число тем на одной странице и в зависимости от запрошенного номера страницы выводишь запрошенные темы путем запроса в БД where id<:id $id берёшь из $_GET.
Примерно так. Возможно будет тормозить поиск. В таком случае надо будет либо менять запросы на легковесные(в запросах я не силён), либо memcache, либо sphinx. Возможно что то ещё.
P.S.
В реальности сложные сайты обычно пишут на фреймворках. Например Yii.