P.S: Weiß nicht ob sqLite das kann, aber es gibt Primärschlüsselverfahren, die direkt beim Einfügen nativ sortieren
Das sollte eigentlich jede Datenbank so machen, wenn ein Index auf der Spalte liegt. Der normale Standard-Index ist bei gängigen Datenbanken immer ein balancierter Baum, wenn man nichts anderes spezifiziert. Deswegen kostet das Sortieren bei einer Abfrage auch keine extra Zeit, wenn auf dem Sortierkriterium ein Index liegt.
Du kannst also ruhigen Gewissens jede Sekunde eine Abfrage à la
SELECT * FROM termine WHERE t1 <= zeit <= t2 ORDER BY zeit
machen. Das bleibt auch dann noch fast gleich schnell (O(log n)), wenn die Datenbank sehr groß wird (wobei es natürlich auch noch davon abhängt, wie viele Datensätze zwischen t1 und t2 liegen, logisch).