Как в mysql выбрать ближайшую бОльшую и ближайшую мЕньшую запись из базы в 1 запрос?
В комментариях тебе уже ответили вариант с order by. Запрос order by и limit очень тяжелый для sql сервера, его очень сложно оптимизировать.

Есть еще min max но тебе нужны id, значит вложенный запрос по timestamp, не уверен что это будет быстрее (лучше поэкспериментируй)
select * from xxx where
   timestamp=(select min(timestamp) from xxx where timestamp > ...)
or timestamp=(select max(timestamp) from xxx where timestamp < ...)p.s. я заметил что ничего не сказано про одинаковые значения timestamp в разных записях, если брать limit 1 то будет выбираться случайная запись (точнее 100500 раз одна но в какой то момент другая - undefined behavior), этот запрос выдаст все записи с одинаковыми timestamp

Вообще то sql базы данных не очень подходят к задачам, где есть относительный порядок, будут накладные расходы, причем сильно заметные при больших размерах и больших количествах запросов.

В каких то ситуациях можно очень СИЛЬНО оптимизировать задачу, если есть какое то знание о том как данные записываются в таблицу. Например если известно гарантированное окно времени, в течении которого поступают данные, и их не сильно много можно просто сделать
select * from xxx
where timestamp > date - const_interval
  and timestamp < date + const_intervalа затем уже среди этих данных выбирать по выше определенным алгоритмам или даже на бакэнде 

Если изменений данных значительно меньше запросов на чтение (особенно если модификации не предполагаются и есть только добавления), то можно складывать искомые значения сразу в момент создания записи (добавлять id новой записи в предыдущую, и тут же ее id в новую), делать это можно как тригерами так и на бакэнде, накладных расходов на такую запись мало зато на чтение данные доступны за константное время, максимально быстро
select p2.*,p3.* from xxx p1
  left join xxx p2 on p1.id=p2.previous_id
  left join xxx p3 on p1.id=p3.next_id
where p1.timestamp=...в данном случае строчка будет одна, данные раскиданы по колонкам p2.* и p3.*

В каких то ситуациях можно даже завести отдельный сервис, службу, дающую нужный ответ на порядок быстрее чем любой sql (например за счет того что данные хранятся в оперативной памяти), очень часто этим сервисом может стать тот же бакэнд (если это не cgi приложение), дабы не множить сущности, но если речь идет не об одной физической машине а о кластере, то там есть варианты и сложности.
Самое нелепое в этом задании - что поле created_at не уникально, и в таблице может быть сколько угодно записей со временем, до секунды совпадающим с заданным. Что лишает всякого смысла предположения про "ближайшие большую и меньшую".