Python - определение ближайшей временной метки

У меня есть метка времени Python datetime и большой dict (индекс), где ключи - это метки времени, а значения - это некоторая другая информация, которая меня интересует.

Мне нужно найти дату и время (ключ) в индексе, который ближе всего к метке времени, как можно эффективнее.

Сейчас я делаю что-то вроде:

for timestamp in timestamps:
    closestTimestamp = min(index,key=lambda datetime : abs(timestamp - datetime))

, что работает, но занимает слишком много времени - мой index dict имеет миллионы значений, и я выполняю поиск тысячи раз. Я гибкий со структурами данных и так далее - временные метки примерно последовательны, так что я повторяю от первой до последней. Точно так же метки времени в текстовом файле, который я загружаю в dict, являются последовательными.

Мы будем благодарны за любые идеи по оптимизации.