Toutes les grandes bases de données (Oracle, MySQL, Postgres, Sybase, et SQL Server) ont des strutures de données internes qui sont proches des arbres équilibrés, et qui donnent toutes à peu près toutes les mêmes performances, car c'est pratiquement impossible de faire mieux. La différence entre les bases se fait donc surtout au niveau des interfaces plutôt que des moteurs.
MySQL est utilisé par de nombreux utilisateurs et parfois pour de très grosses bases de données. Les anciennes versions de son langage SQL n'avaient pas la richesse de certains autres langages SQL, mais il y a eu beaucoup d'améliorations depuis trois ou quatre ans.
Mais comme toujours en informatique, pour savoir ce qui est le mieux, il faut faire des tests avec des jeux de tests pertinents, parce que faire des prédictions à l'aveuglette est assez difficile (malgré tout, avec mon expérience de quatre bases parmi celles citées plus haut, je me risque à dire que MySQL ou autre chose, c'est quasiment du pareil au même).