MySQL / PHP, but more of a MATH Question (Shortening Script)

For my latest project I need to shorten the URLs which I then put in a mysql database. I now ran against a problem, because I don't know how to solve this. Basically, the shortened strings should look like this (I want to include lowercase letters, uppercase letters and numbers)

a
b
...
z
0
...
9
A
...
Z 
aa
ab
ac
...
ba

So, 1. URl --> a. Stored in mysql. Next time, a new url gets stored to --> b because a is already in the mysql database.

And that is it. But I don't have any idea. Could someone of you please help me out?

Edit: Formattted & Further explanation.

It is kinda like the imgur.com URL shortening service. It should continue like this until infinity (which is not needed, I think...)

You can use the following function (code adapted from my personal framework):

function Base($input, $output, $number = 1, $charset = 'abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ')
{
    if (strlen($charset) >= 2)
    {
        $input = max(2, min(intval($input), strlen($charset)));
        $output = max(2, min(intval($output), strlen($charset)));
        $number = ltrim(preg_replace('~[^' . preg_quote(substr($charset, 0, max($input, $output)), '~') . ']+~', '', $number), $charset[0]);

        if (strlen($number) > 0)
        {
            if ($input != 10)
            {
                $result = 0;

                foreach (str_split(strrev($number)) as $key => $value)
                {
                    $result += pow($input, $key) * intval(strpos($charset, $value));
                }

                $number = $result;
            }

            if ($output != 10)
            {
                $result = $charset[$number % $output];

                while (($number = intval($number / $output)) > 0)
                {
                    $result = $charset[$number % $output] . $result;
                }

                $number = $result;
            }

            return $number;
        }

        return $charset[0];
    }

    return false;
}

Basically you just need to grab the newly generated auto-incremented ID (this also makes sure you don't generate any collisions) from your table and pass it to this function like this:

$short_id = Base(10, 62, $auto_increment_id);

Note that the first and second arguments define the input and output bases, respectively.

Also, I've reordered the charset from the "default" 0-9a-zA-Z to comply with your examples.

You can also just use base_convert() if you can live without the mixed alphabet case (base 36).