I think you're underestimating the speed of modern computers and hard-drives, fzf can search through 100k entries easily without any delay. Try it with `cat /usr/share/dict/words | fzf`, it's extremely responsive (my dictionary is about 235k lines). If you want hard numbers, try piping your shell history through `time grep` and see how long finding an entry takes.
Even if you're on spinning rust, your shell history is probably in cache. You don't really need FST index for this usecase, IMHO.
With SQLite one automatically gets reliable persistent storage. Try to emulate that with a text file with history that eliminates duplicates. It is surprisingly hard to archive.
I use SQLite history to have context aware line suggestion in my shell. So the command that gets ghost displayed (and can be expanded with right arrow) depends on the current working directory, its parents and recency. This is fast enough using SQLite to just dump all commands into it and query on each typed letter.
The DB is at this point 10years old. I use it to evaluate my work habits and patterns. More recently I have started transitioning to a different shell and I used it to move only the functions and aliases I still use, instead of the full collection.