You could do it with one table. Add a column to keep track of who's still in the tounament, then draw your players something like this:
$query = "SELECT name FROM my_table WHERE still_in = 'yes' " .
"ORDER BY RAND() LIMIT 2";
Then, after each match, the only change you'd need to make would be to the loser's row:
$query = "UPDATE my_table SET still_in = 'no' " .
"WHERE name = " . $loser;
Archiving of matches could be done in a separate table, or even other columns in the same table.
Edit: That won't quite work; it runs the risk of involving one person in more than one match at a time, or in one level of play more than once. Maybe more like this:
$query = "SELECT name FROM my_table" .
"WHERE still_in = 'yes' AND level = '" . $current_level . "' " .
"ORDER BY RAND() LIMIT 2";
$query = "UPDATE my_table SET still_in = 'maybe' " .
"WHERE name = '" . $name_1 . "' OR name = '" . $name_2 . "'";
// Then, after the match:
$query = "UPDATE my_table SET still_in = 'no' WHERE name = '" . $loser . "'";
$query = "UPDATE my_table SET (still_in = 'yes', level = '" . $next_level . "') " .
"WHERE name = '" . $winner . "'";
Anyway, you get the picture.