With mail server software, as with all software, you need to take a look under the hood and learn how the software works.
For example Cyrus IMAPd
uses Maildir format (at least by default), but in addition to that it has cyrus.{header,index,cache}
files which it uses for improving performance. Thanks to those data files, it can return mail headers and other common stuff to mail client without scanning through every mail file, which improves performance quite a lot.
With database based software, you need to find out which database server works best with your mail server, and you probably need a competent DBA to keep everything running smoothly. Also make sure that the mail server software choice of yours does generate sensible SQL queries.
If you want to sleep your nights peacefully, this is just a start. You also need to take into account the scalability of your system (for example, with Cyrus you can use Cyrus Murder
or put Perdition
in front of Cyrus to scale up to multiple servers), availability of your system (does it matter if one server node goes down or not), and of course maintainability of your system. How easy it would be to recover a single mailbox? Or the whole system? How to backup a potentially huge amount of mail? How to manage user accounts?
Database: generally speaking, regardless of the engine.
is hard to do...since the engine itself often defines how the database is setup/performs/options/characteristics/advantages etc.