Best way to implement A* algoritm

Best way to implement A* algoritm

Currently, I am working on a new feature for our project. This feature is
similar to google maps routing feature. But we are using are own routing
data, that has private roads, that doesn't exist in google maps and some
other data.
I have implemented A* algorithm for finding fastest route. All data is
stored on MS SQL server. Routing algorithm is also implemented on MS SQL.
It works, but performance is very poor.
I have did some profiling and found out that most slow operation is
reading data from Points and Lines tables (1 million records each)
I have added clustered indexes everywhere where is possible and optimized
stored procedure. Also, I have implemented division of data into tiles and
load only needed tiles to cache to avoid quering 1 million table with
points and lines. It became faster but not still enough fast.
In large towns with huge amount of roads in works slow. 5 KMs route takes
15-20 seconds. This website is hosted on Azure on a strong virtual
machine.
So, QUESTION IS BELOW.
Actually, I am thinking to exclude MSSQL and store all data as file (or
files) and load bulk data from hard drive to cache in RAM. I am not very
experienced guy in this area, and ask someone who is familiar - is it
possible, that using this way I will speed up my routing 5-10 times? In my
understanding reading bulk data from hard drive directly into memory
should be much faster than MS SQL 'insert from select' with all it's
checking and etc.
P.S. I can post current stored procedure if someone need
Thanks