А Вы не пробовали добавить индекс на поле из 4-х байтов?
На MySQL индексы работают вполне приемлемо, главное, чтобы это был первый индекс созданный на таблице, тогда InnoDB ( default ) движок по умолчанию создаст кластеризованный индекс.
Вот синтаксис:
https://dev.mysql.com/doc/refman/8.0/en/create-ind...
обратите внимание на варианты UNIQUE, это поможет подтвердить, что ключ каждого текстового поля действительно уникальный.
Потом, во время запроса, надо будет аккуратно проверить синтаксис, чтобы подтвердить что запрос создан так, что индекс будет использован - тип данных в WHERE должен соответствовать, и что запрос действительно его использует ( по моему в MySQL это опция EXPLAIN ).
Если все сделано верно, то скорость выполнения запроса с миллиардом записей должна быть вполне приемлема.
Осталось проверить некоторые детали. Из вопроса не очень понятно, если база многопользовательская, или обслуживает пользователя работающего на этой же машине, есть ли одновременный доступ нескольких пользователей, иными словами доп информация по масштабу использования базы может помочь. И хотя SQLite намекает на чисто локальный характер записей, это детали которые лучше подтвердить, чем оставить за кадром.
Кроме того, какой характер ключа из 4 байтов, это число или бинарная конструкция, если бинарная, приемлемо ли его перевести к типу Integer, это существенно для скорости индекса.
---
Если же индекс уже создан, и не показывает результаты, которые Вы ожидаете, детали запрошенные выше помогут разобраться.
Средний
