Is there a Haskell database using algebraic datatypes?

Database-wise, take a look at Acid-State. There's also a tutorial for it as part of the Happstack Crash Course.

It does what you ask in terms of maintaining type safety in the model. I'm not sure how useful this'll be for you, but I've put it to use in a couple of web-apps, including here, and here (that second one is part of a benchmarking attempt pitting HDBC against MongoDB and AcidState, so you can use it to see how the three compare implementation-wise in the context of a Haskell web-application).

To your third question, at 5000 inserts/reads, you really shouldn't be worried about performance. If you take a look at those benchmarks I mentioned, the "large" benchmark runs a (relatively small) 50 000 transactions in very short order, and they were meatier insertions than what you seem to be doing.

Check out Persistent from Yesod:

Persistent is Yesod’s answer to data storage- a type-safe, universal data store interface for Haskell.

[...]

Persistent allows us to choose among existing databases that are highly tuned for different data storage use cases, interoperate with other programming languages, and to use a safe and productive query interface, while still keeping the type safety of Haskell datatypes.

Persistent follows the guiding principles of type safety and concise, declarative syntax.