I'm looking for a way to store data in a decentralized way such that I can access any record from within the smart contract, probably through oracles I guess?
I've been looking into gundb but not sure how it can be used with solidity.
If you are ok with using (centralized) oracles then you can basically use any database alternative out there. Oracles provide access to the world outside blockchain so the oracle can just call any database you want - depending of course on what the oracle supports.
IPFS is quite popular for somewhat-decentralized data storage, for example.
Storing data on the Ethereum chain can get very economically infeasible.
I would suggest making use of IPFS via Filecoin. This breaks your files up in objects, encrypts it and distributes/stores copies on different user's storage mediums without them having they encryption keys. IPFS will provide you a hash to "relocate" your data. For added safety, you can save that hash on the Ethereum chain.
If your idea is to store data directly on the Ethereum chain and the regain access to it via a Smart Contract, this can be done by a few lines of code but will be economically infeasible for even relatively small data. Thus the latter is proposed.
Hope this helps.