This question's been around for a while. I think possibly it deserves a summarized directional answer.
First, some big headlines that may not seem especially important initially or are possibly hard to digest in one gulp.
- Don't migrate existing or imagined database designs directly to blockchain storage. Take a minimalist approach to on-chain storage. The Smart Contract should in my opinion ensure the integrity of the application. By extension, the Smart Contract should ensure the integrity of the data. Superfluous fields and descriptors generally go somewhere else where storage and performance is plentiful and cheap.
- Gas fees are for bytes stored and OpCodes executed. Again, minimalism because every byte counts.
Given the above, many designs tend toward storage of essential keys and little else.
In terms of a relational database, primary keys and foreign keys might be the minimum on-chain storage required to enforce referential integrity. "
Address Line 2" is the sort of descriptor that doesn't help in that regard, so is a good candidate to store elsewhere.
You could, for example, serialize all the descriptors and store the result in an offchain location - a tranditional database, IPFS, Swarm ... and then store the location and the hash of the current data in the Smart Contract. In this way the Smart Contract provides a pointer to "more information" and a way to confirm the fidelity of the data loaded from that location.
The only way to know the precise cost of byte-by-byte on-chain storage is to try something out and measure it. That involves finding a direction and coding it. To that end, some basic patterns and their strengths and weaknesses are unfolded here:
Are there well-solved and simple storage patterns for Solidity?
Those patterns are designed so that the gas cost is consistent at any scale. because it's critically important to avoid designing something with increasing cost as the dataset grows. A linked article near the end reveals measured gas costs for the example.
Conspicuously absent from this list is any form of sorting/ordering. A Smart Contract that focuses on integrity can often disregard that consideration. That is, if clients need ordered data then optimizations can often be worked out on the client side. The Smart Contracts are simplified considerably by focusing on allowing/disallowing insertions, deletes, updates, etc. Seldom needs a sorted list.
Having said that, a linked list is an inexpensive way to achieve searchable ordered results if needed. You'll find an experimental LinkedList example here:
Again, emphasis on simplicity and consistent gas cost at any scale. It simply will not work if costs for operations like insert and find increase with the size of the dataset.
Also, a generalized collection and an experimental example of enforcing referential integrity in a one-to-many relationship. Code in the repo linked above. Explanation here: https://medium.com/@robhitchens/enforcing-referential-integrity-in-ethereum-smart-contracts-a9ab1427ff42
Hope it helps.