If I wanted to imprint the blockchain data on a database, with the purpose of performing complex or just different than the RPC-based queries, how would I do it? Would I have to go for a relational database or a NoSQL one? Eventually the database would be filled with hundreds of millions of records, which databases would perform well (respond quickly) to these gigantic numbers?
If you settle for a relational DB you can try BitcoinDatabaseGenerator.
Sources and wiki: https://github.com/ladimolnar/BitcoinDatabaseGenerator
It may take you a few hours (it takes me 90 minutes but that will vary depending on your hardware and configuration) to transfer the blockchain files to the DB.
If you do that take a look at the views that are already defined in the DB, some of them may be useful to you.
This probably depends on the type of queries you want to make and the data you want to retrieve from the database.
Personally, I have made good experiences with using a graph-database to traverse the block chain (e.g., Neo4j). However, the graph model you choose will influence the efficiency of certain types of queries.
I found blockchain to be reasonably manageable in size even if you are summarizing individual transactions in each block across all blocks
if you want to try to quickly play with blockchain, then download postgreSQL backup dump from here http://dumps.webbtc.com/bitcoin/ - even if postgeSQL is not what you are looking for, you will be able to quickly re-shape this data with simple SQL and bulk load it to neo4j or whatever other DB in minutes