People don't search, ever. There have been several requests concerning databases, even a few already this week. Anyway...
There are a few things you'll want to consider if you try and write your own. If you only ever need to read from the DB, you could use an XML file and query it using LINQ or Xpath. It may not be the fastest route and could create a lot of garbage, but its an option. The advantage here is that the DB will be deployed with your game to the TitleLocation, so you don't have to worry about managing storage devices.
If you need to update the DB as well (a reasonable request) you will need to maintain it on a Storage device, which will be a bit trickier. You'd have to ensure for every read and write that the device is connected and manage disconnects, that sort of thing. It can get pretty complicated fast.
If you have the memory available, something similar to the arrays approach above might not be a bad compromise. You could load your stats DB in memory and only perform searches and modifications to the in memory version. This way you have to worry less about storage devices (though you will still need to save once in a while).
My curling game has a DB of possible computer shots based on various match criteria, and I found the in memory approach to be fastest and easiest for me to manage. I don't have more than a few MB of data, and the structure is pretty specialized, so it may not work for everything.
