Boas,
O VisualBasic não te serve de muito como recurso para criar uma base de dados.
Do que estás a procura é de software como Microsoft SQL 2005 Express que é gratuito, ou do MySql, sendo o da Microsoft o mais adequado pois a framework (vb7 up) já tem nativas bibliotecas para a ligação e execução de comandos em base de dados.
Depois de teres a base de dados estructurada, e só depois disso, é que te deves preocupar com o Visual Basic ou Visual C++ ou Java ou lá o que tu quiseres.
Agora, bases de dados há muitas. É como os chapéus.
Terás de ser mais específico em relação à tua necessidade de armazenamento e consulta de dados para que nos seja possível brindar-te com algumas estructuras.