bit.lyみたいなショートURLのサイトがありますが、
あれって、任意の（目的地の）URLと一対のユニークの6文字のパラメータをつけてるわけですが、
どうやってその6文字を生成するんでしょうか？

単純に思いつくのが
・DBにテーブル作成。カラムは url／パラメータ （最低限）
・乱数生成
・テーブル中にこの乱数を検索
・なければ発行＆登録
って感じですが、数十万件のログが出来た時、こんな処理だと負荷が心配です。
もっと効率的なやり方があるんでしょうか？
クエリキャッシュ使うとかえって危険そうだし…

PHPの質問なのかDBの質問なのかどっち付かずですが、お願いします

乱数のパターン（1文字目が何かとか）でテーブルを使い分ければ良いのかな？
どういうやり方が正解なのかなぁ…