Why is it so slow?
Is it because my data is on HDD?
Or is it because the historical file database is placed on the HDD along with the files?
Or are these historical files not indexed at all?
This is a known problem (see https://github.com/syncthing/syncthing/issues/7393), however it should work relatively fine unless you’ve got thousands of files there, especially in a single folder that needs to be opened at once. If there are many files, but they are located in reasonable numbers inside subfolders, then the tree should still be usable.
When it comes to your questions, there is no database for the versioned files, so the GUI needs to check and index the folder each time you open the Restore Versions panel. The more files you’ve got there, the slower it will be, and especially on an HDD.
Essentially, I employ syncthing to back up the primary directory in Linux (containing numerous software kernel source codes) as well as the data partition in Windows (encompassing myriad games and music).
I deem it imperative to index all versions of the files; otherwise, it is arduous to guarantee the functional integrity of file history versions.
Frankly, the commonplace practice in NAS involves utilizing SSDs for system installation and HDD arrays for storing files, where the file index database can easily reside on SSDs or even utilize memory for caching. Nextcloud, for instance, utilizes the redis + PostgreSQL solution.
The filesystem is a pretty good index of what exists in it and what does not. If your index is slow, that’s the problem you should fix.